樹(shù)圖和單圈圖的調(diào)和指標(biāo)

王曉

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西　商洛　726000）

樹(shù)圖和單圈圖的調(diào)和指標(biāo)

王曉

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

摘要：利用改變圖的葉子點(diǎn)數(shù)目的變換，得到了關(guān)于調(diào)和指標(biāo)的兩個(gè)引理，證明了固定階數(shù)的樹(shù)圖和單圈圖的調(diào)和指標(biāo)的緊的上下界，并給出相應(yīng)極值的圖類(lèi)。

關(guān)鍵詞：調(diào)和指標(biāo)；樹(shù)圖；單圈圖

設(shè)G＝（V（G），E（G））表示一個(gè)圖，其中V（G）和E（G）分別表示G的頂點(diǎn)集和邊集。圖G的頂點(diǎn)數(shù)目｜V（G）｜稱(chēng)為G的階，對(duì)于任意u∈V（G），NG（u）和dG（u）分別表示圖G中u的鄰點(diǎn)集和頂點(diǎn)度。其他涉及到的概念參閱文獻(xiàn)［1］。

圖G的調(diào)和指標(biāo)H（G）［2－5］是Randic指標(biāo)的一種重要形式，定義為Zhong［3－4］和Liu［5］分別給出了在樹(shù)圖、單圈圖和不含三角形的圖上調(diào)和指標(biāo)的性質(zhì)，Deng［6］給出了圖的色數(shù)和調(diào)和指標(biāo)的關(guān)系，文獻(xiàn)［7－8］對(duì)仙人掌圖的調(diào)和指標(biāo)進(jìn)行了研究。樹(shù)圖和單圈圖在分子拓?fù)浣Y(jié)構(gòu)中起著重要作用，本文中我們利用改變圖的葉子點(diǎn)數(shù)目的兩個(gè)變換及其對(duì)應(yīng)的關(guān)于調(diào)和指標(biāo)的引理，用一種簡(jiǎn)單方式，重新證明了固定階數(shù)的樹(shù)圖和單圈圖的調(diào)和指標(biāo)的緊的上下界，并給出相應(yīng)極值的圖類(lèi)。

1　改變圖的葉子點(diǎn)數(shù)目的變換

首先，我們定義改變圖的葉子點(diǎn)數(shù)目的兩種變換，并給出相應(yīng)的關(guān)于調(diào)和指標(biāo)的引理。

增加葉子點(diǎn)變換：設(shè)圖G中存在邊e＝uv滿(mǎn)足u，v都不是葉子點(diǎn)并且e是一條割邊或者其所在最短圈的長(zhǎng)度至少為4，則刪去頂點(diǎn)v，將G中與v關(guān)聯(lián)的邊都與u關(guān)聯(lián)，且增加一個(gè)新的頂點(diǎn)，記為v′，與u關(guān)聯(lián)，所得的新圖記為G′，稱(chēng)圖G′是G經(jīng)過(guò)增加葉子點(diǎn)變換而得到圖。

引理1設(shè)圖G中存在邊e＝uv滿(mǎn)足u，v都不是葉子點(diǎn)并且e是一條割邊或者其所在最短圈的長(zhǎng)度至少為4，圖G′是圖G經(jīng)過(guò)對(duì)邊e經(jīng)過(guò)增加葉子點(diǎn)變換而得到的圖，則有H（G′）＜H（G）。

證明令NG（u）＼｛v｝＝｛u1，u2，…，un1｝，NG（v）＼｛u｝＝｛v1，v2，…，vn2｝，由于u，v都不是葉子點(diǎn)，故n1≥1，n2≥1。設(shè)E0為圖G中與u，v無(wú)關(guān)的邊的集合，由G′的構(gòu)造知，圖G′中不與u，v′關(guān)聯(lián)的邊的集合也是E0，對(duì)xy∈E0有dG（x）＝dG′（x），dG（y）＝dG′（y），且dG（u）＋dG（v）＝n1＋n2＋2＝dG′（u）＋dG′（v′）。由圖的調(diào)和指標(biāo)的定義，有

減少葉子點(diǎn)變換：設(shè)圖G中存在頂點(diǎn)u1，u2，…，un1，v1，v2，…，vn2，x滿(mǎn)足G［｛u1，u2，…，un1，x｝］≌Pn1＋1和G［｛v1，v2，…，vn2，x｝］≌Pn2＋1，其中uiui＋1∈E（G）（i＝1，2，…，n1－1），vjvj＋1∈E（G）（j＝1，2，…，n2－1），un1x∈E（G），vn2x∈E（G），n2≥n1≥1，（注：當(dāng)n1＝1時(shí)Pn1＋1為一條邊），dG（x）≥3。記A＝｛u1，u2，…，un1｝，B＝｛v1，v2，…，vn2｝，C＝V（G）＼［A∪B∪｛x｝］，對(duì)a∈A，b∈B，c∈C，有abE（G），acE（G），bcE（G）。構(gòu)造圖G′滿(mǎn)足V（G′）＝V（G），E（G′）＝（E（G）＼｛xvn2｝）∪｛u1vn2｝，則稱(chēng)圖G′是由G經(jīng)過(guò)減少葉子點(diǎn)變換而得到的圖。

引理2設(shè)圖G中存在頂點(diǎn)u1，u2，…，un1，v1，v2，…，vn2，x滿(mǎn)足減少葉子點(diǎn)變換的條件，圖G′是G經(jīng)過(guò)減少葉子點(diǎn)變換而得到的圖，則有H（G′）＞H（G）。

證明當(dāng)n1＝1時(shí)，減少葉子點(diǎn)的變換即為增加葉子點(diǎn)變換的逆變換，由引理1，所以H（G）－H（G′）＜0?，F(xiàn)設(shè)n2≥n1≥2，令NG（x）＼｛un1，vn2｝＝｛x1，x2，…，xn3｝，由dG（x）≥3，即n3≥1。圖G中與x，u1無(wú)關(guān)的邊的集合記為E0，由G′的構(gòu)造，知G′中與x，u1無(wú)關(guān)的邊的集也為E0且對(duì)任意xy∈E0有dG（x）＝dG′（x），dG（y）＝dG′（y），NG′（x）＼｛un1｝＝｛x1，x2，…，xn3｝，dG′（xi）＝dG（xi），dG′（x）＝dG（x）－1＝n3＋1，dG′（un1）＝dG（un1）＝dG′（vn2）＝dG（vn2）＝dG′（u2）＝dG（u2）＝dG′（u1）＝dG（u1）＋1＝2。類(lèi)似于引理1的證明，根據(jù)調(diào)和指標(biāo)的定義，有

2　樹(shù)圖和單圈圖的調(diào)和指標(biāo)

定理1設(shè)T是階為n≥3的樹(shù)圖，則有2（n－1）/n≤H（T）≤n/2－1/6，左邊等號(hào)成立時(shí)當(dāng)且僅當(dāng)T≌Kn－1，1，右邊等號(hào)成立時(shí)當(dāng)且僅當(dāng)T≌Pn。

證明由調(diào)和指標(biāo)的定義，對(duì)于星Kn－1，1和路Pn，易知H（Pn）＝n/2－1/6（n≥3），H（Kn－1，1）＝2（n－1）/n。顯然，當(dāng)n＝3時(shí)P3≌K2，1，結(jié)論成立。設(shè)n≥4，令m表示樹(shù)T的葉子點(diǎn)數(shù)目。若m＝2，則T≌Pn，即H（T）＝n/2－1/6；若m＝n－1，則T≌Kn－1，1，即有H（T）＝2（n－1）/n。現(xiàn)假設(shè)3≤m≤n－2，我們要證明2（n－1）/n＜H（T）＜n/2－1/6。由于T的每一條邊都是割邊且葉子點(diǎn)數(shù)目m≤n－2，所以T中存在割邊e＝uv滿(mǎn)足u，v都不是葉子點(diǎn)，則對(duì)邊e＝uv作增加葉子點(diǎn)的變換得樹(shù)T′，根據(jù)引理1，有H（T′）＜H（T）且樹(shù)T′的葉子點(diǎn)數(shù)目為m＋1。若m＋1＝n－1，則T′≌Kn－1，1，否則經(jīng)過(guò)有限次的增加葉子點(diǎn)變換可得Kn－1，1，所以2（n－1）/n＝H（Kn－1，1）＜H（T）。另一方面，由于m≥3，根據(jù)引理2，樹(shù)T可經(jīng)過(guò)減少葉子點(diǎn)的變換得到葉子點(diǎn)數(shù)目為m－1的樹(shù)T″且H（T″）＞H（T）。若m－1＝2，則T″≌Pn，否則經(jīng)過(guò)有限次的減少葉子點(diǎn)變換得Pn，即H（T）＜H（Pn）＝n/2－1/6。

命題1設(shè)Pn1，Pn2，…，Pnk為k條路（或者為孤立點(diǎn)），m≥k，n＝n1＋n2＋…＋nk＋m，將每一條路Pni的一個(gè)端點(diǎn)與圈Cm中一個(gè)點(diǎn)相連（圈Cm中每個(gè)點(diǎn)最多只能連一條路），所得的圖用Cn1，n2，…，nkm表示，則有

證明記Ak＝Cnm1，n2，…，nk，設(shè)Ak在中路Pn1一個(gè)端點(diǎn)u與Cm中的頂點(diǎn)x相連，v是Pn1的另一個(gè)端點(diǎn)，y，z是Cm中x的兩個(gè)鄰點(diǎn)。類(lèi)似于減少葉子點(diǎn)的變換，在圖Ak中刪去邊xy且將頂點(diǎn)y與路Pn1的另一個(gè)端點(diǎn)v相連，所得的圖為Cnm2，＋…n1，nk，記為Ak－1。當(dāng)n1＝1時(shí)，此變換為增加葉子點(diǎn)變換的逆變換，由引理1，所以H（Ak）＜H（Ak－1）。當(dāng)n1≥2時(shí)，2≤dAk－1（z）＝dAk（z）≤3，2≤dAk－1（y）＝dAk（y）≤3，類(lèi)似引理2的證明，有

以此類(lèi)推，有H（Ak）＜H（Ak－1）＜H（Ak－2）＜…＜H（A0＝Cn），即H（Cn1，n2，…，nkm）＜H（Cn）。

命題2設(shè)Δn1，n2，n3表示由圈C3中的三個(gè)頂點(diǎn)分別增加n1，n2，n3個(gè)懸掛點(diǎn)而得到的圖，Δn表示由C3中的一個(gè)頂點(diǎn)增加n個(gè)懸掛點(diǎn)而得到的圖，若n＝n1＋n2＋n3，則有H（Δn1，n2，n3）≥H（Δn），等號(hào)成立當(dāng)且僅當(dāng)n1，n2，n3中有兩個(gè)為0。

證明不失一般性，假設(shè)n1≥n2≥n3。當(dāng)n2＝n3＝0時(shí)，有Δn1，n2，n3≌Δn，即H（Δn1，n2，n3）＝H（Δn）。

當(dāng)n2≥1，n3＝0時(shí)，有

由于2f（1，1）－1/2＝1/10，根據(jù)引理3，f（n1，n2）是關(guān)于n1，n2的增函數(shù)，所以H（Δn1，n2，n3）－H（Δn）＞0。

當(dāng)n2≥n3≥1時(shí)，有

由于2g（1，1，1）－1/2＝0，根據(jù)引理3，g（n1，n2，n3）是增函數(shù)，所以H（Δn1，n2，n3）－H（Δn）＞0。

定理2設(shè)G是階為n≥3的單圈圖，則有5/2＋4/（n＋1）－6/n≤H（G）≤n/2，左邊等號(hào)成立時(shí)當(dāng)且僅當(dāng)G≌Δn－3，右邊等號(hào)成立時(shí)當(dāng)且僅當(dāng)G≌Cn，其中Cn表示n個(gè)頂點(diǎn)的圈，Δn－3表示由C3中的一個(gè)頂點(diǎn)增加n－3個(gè)懸掛點(diǎn)而得到的圖。

證明由調(diào)和指標(biāo)定義，顯然H（Cn）＝n/2，H（Δn－3）＝5/2＋4/（n＋1）－6/n。當(dāng)n＝3時(shí)，只有一個(gè)單圈圖，即為C3，H（C3）＝3/2，結(jié)論成立。現(xiàn)假設(shè)n≥4，對(duì)于階為n的單圈圖G，若G≠Cn，設(shè)Cm為G中的圈，則G可經(jīng)過(guò)有限次的減少葉子點(diǎn)的變換，變?yōu)镃nm1，n2，…，nk，其中m≥k，n＝n1＋n2＋…＋nk＋m，由引理2和命題1，即H（G）＜H（Cn）；另一方面，若G≠Δn－3，則G可經(jīng)過(guò)有限次的增加葉子點(diǎn)的變換，變?yōu)棣1，n2，n3，其中n＝n1＋n2＋n3＋3，由引理1和命題2，即H（Δn－3）＜H（G）。因此原結(jié)論成立。

參考文獻(xiàn)：

［1］DIESTELR.Graphtheory：ElectronicEdition2000［M/OL］［2015-01-10］.https：//www.researchgate.net/publication/240024329-Graph-Theory-Electronic-Editio-2000.

［2］FAJTLOWICZS.OnconjecturesofGraffiti-II［J］.CongrNumer，1987，60：187－197.

［3］ZHONGLP.Theharmonicindexforgraphs［J］.AppliedmathematicsLetters，2012，25（3）：561－566.

［4］ZHONGL.Theharmonicindexonunicyclicgraphs［J］.ArsCombinatoria，2012，104（104）：261－269.

［5］LIUJX.Ontheharmonicindexoftriangle-freegraphs［J］.Appliedmathematics，2013，4（8）：1204－1206.

［6］DENGHY，BALACHANDRANS，AYYASWAMYSK，etal.Ontheharmonicindexandthechromaticnumberofagraph［J］.DiscreteAppliedmathematics，2013，161（16/17）：2740－2744.

［7］陳錦麗.具有k個(gè)懸掛點(diǎn)的仙人掌圖的調(diào)和指標(biāo)［J］.閩南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2014（2）：7－11.

［8］CHENJL，LVJB.Ontheharmonicindexofcacti［J］.InternationalJournalofAppliedmathematicsandStatistics，2014，52（1）：72－83.

［9］王曉，段芳.單圈圖的解析［J］.華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2009（1）：13－21.

Harmonicindexoftreeandunicyclicgraphs

WangXiao

（SchoolofmathematicsandComputerEngineering，ShangluoUniversity，Shangluo726000，China）

Abstract：Weobtaintwolemmasforharmonicindexofgraphsthroughthetransformschangingleafnumbers.Wefurtherprovethesharpboundsforharmonicindexoftreeandunicyclicgraphswithfixedorder.Wealsopresentthecorrespondingextremalgraphs.

Keywords：harmonicindex；treegraphs；unicyclicgraphs

中圖分類(lèi)號(hào)：O157.5

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1002-4026（2016）01-0083-04

DOI：10.3976/j.issn.1002－4026.2016.01.014

收稿日期：2015-04-23

基金項(xiàng)目：陜西省教育廳自然科學(xué)專(zhuān)項(xiàng)基金（12JK0889）；商洛學(xué)院科研基金（12SKY011，14SKY003）

作者簡(jiǎn)介：王曉（1980－），男，講師，研究方向?yàn)閳D論及其應(yīng)用。Email：wangxiaomath＠163.com