李 莎，卓瑪措，王 微

（1.青海師范大學(xué)數(shù)學(xué)系，青海西寧810008；2.唐山市第四十九中學(xué)，河北唐山063000）

Hosoya指數(shù)第二小、第三小的雙圈圖

李 莎1，卓瑪措1，王 微2

（1.青海師范大學(xué)數(shù)學(xué)系，青海西寧810008；2.唐山市第四十九中學(xué)，河北唐山063000）

雙圈圖是邊數(shù)等于點數(shù)加1的連通圖.一個圖的Hosoya指數(shù)是這個圖的所有匹配的個數(shù).在已有結(jié)論的基礎(chǔ)上通過加邊，并利用求指數(shù)的刪邊、刪點公式，刻畫了具有m－匹配的Hosoya指數(shù)第二小、第三小的雙圈圖.

Hosoya指數(shù)；m－匹配；雙圈圖

關(guān)于圖的Hosoya指數(shù)是H.Hosoya在1971年提出的，它是組合化學(xué)的拓撲指標中的一個突出例子，也是目前研究的熱點之一.［1－7］這里考慮的所有圖均是有限、簡單、無向圖，沒有定義的概念和術(shù)語，參見文獻［8］.對于一個圖G，我們用V（G）表示它的點集，E（G）表示它的邊集.G中的兩條邊若不相鄰，則稱這兩條邊是獨立的.G中k個相互獨立的邊組成的集合稱為G的一個k－匹配.用Z（G）表示G的匹配的個數(shù)，則其中m（G，k）表示G的k－匹配的個數(shù)，并且m（G，0）＝1，m（G，1）＝｜E（G）｜.容易看出，若m（G，k）＝0，則m（G，k＋1）＝0（k≥2）.并且些刻畫Hosoya指數(shù)極圖的文獻，主要刻畫了給定的幾類圖－樹，涉及四邊形、六圈的特定結(jié)構(gòu)的圖［5，9－13］.文獻［14］刻畫了具有m－匹配的Hosoya指數(shù)最小及第二小的樹.文獻［15］刻畫了具有m－匹配的Hosoya指數(shù)最小和第二小的單圈圖，及具有m－匹配的Hosoya指數(shù)最小的雙圈圖.文獻［16］刻畫了具有m－匹配的Hosoya指數(shù)第三小至第六小的單圈圖.而我們刻畫了具有m－匹配的Hosoya指數(shù)第二小、第三小的雙圈圖.

1 預(yù)備知識

令M表示G的一個匹配，若v與M中一條邊關(guān)聯(lián)，則稱v是M飽和的，記為v∈M；否則稱為M不飽和的，記為v?M.如果G中所有點均是M飽和的，則稱M是G的一個完美匹配.如果不存在G中的一個匹配M′，滿足｜M′｜＞｜M｜，則稱M是G的最大匹配.顯然，完美匹配一定是極大匹配.我們用α′（G）表示G的最大匹配｜M′｜＞｜M｜的邊數(shù).令U（n，m）表示α′（G）＝m點數(shù)為n的單圈圖.B（n，m）表示α′（G）＝m點數(shù)為n的雙圈圖.

若W?V（G），我們用G－W表示刪掉W中的點及與這些點關(guān)聯(lián)的邊的G的子圖.類似的，如果E′?E（G），用G－E′表示刪掉E′中的邊的G的子圖.如果W＝v，并且E′＝｛xy｝，我們用G－v，G－xy分別代替G－｛v｝，G－｛xy｝.對于圖G的一個點v，令NG（v）＝｛v｝∪｛u｜uv∈E（G）｝.

引理1［14］令G表示一個圖，并且v∈V（G），令v1，v2，…，vk是v的鄰點，則

引理2［14］令G表示一個圖，并且uv表示G的一條邊，則

推論1 令G表示一個圖，如果u∈V（G）是G的一個懸掛點，并且v是u的唯一的鄰點，則

引理3［14］令G表示具有k個分支G1，G2，…，Gk的圖，則

圖1 一些具有m－匹配的單圈圖和雙圈圖

引理4［14］令Pn和Sn表示含有n個點的路和星，則對于含有n個點的所有樹T，我們有

這里fn是第n個Fibonacci數(shù)，并且f0＝0，f1＝1.

引理5 令G表示一個圖，G1是G的子圖，則Z（G）≥Z（G1）.并且若｜E（G1）｜＜｜E（G）｜，則

因為G1的每一個匹配也是G的匹配，從而引理5顯然成立.

引理6 令T是一個樹，α′（T）＝k（k≥1），并且T?lK1∪kK2（l≥0），則Z（T）≥5·2k－2等號成立當(dāng)且僅當(dāng)T?P4∪（k－2）P2∪l′（k1）（l′≥0）.

引理7［15］G∈U（n，m）（n≥2m，m≥4），則Z（G）≥2m－2（2n－3m＋4）等號成立當(dāng)且僅當(dāng)G?U1（n，m）（如圖1）.

引理8［15］令G∈U（n，m）（n≥2m，m≤4），G?U1（n，m）.則Z（G）≥2m－4（10n－15m＋13）等號成立當(dāng)且僅當(dāng)G?U2（n，m）（見圖1）.

引理9［16］令G∈U（n，m）（n≥2m，m≥4），G?｛U1（n，m），U2（n，m）｝，則Z（G）≥2m－4（10n－15m＋14）等號成立當(dāng)且僅當(dāng)G∈｛U3（n，m），U7（8，4），U10（10，5）｝.

引理10 令T是一個樹，α′（T）＝m（m≥1），并且T?｛（n－2m）K1∪mK2，P4∪（m－2）K2∪（n－2m）K1｝，則Z（T）≥3×2m－1等號成立當(dāng)且僅當(dāng)T?｛T3，T5｝（見圖2）.若還有其他含有m個匹配的圖，以圖2中9個圖中的一個作為子圖，則T3，T5在m≥4中是第三小的圖.

圖2 一些包含若干K1和K2的具有m－匹配的圖

引理11［15］令G∈B（n，m）（n≥2m，m≥4），則Z（G）≥2m－2（2n－3m＋5）等號成立當(dāng)且僅當(dāng)G?B1（n，m）（見圖1）.

2 主要結(jié)果及證明

定理1 令G∈B（n，m），G?B1（n，m）（n≥2m，m≥4），則Z（G）≥2m－4（10n－15m＋18）等號成立當(dāng)且僅當(dāng)G∈｛B2（n，m），B7（8，4）｝.

證明 令G∈B（n，m）（n≥2m，m≥4），并且M是G的一個m－匹配，我們總能從G的圈中找出一條邊uv，使得uv?M，則G－uv是一個連通單圈圖.此外，α′（G－uv）＝m（因為G－uv是G的一個子圖，由引理5有α′（G－uv）≤α′（G）＝m，注意到M是G－uv的一個m－匹配，我們有α′（G－uv）≥m，因此α′（G－uv）＝m，G－uv∈U（n，m）.現(xiàn)在分以下三種情況討論：

（1）G－uv?U1（n，m），并且G?B1（n，m），則G∈｛B2（n，m），G1，G2，G3，G4，G5，G6，G7｝（見圖1），由引理1直接計算，得：

因此，Z（Gi）＞Z（B2（n，m）），1≤i≤7.

（2）G－uv?U1（n，m），并且G?B1（n，m），由引理8，Z（G－uv）≥2m－4（10n－15m＋13）等號成立當(dāng)且僅當(dāng)G－uv?U2（n，m）.注意到G－｛u，v｝有（m－2）－匹配，所以有Z（G－｛uv｝）≥2m－2等號成立當(dāng)且僅當(dāng)G－｛u，v｝?（n－2m＋1）K1∪（m－2）K2，易看出uv中必有一個點是U2（n，m）中的一個（n－m）度點，另一個是U2（n，m）中的一個3度點，這種情況是不可能的.由引理6，若Z（G－｛u，v｝）≥5·2m－4等號成立當(dāng)且僅當(dāng)G－｛u，v｝?（m－4）K2∪P4∪（n－2m＋2）K1.由引理2，

等號成立當(dāng)且僅當(dāng)G－uv?U2（n，m），并且G－｛u，v｝?（m－2）K2∪P4∪（n－2m＋2）K1.易看出u，v中的一個點是U2（n，m）中的一個（n－m）度點，另一個是一個鄰接于U2（n，m）中的一個2度點的懸掛點.因此等號成立當(dāng)且僅當(dāng)G?B2（n，m）.

（3）G－uv?｛U1（n，m），U2（n，m）｝，如果m＝4，n＝8，則

并且

所以

等號成立當(dāng)且僅當(dāng)u，v的兩個點在U7（8，4）中為3度點.因此等號成立當(dāng)且僅當(dāng)G?B7（8，4）.如果m＝5，n＝10，則Z（G－uv）≥Z（U10（10，5）），并且Z（G－｛u，v｝）≥25－2＝23＝Z（（5－2）K2），

等號成立當(dāng)且僅當(dāng)G－uv?U10（10，5），且G－｛u，v｝?3 K2.此時G不可能是m＝5時，Hosoya指數(shù)第二小的圖.

當(dāng)G－uv?｛U1（n，m），U2（n，m），U7（8，4），U10（10，5）｝，由引理9，Z（G－uv）≥2m－4（10n－15m＋14）等號成立當(dāng)且僅當(dāng)G－uv?U3（n，m）.注意到G－｛u，v｝有（m－2）－匹配，所以有Z（G－｛u，v｝）≥2m－2等號成立當(dāng)且僅當(dāng)G－｛u，v｝?（n－2m＋2）K1∪（m－2）K2.從而

等號成立當(dāng)且僅當(dāng)G－uv?U3（n，m），而且G－｛u，v｝?（m－2）K2∪（n－2m＋2）K1.此時，uv的一個端點必是U3（n，m）的一個（n－m）度點，另一個是鄰接于一個3度點的2度點，此時Z（G）≥Z（B2（n，m））.綜上，定理得證.

定理2 G∈B（n，m），G?｛B1（n，m），B2（n，m），B7（8，4）｝（n≥2m，m≥4），則

等號成立當(dāng)且僅當(dāng)G∈｛G2，B3（n，m），B10（10，5），B12（12，6），B11（13，5）｝.

證明 G∈B（n，m）（n≥2m，m≥4），使得G?｛B1（n，m），B2（n，m），B7（8，4）｝，并且M是G的一個m－匹配，我們總能從G的一個圈中選出一條邊uv，使得uv?M，則G－uv是一個n度點的連通單圈圖，并且α′（G－uv）＝m（因為G－uv是G的一個子圖，由引理5我們有α′（G－uv）≤α′（G）＝m，注意到M是G－uv的一個m－匹配，我們有α′（G－uv）≥m，因此α′（G－uv）＝m）.現(xiàn)在分以下4種情況討論：

（1）G－uv?U1（n，m），并且G?｛B1（n，m），B2（n，m），B7（8，4）｝，由定理1，有

（2）G－uv?U1（n，m），并且G?｛B1（n，m），B2（n，m），B7（8，4）｝，由引理8，有

等號成立當(dāng)且僅當(dāng)G－uv?U2（n，m）.注意到G－｛u，v｝有（m－2）－匹配，我們再分3種情況討論：

ⅰ.若G－｛u，v）?（m－2）K2∪（n－2m＋2）K1，Z（G－｛u，v｝）＝2m－2，則容易看出uv的一個端點是U2（n，m）的一個（n－m）度點，并且uv的另一個端點是U2（n，m）的一個3度點.顯然，這是不可能的.

ⅱ.若G－｛u，v｝?（m－4）P2∪P4∪（n－2m＋2）K1，Z（G－｛u，v｝）＝5·2m－4，因此G?B2（n，m）.矛盾.

ⅲ.由引理10，我們有Z（G－｛u，v｝）≥3·2m－3等號成立當(dāng)且僅當(dāng)G－｛u，v）?｛T3，T3｝（見圖2）.因此，如果G－｛u，v｝?T5，那么

但P5是T5的子圖，并且U2（n，m）中的子圖P5必以U2（n，m）的（n－m）度點為點，從而若u，v中有點是（n－m）度點，則G－｛u，v｝中不可能有T5.若v中沒有點是（n－m）度點，則G－uv?U2（n，m），從而矛盾.如果G－｛u，v｝?T3，那么

等號成立當(dāng)且僅當(dāng)uv的一個端點是U2（n，m）的（n－m）度點，另一個端點是鄰接于一個3度點的懸掛點，從而Z（G）≥Z（G2）.

（3）G－uv?｛U1（n，m），U2（n，m）｝，此時Z（G－uv）≥2m－4（10n－15m＋14）等號成立當(dāng)且僅當(dāng)G－uv?U3（n，m）.又G－｛u，v｝中有（m－2）－匹配，Z（G－｛u，v｝）≥2m－2等號成立當(dāng)且僅當(dāng)G－｛u，v｝?（m－2）K2∪（n－2m＋2）K1.此時，u，v中必有一個端點是（n－m）度點，另一個是鄰接于一個3度點的2度點，此時G?B2（n，m），矛盾.從而Z（G－｛u，v｝）≥5·2m－4等號成立當(dāng)且僅當(dāng)G－｛u，v｝?（m－4）P2∪P4∪（n－2m＋2）K1.此時，

當(dāng)m＝4，n＝8，則Z（G－uv）≥Z（U7（8，4）），此時G－｛u，v｝中有2－匹配，從而｛G－｛u，v｝｝≥22.矛盾.若G－｛u，v｝?P4∪2k1，此情況不可能.當(dāng)G－｛u，v｝?｛T3，T5｝，此情況也不可能.當(dāng)m＝5，n＝10，則Z（G－uv）≥Z（U10（10，5）），并且G－｛u，v｝中有3－匹配.

等號成立當(dāng)且僅當(dāng)G?（B10（10，5））.

（4）G－uv?｛U1（n，m），U2（n，m），U3（n，m），U7（8，4），U10（10，5）｝，此時Z（G－uv）≥2m－4（10n－15m＋15）等號成立當(dāng)且僅當(dāng)G∈｛U4（n，m），U5（n，m）｝，并且G－｛u，v｝中有（m－2）－匹配，Z（G－｛u，v｝）≥2m－2等號成立當(dāng)且僅當(dāng)G－｛u，v）?（m－2）K2∪（n－2m＋2）K1.

等號成立當(dāng)且僅當(dāng)G－uv?U4（n，m）且G－｛u，v｝?（m－2）K2∪（n－2m＋2）K1，或G－uv?U5（n，m）且G－｛u，v｝?（m－2）K2∪（n－2m＋2）K1.此時易得Z（G）≥Z（G2），并且容易證出B12（12，6），B11（10，5）也是Hosoya指數(shù)第三小的圖.

［1］ HOSOYA H.Topological index，a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons［J］.Bull Soc Jpn，1971，44：2332－2339.

［2］ CYVIN S J，GUTMAN I.Hosoya index of fused molecules［J］.MATCH Commun Math Comput Chem，1988，23：89－94.

［3］ CYVIN S J，GUTMAN I，KOLAKOVIC.Hosoya index of some polymers［J］.MATCH Commun Math Comput Chem，1989，24：105－117.

［4］ GUTMAN I.On the Hosoya index of very large molecules［J］.MATCH Commun Math Comput.Chem，1988，23：95－103.

［5］ GUTMAN I.Extremal hexagonal chains［J］.J Math Chem，1993，12：197－210.

［6］ GUTMAN I，POLANSKY O E.Mathematical concepts in organic chemistry［M］.Berlin：Springer，1986：1－228.

［7］ TURKER L.Contemplation on the Hosoya indices［J］.J Mol Struct（Theochem），2003，623：57－77.

［8］ BONDY J A，MURTY U S.Graph theory with applications［M］.Amsterdam：North－Holland，1976：1－264.

［9］ ZHANG L Z.The proof of Gutman's concerning extremal hexagonal chains［J］.J Sys Sci Math Scis，1998，18：460－465.

［10］ ZHANG L Z，TIAN F.Extremal hexagonal chains concerning largest eigenvalue［J］.Sciences in China：Series A，2001，44：1089－1097.

［11］ ZHANG L Z，TIAN F.Extremal catacondensed benzenoids［J］.J Math Chem，2003，34：111－122.

［12］ 唐保祥，任韓.4類圖完美匹配數(shù)目的解析式［J］.東北師大學(xué)報：自然科學(xué)版，2013，45（3）：20－24.

［13］ 馬海成，李生剛.圖的多項式與Hosoya指標［J］.東北師大學(xué)報：自然科學(xué)版，2013，45（4）：41－44.

［14］ HOU Y P.On acyclic systems with minimal Hosoya index［J］.Discrete Appl Math，2002，119：251－257.

［15］ YU A M，TIAN F.A kind of graphs with minimal Hosoya indices and maximal Merrifield－Simmons indices［J］.MATCH Commun Math Comput Chem，2006，55：103－118.

［16］ YE C F.Unicyclic graphs with the third smallest to sixth smallest Hosoya index［J］.MATCH Communications in Mathematical and in Computer Chemistry，2012，55：593－604.

Bicycle graphs with the second and third Hosoya index

LI Sha1，ZHUOMA Cuo1，WANG Wei2
（1.Department of Mathematics，Qinghai Normal University，Xining 810008，China；2.Tangshan No.49Middle School，Tangshan 063000，China）

Bicycle graphs are connected graphs with m＝n＋1，where mdenotes the number of edges and ndenotes the number of vertices.The Hosoya index of a graph G，denoted by Z（G），is defined as the total number of matchings（independent edge subsets），including the empty edge set，of a graph.On the basis of the existing conclusions，we characterize the bicycle graphs with the second and third Hosoya index with m－matching by adding edges and using known formulas.

Hosoya index；m－matching；bicycles

O 157.5 ［學(xué)科代碼］ 110·7470

A

（責(zé)任編輯：陶 理）

1000－1832（2014）02－0045－06

10.11672／dbsdzk2014－02－010

2013－12－16

國家自然科學(xué)基金資助項目（11161037；11101232）.

李莎（1988—），女，碩士研究生，主要從事圖論及其應(yīng)用研究.