樹圖和單圈圖的調和指標

王曉

（商洛學院數學與計算機應用學院，陜西　商洛　726000）

樹圖和單圈圖的調和指標

王曉

（商洛學院數學與計算機應用學院，陜西商洛726000）

摘要：利用改變圖的葉子點數目的變換，得到了關于調和指標的兩個引理，證明了固定階數的樹圖和單圈圖的調和指標的緊的上下界，并給出相應極值的圖類。

關鍵詞：調和指標；樹圖；單圈圖

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

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

1　改變圖的葉子點數目的變換

首先，我們定義改變圖的葉子點數目的兩種變換，并給出相應的關于調和指標的引理。

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

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

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

減少葉子點變換：設圖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，（注：當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′滿足V（G′）＝V（G），E（G′）＝（E（G）＼｛xvn2｝）∪｛u1vn2｝，則稱圖G′是由G經過減少葉子點變換而得到的圖。

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

證明當n1＝1時，減少葉子點的變換即為增加葉子點變換的逆變換，由引理1，所以H（G）－H（G′）＜0?，F設n2≥n1≥2，令NG（x）＼｛un1，vn2｝＝｛x1，x2，…，xn3｝，由dG（x）≥3，即n3≥1。圖G中與x，u1無關的邊的集合記為E0，由G′的構造，知G′中與x，u1無關的邊的集也為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的證明，根據調和指標的定義，有

2　樹圖和單圈圖的調和指標

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

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

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

證明記Ak＝Cnm1，n2，…，nk，設Ak在中路Pn1一個端點u與Cm中的頂點x相連，v是Pn1的另一個端點，y，z是Cm中x的兩個鄰點。類似于減少葉子點的變換，在圖Ak中刪去邊xy且將頂點y與路Pn1的另一個端點v相連，所得的圖為Cnm2，＋…n1，nk，記為Ak－1。當n1＝1時，此變換為增加葉子點變換的逆變換，由引理1，所以H（Ak）＜H（Ak－1）。當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設Δn1，n2，n3表示由圈C3中的三個頂點分別增加n1，n2，n3個懸掛點而得到的圖，Δn表示由C3中的一個頂點增加n個懸掛點而得到的圖，若n＝n1＋n2＋n3，則有H（Δn1，n2，n3）≥H（Δn），等號成立當且僅當n1，n2，n3中有兩個為0。

證明不失一般性，假設n1≥n2≥n3。當n2＝n3＝0時，有Δn1，n2，n3≌Δn，即H（Δn1，n2，n3）＝H（Δn）。

當n2≥1，n3＝0時，有

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

當n2≥n3≥1時，有

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

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

證明由調和指標定義，顯然H（Cn）＝n/2，H（Δn－3）＝5/2＋4/（n＋1）－6/n。當n＝3時，只有一個單圈圖，即為C3，H（C3）＝3/2，結論成立。現假設n≥4，對于階為n的單圈圖G，若G≠Cn，設Cm為G中的圈，則G可經過有限次的減少葉子點的變換，變為Cnm1，n2，…，nk，其中m≥k，n＝n1＋n2＋…＋nk＋m，由引理2和命題1，即H（G）＜H（Cn）；另一方面，若G≠Δn－3，則G可經過有限次的增加葉子點的變換，變為Δn1，n2，n3，其中n＝n1＋n2＋n3＋3，由引理1和命題2，即H（Δn－3）＜H（G）。因此原結論成立。

參考文獻：

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

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

［9］王曉，段芳.單圈圖的解析［J］.華東師范大學學報：自然科學版，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

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

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