具有極小 Hosoya指數(shù)的含圈共軛圖

孫志榮

(安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院,安徽合肥230039)

0 引 言

圖G(V(G),E(G))為n階一般無向共軛圖,即圖 G含有完備匹配.其頂點集為V(G),邊集為 E(G).圖G的匹配是指G中的邊子集N,在N中任意兩條不相同的邊均無公共點.m(G,k)表示G中恰含k條邊的匹配個數(shù)并且規(guī)定m(G,0)=1.圖的 Hosoya指數(shù) (或簡稱 z-指數(shù))指的是圖 G的所有匹配之和,記為z(G),即z(G)=(G,k),顯然,當(dāng) 時,m(G,k)=0.Hosoya指數(shù)是由Hosoya于1971年提出來的,作為組合數(shù)學(xué)中的一個重要的拓撲指標,它與分子的總π-電子能[1]、沸點[2]等化學(xué)物理特性有密切關(guān)系.

近年來,國內(nèi)外已有很多關(guān)于 Hosoya指數(shù)的研究成果.例如在 n個頂點的樹中,路 Pn和星圖Sn分別具有最大和最小的Hosoya指數(shù)[3,4].固定圈長單圈圖且具有最小Hosoya指數(shù)的極值圖[5]和給定懸掛點個數(shù)的單圈圖集合中具有最小 Hosoya指數(shù)的極值圖[6]已被刻畫出.歐建平刻畫了單圈圖的最大、次大的Hosoya指數(shù)及其極值圖[7]和沒有完備匹配的樹當(dāng)中 Hosoya指數(shù)最大的極值圖[8].n階樹中具有 m-匹配的第三小 Hosoya指數(shù)是 2m-4(10n-15m+11)[9].n個頂點的樹中具有 m-匹配的第四小、第五小的Hosoya指數(shù)分別為2m-4(12n-18m+4)和2m-4(12n-18m+5)[10].n個頂點的雙圈圖中具有最大Hosoya指數(shù)的圖由4階圈和n-2階圈共用一條邊得到[11],具有最小 Hosoya指數(shù)的圖由含一條公共邊的兩個三角形并在公共邊的一個頂點加 n-4個懸掛點得到[12].含 n個點的無圈圖的第二小 Hosoya指數(shù)為2n-3[13].一些給定特殊條件的圖類的 Hosoya指數(shù)也被刻畫出,例如直徑是3和4的 n階樹的 Hosoya指數(shù)的最大值[14]和雙星樹的Merrifield-Simmons和 Hosoya指數(shù)序列[15]等.對于無圈圖和單圈圖,積和式和Hosoya指數(shù)有著一定的聯(lián)系,利用積和式可以求出一些特殊單圈圖的極小 Hosoya指數(shù)[16].此外,Hosoya指數(shù)與圖的能量[17]和常見的六角鏈化學(xué)分子的某些特性[18]也有聯(lián)系.但是對于共軛分子圖的Hosoya指數(shù)的研究并不是很多,本文則刻畫了共軛分子的含圈圖中具有最小、次小 Hosoya指數(shù)的極值圖.

1 定義與符號

下面先介紹一些定義,其它未加說明的圖論術(shù)語和符號請參考文獻[2].G有完備匹配,因此|V(G)|=n為偶數(shù),|E(G)|=m(n≤m≤-2).dG(u)表示頂點 u在圖G中的度.φn,m表示含有n(n≥8)個頂點 m(n≤m≤-2)條邊的共軛圖集合.M(G)表示圖G的完備匹配,則|M(G)|=Q(G)=E(G)-M(G)表示G去掉M(G)中的邊剩下的邊集合.用 G＊表示圖 G去掉完備匹配的邊集,再去掉孤立點剩下的子圖,即由邊集Q(G)導(dǎo)出的子圖,因此|E(G)＊|=m-對于圖 G的任何一個k-匹配Ω,都可以分成兩部分Ω=R∪S,其中 R∈E(G＊),S∈M(G),即 G的任一k-匹配,都可以從 G＊中選擇 i(0≤i≤k)條不相鄰的邊,再從 M(G)中選擇 k-i條邊,且保證 M(G)中的 k-i條邊和G＊中的i條邊互不相鄰.

2 引 理

引理1 a,b為正整數(shù),若 a+b=n,則 ab≥n-1.

證明 a+b=n,所以a=n-b.

即ab＞n-1.

綜上所訴,ab≥n-1.證畢

引理3 若 (X,Y)是一個二部圖 G的二部劃分,|E(G)|=p,且滿足|X|≥2,|Y|≥2.則這個二部圖至少有 p-2個2-匹配.

證明 G是二部圖,所以 G沒有奇圈.

如果二部圖 G可以分成邊不交的兩部分G1和 G2,即 G是不連通的,設(shè)|E(G1)|=a,|E(G2)|=b,則 a+b=p.按照從 G1中選擇一條邊,從 G2中選擇一條邊的方法組成 2-匹配.根據(jù)引理1,則至少可以選出 ab≥p-1個2-匹配.

若G是連通的,即不能分成邊不交的兩部分,且二部劃分|X|≥2,|Y|≥2,則在 G中存在邊uν,滿足 d(u) ≥2,d(ν) ≥2.設(shè) d(u) =k1,d(ν)=k2.由于 G不含奇圈,除了邊 uν之外,與 u關(guān)聯(lián)的k1-1條邊和與ν關(guān)聯(lián)的k2-1條邊無公共頂點.設(shè)與u關(guān)聯(lián)的邊集為E1,與ν關(guān)聯(lián)的邊集為E2,則|E1-uν|=k1-1,|E2-uν|=k2-1.首先邊 uν可與 p-1- (k1-1) - (k2-1)條邊組成 p+1-k1-k2個 2-匹配.按照從 E1-uν和 E2-uν中各取一邊的選法至少有 (k1-1)(k2-1) ≥k1+k2-3個2-匹配,所以圖 G至少有p+1-k1-k2+k1+k2-3=p-2個2-匹配. 證畢

3 結(jié) 論

定理4 若 G∈φn,m(n≤m≤n+n-2),G≠Hn,m,則 z(G)＞z(Hn,m). Hn,m如圖1所示,由-i-2 1個三角形和一條懸掛邊及i個 P2的端點粘合在同一點組成.

圖2

圖1 Hn,m

證明 如果對任意 G∈φn,m和都滿足 m(Hn,m,k)≤m(G,k),那么,就可以證明(H,k) ≤ m(G,k),即z(H) ≤z(G).n,mn,m

定理5 若 G∈φn,m(n≤m≤n+-3),G≠Hn,m,In,m,則 z (G) ＞z (In,m). In,m是在 Hn-1,m-2的一個三角形的兩個2度頂點上各加一個懸掛點得到,如圖3所示.

圖3 In,m

圖4

證明 In,m如圖3所示,如圖4所示.先考慮In,m的Hosoya指數(shù),z(In,m)= m(In,m, k).中有m個1-匹配,有 m--3個2-匹配,沒有3-匹配,且中的每個i-匹配(i=0,1,2)與M (In,m)中的2i條邊相鄰.即:

G∈φn,m,G≠Hn,m,In,m,把 G分兩種情況討論:

情況1 若 G＊是非連通圖,則 G＊至少包含兩部分邊非空的子圖 G1和 G2.設(shè)|E(G1)|=a,|E(G2)|=b,則a+b=.假設(shè) a≥b,由引理1可知 ab≥-1,若從 G1中選一條邊,從 G2中選一條邊,則至少可構(gòu)成2-匹配至少m-n-1個,且每個2-匹配至多關(guān)聯(lián)4條 M(G)中的邊.所以:

情況2 若 G＊是連通圖,G≠Hn,m,In,m,則 G＊是非星圖,且|V (G＊) |≥4,則在 G＊中存在割邊集B把G＊分割成邊非空的兩個子圖 G1和 G2,即 EG＊(G1,G2)=B.由割邊集B生成的子圖可視為一個二部分圖,設(shè)|B|=p. |E(G1)|=a,|E(G2)|=b,則a+b=-p.首先按照從 G1中選擇一條邊,從 G2中選擇一條邊的方法至少可組成ab≥p-1個2-匹配.

子情況2.1 若割邊集B只含一條邊,即 p=1,則 G＊至少可組成 ab≥-2個2-匹配.

子情況2.2 若由割邊集B生成的子圖是星圖,則 G1和 G2中至少有一邊可與星圖的 p-2條邊組成p-2個2-匹配.G＊至少含-3個2-匹配.

子情況2.3 若邊集B生成的子圖不是星圖,由引理3可知割邊集B本身至少含p-2個2-匹配,則G＊至少含-p-1+p-2=-3個2-匹配.

在以上三種情況中,由于每個2-匹配最多與M(G)中的4條邊相鄰,則

[1] Hosoya H.Topological index,a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons[J].Bull Chem Soc Jpn,1971,44(09)：2332-2339

[2] Gutman I,Polansky OE.Mathematical Concepts in Organic Chemistry[M].Berlin：Springer,1986：1-70

[3] Chan O,Gutman I,Lam TK,et al.Algebraic connections between topological indices[J].J Chem Inform Comp Sci,1998,38(01)：62-65

[4] Gutman I.Acyclic systems with extremal Huckelπ-electron energy[J].Theor Chim Acta,1977：78-87

[5] Qu JP.On extremal unicyclic molecular graphs with prescribed girth and minimal Hosoya index[J].J Math Chem,2007,42(03)：423-432

[6] Hua HB.Hosoya index of unicyclic graphs with prescribed pendent vertices[J].J Math Chem,2008,43(02)：831-844

[7] Qu JP.On extremal unicyclic molecular graphs with maximal Hosoya index[J].Discr Appl Math,2009,157(02)：391-397

[8] Qu JP.Maximal Hosoya index and extremal acyclic molecular graphs without perfect matching[J].Appl Math Lett,2006,19(07)：652-656

[9] Ye C,Wang JF,Zhao H.Trees with m-matchings and the third minimal Hosoya index[J].Comm Math Comp Chem/MATCH,2006,56(03)：593-604

[10] Ye CF,Wang JF.Trees with m-matchings and the fourth and fifth minimal Hosoya index[J].Comp Math Appl,2008,56(02)：387-399

[11] Deng HY.The largest Hosoya index of(n,n+1)-graphs[J].Comp Math Appl,2008,56(10)：2499-2506

[12] Deng HY.The smallest Hosoya index in(n,n+1)-graphs[J].J Math Chem,2008,43(01)：119-133

[13] Hou YP.On acyclic systems with minimal Hosoya index[J].Discr Appl Math,2002,119(03)：251-257

[14] 曹慶信,陳祥恩,劉信生.直徑是3和4的n階樹的Hosoya指數(shù)的最大值[J].甘肅聯(lián)合大學(xué)學(xué)報,2009,23(03)：31-34

[15] 肖正明.雙星樹的Merrifield-Simmons和 Hosoya指數(shù)序列 [J].湖南城市學(xué)院學(xué)報,2007,16(04)：50-52

[16] Hua HB.Minimizing a class of unicyclic graphs by means of Hosoya index[J].Math Comp Modell,2008,48(5-6)：940-948

[17] Heuberger C,Wagner SG.Chemical trees minimizing energy and Hosoya index[J].J Math Chem,2009,46(01)：214-230

[18] Shiu WC.Extremal Hosoya index and merrifield Simmons index of hexagonal spiders[J].Discr Appl Math,2008,156(15)：2978-2985