四葉樹Hosoya指標顯式公式及其序列

楊 利 民， 段 麗 燕， 王 天 明

( 1.大理大學 數學與計算機學院, 云南 大理 671003；2.大連理工大學 數學科學學院, 遼寧 大連 116024 )

?

四葉樹Hosoya指標顯式公式及其序列

楊 利 民*1， 段 麗 燕1， 王 天 明2

( 1.大理大學 數學與計算機學院, 云南 大理 671003；2.大連理工大學 數學科學學院, 遼寧 大連 116024 )

為研究四葉樹Hosoya指標的規律，利用圖論的分支分析法，解決了四葉樹Hosoya指標的顯式公式和序列．對于一般的t葉樹，仍然用同樣分支分析法，得到相應的t葉樹Hosoya指標的顯式公式和序列．發現了一族初值不一樣的Fibonacci序列，在科學上對組合數學和圖論提供了一定參考．

四葉樹；t葉樹；S(n)-因子；Fibonacci數；Hosoya指標

0 引 言

四葉草又名幸運草，是三葉草或苜蓿草的稀有變種．苜蓿草，是多年生草本植物，一般只有三片小葉子，葉形呈心形，葉心較深色的部分亦是心形．最為有趣也最特別的是，在十萬株苜蓿草中，可能只會發現一株是四葉草，因為概率是十萬分之一，四葉草成為國際公認的幸運的象征．

由四葉草引出四葉樹，四片葉子、頂點數為n的樹叫做四葉樹．

Fibonacci數列，也稱為“兔子數列”，其數列為0，1，1，2，3，5，8，13，21，34，55，89，144，…，滿足遞歸關系式Fn=Fn-1+Fn-2，初值F0=0，F1=1[1-3]．

本文研究四葉樹Hosoya指標的顯式公式和序列．

1 定義和引理

1.1 定 義

定義1[4]設S(n)={Ki：1≤i≤n}(n≥1)，Ki是i個頂點的完全圖．假設M是G的子圖并且M的每一個分支都同構于S(n)={Ki：1≤i≤n}(n≥1)中的某一個元素，則稱M為圖G的一個S(n)={Ki：1≤i≤n}-子圖．假設M是圖G的生成子圖，則稱M為圖G的一個S(n)={Ki：1≤i≤n}-因子．

令A(G)是圖G的所有S(n)={Ki：1≤i≤n}-因子個數．圖G是簡單圖，不包括多重邊和環．

定義2 圖G的所有k-匹配個數稱作Hosoya指標．Hosoya指標用Z(G)表示．

1.2 基本引理

引理2 如果G和H的交為空圖，即G∩H=?，則A(G∪H)=A(G)·A(H)．

引理3[5]假設Pn是長為n的路，且有n+1個頂點，則Pn的S(n)={Ki：1≤i≤n}-因子個數是A(Pn)=Fn+2(n≥1)，其中Fn+2是第n+2個Fibonacci數．

引理4[6]假設圖G的頂點數為n并且無K3子圖，則Hosoya指標Z(G)等于圖G的所有S(n)={Ki：1≤i≤n}-因子個數：Z(G)=A(G)．

2 主要結果

2.1 四葉樹Hosoya指標的顯式公式

下面給出四葉樹的Hosoya指標的顯式公式并證明[7-8]．

定理1 如圖1所示n個頂點的四葉樹，它的Hosoya指標為

Z(G1)=5Fn-4+Fn-5；n≥5

圖1 四葉樹圖G1

證明 利用圖的分支分析法[9-10]，對給定點Vn-4進行分析，過Vn-4頂點的一切完全圖只有K1和5個K2，無Ki(3≤i≤n)，討論分3種情況：

情況一 過Vn-4點完全圖為K1，即為點Vn-4，Vn-4作為一個完全分支，則S(n)-因子個數如下：

A(G1-V(K1))=

A(Vn-3∪Vn-2∪Vn-1∪Vn∪Pn-6)=

A(Vn-3)A(Vn-2)A(Vn-1)A(Vn)A(Pn-6)=

1×1×1×1×A(Pn-6)=A(Pn-6)

根據引理3就有

A(G1-V(K1))=Fn-4

情況二 過Vn-4點完全圖為vn-4vn-3，vn-4vn-2，vn-4vn-1和vn-4vn，這4個完全圖K2是對稱的，K2作為兩個點的完全分支，則S(n)-因子個數如下：

4A(G1-V(K2))=

4A(Vn-2∪Vn-1∪Vn∪Pn-6)=

4A(Vn-2)A(Vn-1)A(Vn)A(Pn-6)=

4×1×1×1×A(Pn-6)=4Fn-4

情況三 過Vn-4點完全圖為vn-5vn-4，K2作為兩個點的一個完全分支，則S(n)-因子個數如下：

“我說我快要活不成了。”我失去了與他斗嘴的樂趣和力氣，我的眼前一陣陣發黑，手腕處那種汩汩的聲音讓我覺得害怕。

A(G1-V(K2))=

A(Vn-3∪Vn-2∪Vn-1∪Vn∪Pn-7)=

A(Vn-3)A(Vn-2)A(Vn-1)A(Vn)A(Pn-7)=

1×1×1×1×A(Pn-7)=A(Pn-7)=Fn-5

據引理1得到

A(G1-V(K1))+4A(G1-V(K2))+

A(G1-V(K2))=

Fn-4+4Fn-4+Fn-5=5Fn-4+Fn-5

Z(G1)=A(G1)=5Fn-4+Fn-5；n≥5

有趣的是，四葉樹序列的初值f0=5，f1=6，通項fn=fn-1+fn-2，這好像是Fibonacci序列，只是初值不一樣．下面將證明這個規律是對的．

證明 因為fn=5Fn-4+Fn-5，所以fn-1=5Fn-5+Fn-6，fn-2=5Fn-6+Fn-7，又因為fn-1+fn-2=5(Fn-5+Fn-6)+(Fn-6+Fn-7)=5Fn-4+Fn-5，則fn=fn-1+fn-2．

□

Tab.1 Some initial values of Hosoya index of four

nZ(T4n)nZ(T4n)55928661045711117381712118

5，6，11，17，28，45，73，118，191，309，500，809，1 309，2 118，3 427，5 545，8 972，14 517，23 489，38 006，61 495，99 501，160 996，260 497，421 493，681 990，1 103 483，…

2.2 t葉樹Hosoya指標的顯式公式

定理2 如圖2所示n個頂點、t片樹葉的t葉樹，它的Hosoya指標為

圖2 t葉樹

證明 利用圖的分支分析法，對給定點Vn-t進行分析，過Vn-t頂點的一切完全圖只有K1和(t+1)個K2，無Ki(3≤i≤n)，討論分3種情況：

情況一 過Vn-t點完全圖為K1，即為點Vn-t，Vn-t作為一個完全分支，則S(n)-因子個數如下：

A(Vn-t+1∪Vn-t+2∪…∪Vn∪Pn-t-2)=

A(Vn-t+1)A(Vn-t+2)…A(Vn)A(Pn-t-2)=

1×1×…×1×A(Pn-t-2)=A(Pn-t-2)

根據引理3有

情況二 過Vn-t點完全圖為vn-tvn-t+1，vn-tvn-t+2，…，vn-tvn，這t個完全圖K2是對稱的，K2作為兩個點的完全分支，則S(n)-因子個數如下：

tA(Vn-t+2∪…∪Vn∪Pn-t-2)=

tA(Vn-t+2)…A(Vn)A(Pn-t-2)=

t×1×…×1×A(Pn-t-2)=tA(Pn-t-2)=tFn-t

情況三 過Vn-t點完全圖為vn-tvn-t-1，K2作為兩個點的一個完全分支，則S(n)-因子個數如下：

A(Vn-t+1∪Vn-t+2∪…∪Vn∪Pn-t-3)=

A(Vn-t+1)A(Vn-t+2)…A(Vn)A(Pn-t-3)=

1×1×…×1×A(Pn-t-3)=

A(Pn-t-3)=Fn-t-1

據引理1得到

Fn-t+tFn-t+Fn-t-1=

(t+1)Fn-t+Fn-t-1

據引理4得到

n≥t+1，t≥2

圖3 二葉樹

同樣有趣的是，二葉樹序列的初值f0=3，f1=4，通項fn=fn-1+fn-2，這好像是Fibonacci序列，只是初值不一樣．下面將證明這個規律是對的．

因為fn=3Fn-2+Fn-3，所以fn-1=3Fn-3+Fn-4，fn-2=3Fn-4+Fn-5，又因為fn-1+fn-2=3(Fn-3+Fn-4)+(Fn-4+Fn-5)=3Fn-2+Fn-3，則fn=fn-1+fn-2．

□

3，4，7，11，18，29，47，76，123，199，322，521，843，1 364，2 207，3 571，5 778，9 349，…

圖4 三葉樹

三葉樹序列的初值f0=4，f1=5，通項fn=fn-1+fn-2，這好像是Fibonacci序列，只是初值不一樣．下面將證明這個規律是對的．

因為fn=4Fn-3+Fn-4，所以fn-1=4Fn-4+Fn-5，fn-2=4Fn-5+Fn-6，又因為fn-1+fn-2=4(Fn-4+Fn-5)+(Fn-5+Fn-6)=4Fn-3+Fn-4，則fn=fn-1+fn-2．

□

4，5，9，14，23，37，60，97，157，254，411，665，1 076，1 741，2 817，4 558，7 375，11 933，…

對于一般的t葉樹，發現它的Hosoya指標序列呈現同樣規律．初值f0=t+1，f1=t+2，通項fn=fn-1+fn-2．

證明 因為fn=(t+1)Fn-t+Fn-t-1，所以fn-1=(t+1)Fn-t-1+Fn-t-2，fn-2=(t+1)Fn-t-2+Fn-t-3，又因為fn-1+fn-2=(t+1)(Fn-t-1+Fn-t-2)+(Fn-t-2+Fn-t-3)=(t+1)Fn-t+Fn-t-1，則fn=fn-1+fn-2．

□

t+1，t+2，2t+3，3t+5，5t+8，8t+13，13t+21，21t+34，34t+55，…

推論3 如圖5所示的五葉樹的Hosoya指標為

令t=5，五葉樹的Hosoya指標與t葉樹的呈同樣規律，初值f0=6，f1=7，通項fn=fn-1+fn-2．

6，7，13，20，33，53，86，139，225，364，589，953，1 542，2 495，…

圖5 五葉樹

3 結 語

本文解決了四葉樹Hosoya指標的顯式公式和序列，并將它推廣到一般的t葉樹上，有趣的是，發現了一族初值不一樣的Fibonacci序列，在科學上對組合數學和圖論提供了一定參考價值．

[1] 王天明. 近代組合學[M]. 大連:大連理工大學出版社, 2008.

WANG Tian-ming. Modern Combinatorics [M]. Dalian:Dalian University of Technology Press, 2008. (in Chinese)

[2] Comtet L. 高等組合學:有限和無限展開的藝術[M]. 譚明術,楊利民,等譯. 大連:大連理工大學出版社, 1991.

Comtet L. Advanced Combinatorics: The Art of Finite and Infinite Unfolding [M]. TAN Ming-shu, YANG Li-min,etal., trans. Dalian: Dalian University of Technology Press, 1991. (in Chinese)

[3] Harary F, Palmer E M. Graphical Enumeration [M]. New York: Academic Press Inc., 1973.

[4] 楊利民,王天明. 色多項式的顯示公式[J]. 數學進展, 2006, 35(1):55-66.

YANG Li-min, WANG Tian-ming. The explicit formula of the chromatic polynomial [J]. Advances in Mathematics, 2006, 35(1):55-66. (in Chinese)

[5] 楊利民.S(n)={Ki:1≤i≤n}-因子數的遞歸關系式[J]. 數學研究與評論, 1991, 11(1):78.

YANG Li-min. A recurrence relation for the number of factors ofS(n)={Ki:1≤i≤n} [J]. Journal of Mathematical Research and Exposition, 1991, 11(1):78. (in Chinese)

[6] 楊利民,楊正亮. Fibonacci數的圖論應用[J]. 大理學院學報, 2011, 10(4):12-16.

YANG Li-min, YANG Zheng-liang. Graphic applications on Fibonacci numbers [J]. Journal of Dali University, 2011, 10(4):12-16. (in Chinese)

[7] 楊利民,王天明,年四洪. 完全i部圖N[(X1,X2,…,Xi),k]計數公式[J]. 大連理工大學學報, 2007, 47(6):925-930.

YANG Li-min, WANG Tian-ming, NIAN Si-hong. Counting formulas ofN[(X1,X2,…,Xi),k] of completei-partite graphs [J]. Journal of Dalian University of Technology, 2007, 47(6):925-930. (in Chinese)

[8] 楊利民. 理想子圖計數及其應用[J]. 大連理工大學學報, 1989, 29(5):605-609.

YANG Li-min. Enumeration of ideal subgraphs and its applications [J]. Journal of Dalian University of Technology, 1989, 29(5):605-609. (in Chinese)

[9] YANG Li-min, WANG Tian-ming. The representing formula ofN(G,k) [J]. International Journal of Analyzing Methods of Combinatorial Biology in Mathematics, 2008, 1(1):1-26.

[10] 楊利民.S(n)-因子計數理論及其應用[D]. 大連:大連理工大學, 2006.

YANG Li-min. Counting theory ofS(n)-factors and applications [D]. Dalian: Dalian University of Technology, 2006. (in Chinese)

Explicit formula of Hosoya index of four leaf tree with its sequence

YANG Li-min*1, DUAN Li-yan1, WANG Tian-ming2

( 1.School of Mathematics and Computer, Dali University, Dali 671003, China；2.School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China )

To research into the laws of Hosoya index for four leaf tree, by means of analyzing method of components in graph theory, the explicit formula of Hosoya index of four leaf tree and its sequence are solved. For generaltleaf tree, by adopting the same method, the explicit formula of Hosoya index of correspondingtleaf tree and its sequence are obtained. A family of Fibonacci sequences whose initial values are not the same are discovered, which provides some scientific

for combinatorics and graph theory.

four leaf tree;tleaf tree;S(n)-factor; Fibonacci number; Hosoya index

2016-04-10；

2016-09-25．

大理大學高層次人才科研啟動基金資助項目(KY0719203410).

楊利民*(1965-)，男，博士，教授，E-mail:yanglm65@aliyun.com.

1000-8608(2016)06-0657-05

O157.5

A

10.7511/dllgxb201606015