樹圖和單圈圖的調(diào)和指標

王曉

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

樹圖和單圈圖的調(diào)和指標

王曉

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

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

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

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

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

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

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

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

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

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

減少葉子點變換：設(shè)圖G中存在頂點u1，u2，…，un1，v1，v2，…，vn2，x滿足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時Pn1＋1為一條邊），dG（x）≥3。記A＝｛u1，u2，…，un1｝，B＝｛v1，v2，…，vn2｝，C＝V（G）＼［A∪B∪｛x｝］，對a∈A，b∈B，c∈C，有abE（G），acE（G），bcE（G）。構(gòu)造圖G′滿足V（G′）＝V（G），E（G′）＝（E（G）＼｛xvn2｝）∪｛u1vn2｝，則稱圖G′是由G經(jīng)過減少葉子點變換而得到的圖。

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

證明當(dāng)n1＝1時，減少葉子點的變換即為增加葉子點變換的逆變換，由引理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無關(guān)的邊的集合記為E0，由G′的構(gòu)造，知G′中與x，u1無關(guān)的邊的集也為E0且對任意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。類似于引理1的證明，根據(jù)調(diào)和指標的定義，有

2　樹圖和單圈圖的調(diào)和指標

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

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

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

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

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

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

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

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

由于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時，有

由于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，左邊等號成立時當(dāng)且僅當(dāng)G≌Δn－3，右邊等號成立時當(dāng)且僅當(dāng)G≌Cn，其中Cn表示n個頂點的圈，Δn－3表示由C3中的一個頂點增加n－3個懸掛點而得到的圖。

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

參考文獻：

［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個懸掛點的仙人掌圖的調(diào)和指標［J］.閩南師范大學(xué)學(xué)報：自然科學(xué)版，2014（2）：7－11.

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

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

Harmonicindexoftreeandunicyclicgraphs

WangXiao

（SchoolofmathematicsandComputerEngineering，ShangluoUniversity，Shangluo726000，China）

Abstract：Weobtaintwolemmasforharmonicindexofgraphsthroughthetransformschangingleafnumbers.Wefurtherprovethesharpboundsforharmonicindexoftreeandunicyclicgraphswithfixedorder.Wealsopresentthecorrespondingextremalgraphs.

Keywords：harmonicindex；treegraphs；unicyclicgraphs

中圖分類號：O157.5

文獻標識碼：A

文章編號：1002-4026（2016）01-0083-04

DOI：10.3976/j.issn.1002－4026.2016.01.014

收稿日期：2015-04-23

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

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