完美匹配單圈圖的hyper－Wiener指標(biāo)

侯遠(yuǎn)，鄭藝容

（1.福州大學(xué) 至誠(chéng)學(xué)院，福建 福州 350002；2.廈門理工學(xué)院 應(yīng)用數(shù)學(xué)學(xué)院，福建 廈門 361024）

在化學(xué)理論中，基于分子圖的頂點(diǎn)間距離的拓?fù)渲笜?biāo)對(duì)刻畫分子圖以及建立分子結(jié)構(gòu)和特征間的關(guān)系有重要作用，同時(shí)被廣泛用于預(yù)測(cè)化合物的物理化學(xué)性質(zhì)和生物活性.Randic＇在1993年提出了無圈圖的hyper－Wiener指標(biāo)的定義，之后klein等人［1－3］將Randicc＇的定義推廣到所有連通圖.頂點(diǎn)u和v 間的距離d（u，v｜G）表示頂點(diǎn)u和v 之間最短路的長(zhǎng)度，則圖G 的hyper－Wiener指標(biāo)為

Bo Zhou［5］提出了hyper－Wiener指標(biāo)的另一計(jì)算式.令d（G，k）表示圖G 中距離為k 的無序點(diǎn)對(duì)的個(gè)數(shù)，則圖G 的hyper－Wiener指標(biāo)為

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

文獻(xiàn)［4－8］研究了樹的hyper－Wiener指標(biāo)，因此有必要對(duì)非Kn的c－圈圖的hyper－Wiener指標(biāo)做進(jìn)一步研究.

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

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

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

引理2 設(shè)G 和G′為由子圖A，B 和路Ps＝p1p2…ps（s≥2）構(gòu)成的n 階簡(jiǎn)單連通圖（圖1），則WW（G）＞W(wǎng)W（G′）.

引理3 設(shè)H 和H′為如上所定義的n 階連通圖（圖1），則當(dāng)n≥5時(shí)，WW（H）≥WW（H′），等號(hào)成立當(dāng)且僅當(dāng)｜V（A）｜＝2.

令U＋（2n）表示2n階完美匹配單圈圖的集合.設(shè)Uk（2n）為u＋（2n）中由k個(gè)頂點(diǎn)極小圈Ck＝r1r2…rkr1和粘在極小圈頂點(diǎn)ri上的懸掛樹Tri構(gòu)成的單圈圖.若邊e＝uv為懸掛樹上一條非懸掛邊，施行圖形變換Ⅰ：收縮邊e＝uv為頂點(diǎn)u，在頂點(diǎn)u上增加一條懸掛邊uu′；否則施行圖形變換Ⅱ：收縮邊uv 和邊u1u 到頂點(diǎn)u1，在頂點(diǎn)u1上增加長(zhǎng)為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 設(shè)Uk（2n）和（t1，t2，…，tk）為如上所定義的完美匹配單圈圖，則

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

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

情形1：k為偶數(shù)，設(shè)頂點(diǎn)x，y∈V（U＋k）－｛r1，r2｝，顯然

等號(hào)成立當(dāng)且僅當(dāng)k＝4且t1＝t2＝｜V（Trk）｜＝0.

等號(hào)成立當(dāng)且僅當(dāng)k＝5且t1＝t2＝｜V（Trk）｜＝0.證畢.

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

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

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

等號(hào)成立當(dāng)且僅當(dāng)k＝4且t1＝t2＝｜V（Trk）｜＝0.

等號(hào)成立當(dāng)且僅當(dāng)k＝5且t1＝1，t2＝｜V（Trk）｜＝0.證畢.

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

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

不妨假設(shè)t1≠0且證畢.

定理1 設(shè)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］ 侯遠(yuǎn).單圈圖的hyper－Wiener指標(biāo)［J］.數(shù)學(xué)研究，2013，46：142－150.HOU Yuan.On the hyper－Wiener index of unicyclic graphs［J］.Journal of mahthematical study，2013，46：142－150.

［10］ 侯遠(yuǎn).完美匹配樹的hyper－Wiener指標(biāo)［J］.閩江學(xué)院學(xué)報(bào)，2013，34：10－12.HOU Yuan.Minimum hyper－Wiener index of trees with perfect matchings［J］.Journal of Minjiang University，2013，34：10－12.