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

張深林

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

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

張深林

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

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

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

一、引言

Hosoya指數(shù)由日本化學家Hosoya[1]于1971年首次提出，它被看作是研究分子的物理特性和化學特性的一個重要指標，與分子的熔點、沸點、熵[2][3]都有密切關系。匹配是組合圖論中的重要分支，Hosoya指出了圖的匹配數(shù)作為拓撲指數(shù)在化學上的作用，并以此來描述飽和碳氫化合物的熱力學性質(zhì)。因此，確定一個圖的最大或最小Hosoya指數(shù)是非常有意義的。

二、預備知識與主要定義

除特別說明外，本文假設G=(V，E)是簡單連通圖。設e=(u，v)是G的一條邊（方便起見，有時也記為e=uv），G-u-v表示G中刪去頂點u與v得到的頂點導出子圖，G-e表示G中刪去邊e得到的G的邊導出子圖。圖G的一個邊子集M稱為一個匹配（matching），如果G中的每個頂點與M中的至多一條邊相關聯(lián)；M稱為G的一個完美匹配（perfect matching），如果G中的每個頂點恰好與M中的一條邊相關聯(lián)。記m(G，j)為G中含j條邊的匹配的數(shù)目，習慣上總假定G的零匹配為1，即m(G， 0)=1，于是m(G，1)為圖G的邊數(shù)；而當n為偶數(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)的頂點v稱為割點，如果E可劃分為兩個非空子集E1和E2，使得G[E1]和G[E2]恰有一個公共頂點v。沒有割點的連通圖稱為塊。若圖G的子圖B是塊，且G中沒有真包含B的子圖也是塊，則稱B是G的塊[4]。

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

圖1

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

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

三、 有關的引理

下面介紹與本文有關的引理。

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

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

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

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

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

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

四、主要定理與結論

引理4．1 設Wr∈ζ是如上定義的簡單圖，則

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

圖2

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

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

定理4．1 假設Gr∈ζ，r∈N+，則

等號成立當且僅當Gr=Wr

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

（1）當r=1，2時，容易驗證命題成立。現(xiàn)在假設命題對于r≤m成立，現(xiàn)考慮當r=m+1時。

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

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

即命題對于r=m+1也成立。

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

定理4．2 設1≤r1≤r2，則

證明

應用上述引理和定理，可以得到更一般的結果。

[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] 張先迪,李正良,圖論及其應用[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)根,葉永南．一類運算圖的匹配數(shù)[J]．中國科學,2006,(9):1014-1022．

（責任編輯 王魏紅）

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—），女，福建閩清人，福建江夏學院數(shù)理教研部教師。