完美匹配單圈圖的hyper－Wiener指標

侯遠，鄭藝容

（1.福州大學 至誠學院，福建 福州 350002；2.廈門理工學院 應用數學學院，福建 廈門 361024）

在化學理論中，基于分子圖的頂點間距離的拓撲指標對刻畫分子圖以及建立分子結構和特征間的關系有重要作用，同時被廣泛用于預測化合物的物理化學性質和生物活性.Randic＇在1993年提出了無圈圖的hyper－Wiener指標的定義，之后klein等人［1－3］將Randicc＇的定義推廣到所有連通圖.頂點u和v 間的距離d（u，v｜G）表示頂點u和v 之間最短路的長度，則圖G 的hyper－Wiener指標為

Bo Zhou［5］提出了hyper－Wiener指標的另一計算式.令d（G，k）表示圖G 中距離為k 的無序點對的個數，則圖G 的hyper－Wiener指標為

令G＝（V，E）表示頂點數｜V（G）｜＝n，邊數｜E（G）｜＝m 的連通圖.若m＝n＋c－1，則G 被稱為c－圈圖.特別地如果c＝1，則圖G 稱為單圈圖.Kn，Pn與K1，n－1分別表示n階完全圖，路及星.圖G 中不鄰接的2條邊稱為是獨立的.兩兩獨立的邊構成的集合稱為圖G 的一個匹配.如果圖G 的所有頂點都包含在一個匹配中，則稱這個匹配為圖G 的一個完美匹配.

文獻［4－8］研究了樹的hyper－Wiener指標，因此有必要對非Kn的c－圈圖的hyper－Wiener指標做進一步研究.

猜想1：設完美匹配c－圈圖G（n，m）為取得最小hyper－Wiener指標的極圖，則G 不包含P5且必有一頂點u度數為

令U3（s1，s2，s3）表示由3個頂點極小圈C3＝r1r2r3r1和粘在極小圈頂點ri上的懸掛樹Tri構成的單圈圖.其中｜V（Tri）｜＝si表示懸掛樹Tri頂點個數.引理1—3在文獻［9－10］中已給出證明：

引理1 設U3（s1，s2，s3），U3（s1＋s2，0，s3）及U3（s1＋s2＋s3，0，0）為如上定義單圈圖，則

引理2 設G 和G′為由子圖A，B 和路Ps＝p1p2…ps（s≥2）構成的n 階簡單連通圖（圖1），則WW（G）＞WW（G′）.

引理3 設H 和H′為如上所定義的n 階連通圖（圖1），則當n≥5時，WW（H）≥WW（H′），等號成立當且僅當｜V（A）｜＝2.

令U＋（2n）表示2n階完美匹配單圈圖的集合.設Uk（2n）為u＋（2n）中由k個頂點極小圈Ck＝r1r2…rkr1和粘在極小圈頂點ri上的懸掛樹Tri構成的單圈圖.若邊e＝uv為懸掛樹上一條非懸掛邊，施行圖形變換Ⅰ：收縮邊e＝uv為頂點u，在頂點u上增加一條懸掛邊uu′；否則施行圖形變換Ⅱ：收縮邊uv 和邊u1u 到頂點u1，在頂點u1上增加長為2的路u1u′v′（圖1），最終得到單圈圖（t1，t2，…，tk）（圖2）.

圖1 引理2中的圖G 和G′與引理3的圖H 和H′Fig.1 Graphs Gand G′in Lemma 2，Hand H′in Lemma 3

推論1 設Uk（2n）和（t1，t2，…，tk）為如上所定義的完美匹配單圈圖，則

證明 將連通圖G＝（V，E）的頂點集分為3部分，e＝uv為連通圖G 的一條邊，

設x∈Nr2（e）－｛r2｝且y∈V（Tr2）－｛r2｝，下列等式成立：

情形1：k為偶數，設頂點x，y∈V（U＋k）－｛r1，r2｝，顯然

等號成立當且僅當k＝4且t1＝t2＝｜V（Trk）｜＝0.

等號成立當且僅當k＝5且t1＝t2＝｜V（Trk）｜＝0.證畢.

圖2 圖形變換Ⅳ與ⅤFig.2 Graph transformationⅣandⅤ

證明 設x∈Nr2（e）－｛r2｝且y∈V（Tr2）－｛r2，｝，下列等式成立：

情形3：k為偶數，顯然N＝（e）是空集.設頂點x，y∈V（t1，t2，…，tk））－｛r1，r2｝，顯然d（x，y｜

等號成立當且僅當k＝4且t1＝t2＝｜V（Trk）｜＝0.

等號成立當且僅當k＝5且t1＝1，t2＝｜V（Trk）｜＝0.證畢.

設邊e＝r1r2為圈Ck上的一條邊，若頂點r1和r2上都沒有懸掛邊，對邊r1r2施行圖形變換Ⅳ（圖2）；若頂點r1，r2上各有一個懸掛邊，對邊r1r2施行圖形變換Ⅴ（圖2）.

證明 由圖形變換Ⅲ及引理3可知，不等式（8）顯然成立.由等式（2）可知

不妨假設t1≠0且證畢.

定理1 設G∈u＋（2n）（n＞4），則

圖3 圖（t1，t2，t3）與（t1，t2，t3）Fig.3 Graphs （t1，t2，t3）and（t1，t2，t3）

［1］ DOBRYNIN A A，GUTMAN I，KLAVZAR S，et al.Wiener index of hexagonal systems［J］.Acta Appl Math，2002，72：247－294.

［2］ KLAVZAR S，ZIGERT P，GUTMAN I.An algorithm for the calculation of the hyper－Wiener index of benzenoid hydrocarbons［J］.Comput Chem，2000，24：299－233.

［3］ KLEIN D J，LUKOVITS I.On the definition of the hyper－Wiener index for cyclecontaining structures［J］.J Chem Inf Comput Sci，1995，35：50－52.

［4］ GUTMAN I.Relation between hyper－Wiener and Winer index［J］.Chem Phys Lett，2002，364：352－356.

［5］ ZHOU Bo，GUTMAN I.Relations between Wiener，hyper－Wiener and Zagreb indices［J］.Chem Phys Lett，2004，394：93－95.

［6］ KHALIFEH M H，YOUSEFI－AZARI H，ASHRAFI A R.The hyper－Wiener index of graph operations［J］.Comput Math Appl，2008，56：1402－1407.

［7］ WIENER H.Structural determination of paraffin boiling points［J］.J Amer Chem Soc，1947，69：17－20.

［8］ CASH G G.Polynomial expressions for the hyper－Wiener index of extended hydrocarbon networks［J］.Chem，2001，25：577－582.

［9］ 侯遠.單圈圖的hyper－Wiener指標［J］.數學研究，2013，46：142－150.HOU Yuan.On the hyper－Wiener index of unicyclic graphs［J］.Journal of mahthematical study，2013，46：142－150.

［10］ 侯遠.完美匹配樹的hyper－Wiener指標［J］.閩江學院學報，2013，34：10－12.HOU Yuan.Minimum hyper－Wiener index of trees with perfect matchings［J］.Journal of Minjiang University，2013，34：10－12.