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

李 莎，卓瑪措，王 微

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

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

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

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

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

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

引理4［14］令Pn和Sn表示含有n個(gè)點(diǎn)的路和星，則對(duì)于含有n個(gè)點(diǎn)的所有樹T，我們有

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

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

因?yàn)镚1的每一個(gè)匹配也是G的匹配，從而引理5顯然成立.

引理6 令T是一個(gè)樹，α′（T）＝k（k≥1），并且T?lK1∪kK2（l≥0），則Z（T）≥5·2k－2等號(hào)成立當(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）等號(hào)成立當(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）等號(hào)成立當(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）等號(hào)成立當(dāng)且僅當(dāng)G∈｛U3（n，m），U7（8，4），U10（10，5）｝.

引理10 令T是一個(gè)樹，α′（T）＝m（m≥1），并且T?｛（n－2m）K1∪mK2，P4∪（m－2）K2∪（n－2m）K1｝，則Z（T）≥3×2m－1等號(hào)成立當(dāng)且僅當(dāng)T?｛T3，T5｝（見圖2）.若還有其他含有m個(gè)匹配的圖，以圖2中9個(gè)圖中的一個(gè)作為子圖，則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）等號(hào)成立當(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）等號(hào)成立當(dāng)且僅當(dāng)G∈｛B2（n，m），B7（8，4）｝.

證明 令G∈B（n，m）（n≥2m，m≥4），并且M是G的一個(gè)m－匹配，我們總能從G的圈中找出一條邊uv，使得uv?M，則G－uv是一個(gè)連通單圈圖.此外，α′（G－uv）＝m（因?yàn)镚－uv是G的一個(gè)子圖，由引理5有α′（G－uv）≤α′（G）＝m，注意到M是G－uv的一個(gè)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直接計(jì)算，得：

因此，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）等號(hào)成立當(dāng)且僅當(dāng)G－uv?U2（n，m）.注意到G－｛u，v｝有（m－2）－匹配，所以有Z（G－｛uv｝）≥2m－2等號(hào)成立當(dāng)且僅當(dāng)G－｛u，v｝?（n－2m＋1）K1∪（m－2）K2，易看出uv中必有一個(gè)點(diǎn)是U2（n，m）中的一個(gè)（n－m）度點(diǎn)，另一個(gè)是U2（n，m）中的一個(gè)3度點(diǎn)，這種情況是不可能的.由引理6，若Z（G－｛u，v｝）≥5·2m－4等號(hào)成立當(dāng)且僅當(dāng)G－｛u，v｝?（m－4）K2∪P4∪（n－2m＋2）K1.由引理2，

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

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

并且

所以

等號(hào)成立當(dāng)且僅當(dāng)u，v的兩個(gè)點(diǎn)在U7（8，4）中為3度點(diǎn).因此等號(hào)成立當(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），

等號(hào)成立當(dāng)且僅當(dāng)G－uv?U10（10，5），且G－｛u，v｝?3 K2.此時(shí)G不可能是m＝5時(shí)，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）等號(hào)成立當(dāng)且僅當(dāng)G－uv?U3（n，m）.注意到G－｛u，v｝有（m－2）－匹配，所以有Z（G－｛u，v｝）≥2m－2等號(hào)成立當(dāng)且僅當(dāng)G－｛u，v｝?（n－2m＋2）K1∪（m－2）K2.從而

等號(hào)成立當(dāng)且僅當(dāng)G－uv?U3（n，m），而且G－｛u，v｝?（m－2）K2∪（n－2m＋2）K1.此時(shí)，uv的一個(gè)端點(diǎn)必是U3（n，m）的一個(gè)（n－m）度點(diǎn)，另一個(gè)是鄰接于一個(gè)3度點(diǎn)的2度點(diǎn)，此時(shí)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），則

等號(hào)成立當(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的一個(gè)m－匹配，我們總能從G的一個(gè)圈中選出一條邊uv，使得uv?M，則G－uv是一個(gè)n度點(diǎn)的連通單圈圖，并且α′（G－uv）＝m（因?yàn)镚－uv是G的一個(gè)子圖，由引理5我們有α′（G－uv）≤α′（G）＝m，注意到M是G－uv的一個(gè)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，有

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

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

ⅱ.若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等號(hào)成立當(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）度點(diǎn)為點(diǎn)，從而若u，v中有點(diǎn)是（n－m）度點(diǎn)，則G－｛u，v｝中不可能有T5.若v中沒有點(diǎn)是（n－m）度點(diǎn)，則G－uv?U2（n，m），從而矛盾.如果G－｛u，v｝?T3，那么

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

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

當(dāng)m＝4，n＝8，則Z（G－uv）≥Z（U7（8，4）），此時(shí)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－匹配.

等號(hào)成立當(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）｝，此時(shí)Z（G－uv）≥2m－4（10n－15m＋15）等號(hào)成立當(dāng)且僅當(dāng)G∈｛U4（n，m），U5（n，m）｝，并且G－｛u，v｝中有（m－2）－匹配，Z（G－｛u，v｝）≥2m－2等號(hào)成立當(dāng)且僅當(dāng)G－｛u，v）?（m－2）K2∪（n－2m＋2）K1.

等號(hào)成立當(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.此時(shí)易得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é)報(bào)：自然科學(xué)版，2013，45（3）：20－24.

［13］ 馬海成，李生剛.圖的多項(xiàng)式與Hosoya指標(biāo)［J］.東北師大學(xué)報(bào)：自然科學(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

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

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