塊為三角形的簡(jiǎn)單圖的最小Hosoya指數(shù)

張深林

（福建江夏學(xué)院數(shù)理教研部，福建福州，350108）

塊為三角形的簡(jiǎn)單圖的最小Hosoya指數(shù)

張深林

（福建江夏學(xué)院數(shù)理教研部，福建福州，350108）

一個(gè)圖G的Hosoya指數(shù)是指圖G中所有匹配的計(jì)數(shù)。用ζ表示塊為三角形的簡(jiǎn)單連通圖的集合，Gr∈ζ是ζ中塊數(shù)為r的圖，Wr∈ζ是ζ中直徑為2，塊數(shù)為r的圖。利用邊收縮法和數(shù)學(xué)歸納法可證Wr是Gr∈ζ中Hosoya指數(shù)最小的圖。該結(jié)論在連通分支數(shù)大于1的圖中也是成立的。

匹配；Hosoya指數(shù)；塊

一、引言

Hosoya指數(shù)由日本化學(xué)家Hosoya[1]于1971年首次提出，它被看作是研究分子的物理特性和化學(xué)特性的一個(gè)重要指標(biāo)，與分子的熔點(diǎn)、沸點(diǎn)、熵[2][3]都有密切關(guān)系。匹配是組合圖論中的重要分支，Hosoya指出了圖的匹配數(shù)作為拓?fù)渲笖?shù)在化學(xué)上的作用，并以此來描述飽和碳?xì)浠衔锏臒崃W(xué)性質(zhì)。因此，確定一個(gè)圖的最大或最小Hosoya指數(shù)是非常有意義的。

二、預(yù)備知識(shí)與主要定義

除特別說明外，本文假設(shè)G=(V，E)是簡(jiǎn)單連通圖。設(shè)e=(u，v)是G的一條邊（方便起見，有時(shí)也記為e=uv），G-u-v表示G中刪去頂點(diǎn)u與v得到的頂點(diǎn)導(dǎo)出子圖，G-e表示G中刪去邊e得到的G的邊導(dǎo)出子圖。圖G的一個(gè)邊子集M稱為一個(gè)匹配（matching），如果G中的每個(gè)頂點(diǎn)與M中的至多一條邊相關(guān)聯(lián)；M稱為G的一個(gè)完美匹配（perfect matching），如果G中的每個(gè)頂點(diǎn)恰好與M中的一條邊相關(guān)聯(lián)。記m(G，j)為G中含j條邊的匹配的數(shù)目，習(xí)慣上總假定G的零匹配為1，即m(G， 0)=1，于是m(G，1)為圖G的邊數(shù)；而當(dāng)n為偶數(shù)時(shí)，m(G,)則為G的完美匹配的數(shù)目。用Z(G)表示圖G中所有匹配的數(shù)目，即Z(G)=m(G，0)+m(G，1)+…m(G，），圖G中所有匹配的數(shù)目也稱為Hosoya指數(shù)。

圖G=(V，E)的頂點(diǎn)v稱為割點(diǎn)，如果E可劃分為兩個(gè)非空子集E1和E2，使得G[E1]和G[E2]恰有一個(gè)公共頂點(diǎn)v。沒有割點(diǎn)的連通圖稱為塊。若圖G的子圖B是塊，且G中沒有真包含B的子圖也是塊，則稱B是G的塊[4]。

用ζ表示塊為三角形的簡(jiǎn)單連通圖的集合，Gr∈ζ是ζ中塊數(shù)為r的圖，Wr∈ζ是ζ中直徑為2，塊數(shù)為r的圖，在一些地方也被稱為風(fēng)車圖[4][5]（windmill graph）。圖1給出了r=1，2，3，4的所有Gr∈ζ圖。其中的a，b，c，e為r≤4的Wr。

圖1

在Gr∈ζ的塊中，我們稱恰有2個(gè)2度點(diǎn)的三角形為第一類三角形，數(shù)目為s1；恰有1個(gè)2度點(diǎn)的三角形為第二類三角形，數(shù)目為s2；有0個(gè)2度點(diǎn)的三角形為第三類三角形，數(shù)目為s3。顯然

設(shè)頂點(diǎn)c∈V(Gr)，則以c為頂點(diǎn)的塊三角形稱為c關(guān)聯(lián)的三角形。

三、 有關(guān)的引理

下面介紹與本文有關(guān)的引理。

引理3．1[6]設(shè)G是一個(gè)圖，e=(u，v)是G的一條邊，則

其中G-uv和G-u-v分別表示G中刪去邊e及刪去頂點(diǎn)u與v的邊導(dǎo)出子圖與頂點(diǎn)導(dǎo)出子圖。引理3．2[6]設(shè)v是圖G的一個(gè)頂點(diǎn)，NG(v)表示v的鄰點(diǎn)集，則

引理3．3[6]設(shè)圖G有分支G1，G2，…，Gk，則

引理3．4[6]Cn表示有n個(gè)頂點(diǎn)的圈，Pn表示有n個(gè)頂點(diǎn)的路，F(xiàn)n表示第n個(gè)斐波那契數(shù)（Fibonacci number），則

引理3．5[7]設(shè)Gr∈ζ是滿足s3=0的簡(jiǎn)單圖，從Gr圖中的每個(gè)三角形都刪去一個(gè)2度的頂點(diǎn)后得到的圖記為Tr+1，且d1，d2，…，dr+1是圖Tr+1的頂點(diǎn)的度序列，則

引理3．6[7]設(shè)G是有n個(gè)頂點(diǎn)的簡(jiǎn)單圖，a是G的一個(gè)頂點(diǎn)。構(gòu)造一個(gè)n+2個(gè)頂點(diǎn)的新圖G'，使得G'的頂點(diǎn)集為V(G)=V(G')∪{x，y}，邊集為E(G')=E(G)∪{ax，ay，xy}，其中x，y∈/V(G)，則

四、主要定理與結(jié)論

引理4．1 設(shè)Wr∈ζ是如上定義的簡(jiǎn)單圖，則

證明 因?yàn)閃r∈ζ也是滿足s3=0的圖，由引理3．5可知，Wr所對(duì)應(yīng)的度序列為d1=d2=…=dr=1，dr+1=r，從而Z(Wr)=2r(r+1)．

圖2

引理4．2 用Gr1(+)Gr2表示用一條邊連接Gr1和Gr2的某一頂點(diǎn)所成的圖，Gr1，Gr2∈ζ，用Gr1+r2表示把Gr1(+)Gr2中唯一不在三角形塊中的邊收縮成連接Gr1，Gr2的公共頂點(diǎn)的圖（如圖2所示），則

證明 顯然，Gr1+r2的匹配都是Gr1(+)Gr2的匹配，反之則不然。

定理4．1 假設(shè)Gr∈ζ，r∈N+，則

等號(hào)成立當(dāng)且僅當(dāng)Gr=Wr

證明 設(shè)Gr∈ζ，對(duì)塊數(shù)r做數(shù)學(xué)歸納法。

（1）當(dāng)r=1，2時(shí)，容易驗(yàn)證命題成立。現(xiàn)在假設(shè)命題對(duì)于r≤m成立，現(xiàn)考慮當(dāng)r=m+1時(shí)。

（2）當(dāng)r=m+1時(shí)，若Gr中的塊都是第一類三角形，由引理4．1，命題成立。

若Gr中的塊不全是第一類三角形，則必存在第二類或第三類三角形。任意選取圖Gr的某一個(gè)非第一類三角形，考慮它的非2度頂點(diǎn)所聯(lián)接的三角形是否第一類三角形，重復(fù)這個(gè)過程，直到找到這個(gè)第一類三角形為止（因?yàn)閴K數(shù)是有限的，所以尋找第一類三角形的過程也是有限的）。接著，考慮該第一類三角形的非2度頂點(diǎn)所關(guān)聯(lián)的三角形，是否除了一個(gè)非第一類三角形外，其余都是第一類三角形，如果不是，則重復(fù)以上步驟，直到找到為止。則Gr中必存在一點(diǎn)c，除了關(guān)聯(lián)一個(gè)非第一類三角形外，其余關(guān)聯(lián)的三角形都是第一類三角形。設(shè)該點(diǎn)上關(guān)聯(lián)p(1≤p≤r－2)個(gè)第一類三角形，分別是△1，△2，…，△p，記Gr-p=Gr－△1－△2－…－△p。由引理3．6及歸納假設(shè)可得，

即命題對(duì)于r=m+1也成立。

綜上所述，命題對(duì)于一切正整數(shù)都成立。

定理4．2 設(shè)1≤r1≤r2，則

證明

應(yīng)用上述引理和定理，可以得到更一般的結(jié)果。

[1] Hosoya H．Topolpgical index,a newly proposed quantity charaterizing the topological nature of structural isomers of saturated hydrocarbons[M]．Bull Chem Soc Jpn,1971,44:2332-2339．

[2] Gutmani,Polanskyor．Mathematical concepts in chemistry[M]．Berlin:Spring,1986．

[3] Merrifield R．E．,Simmons H．E．,Topological methods in chemistry[M]．New York:Wiley,1989．

[4] 張先迪,李正良,圖論及其應(yīng)用[M]．北京:高等教育出版社,2005:277．

[5] Gallian,J．A．"Dynamic Survey DS6:Graph Labeling．"Electronic J．Combinatorics[J]．DS6,1-58,Jan．3,2007．

[6] Godsil C．D．,Algebraic Combinatorics[M]．New York． Chapman and Hall,1993．

[7] 晏衛(wèi)根,葉永南．一類運(yùn)算圖的匹配數(shù)[J]．中國(guó)科學(xué),2006,(9):1014-1022．

（責(zé)任編輯 王魏紅）

Smallest Hosoya Index in Triangle-Block Graphs

ZHANG Shen-lin
(Department of Mathematics and Physics,Fujian Jiangxia University,Fuzhou,350108,China)

The Hosoya index of a graph G is defined as the number of matching in the graph G. Denoteζas the set of simple connected graph with triangle blocks. Wr∈ζis a graph consisting of r blocks. Wr∈ζis a graph consisting of r blocks and with diameter of 2.By using the method of edge contraction and mathematical induction, the paper proves that Wris the graph with the minimum Hosoya index in Gr∈ζ.This statement is also valid for a graph with the number of connected component greater than 1.

matching;Hosoya index;block

0157.5

A

2095-2082（2015）06-0112-04

2015-06-24

張深林（1979—），女，福建閩清人，福建江夏學(xué)院數(shù)理教研部教師。