四葉樹Hosoya指標(biāo)顯式公式及其序列

楊 利 民， 段 麗 燕， 王 天 明

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

?

四葉樹Hosoya指標(biāo)顯式公式及其序列

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

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

為研究四葉樹Hosoya指標(biāo)的規(guī)律，利用圖論的分支分析法，解決了四葉樹Hosoya指標(biāo)的顯式公式和序列．對于一般的t葉樹，仍然用同樣分支分析法，得到相應(yīng)的t葉樹Hosoya指標(biāo)的顯式公式和序列．發(fā)現(xiàn)了一族初值不一樣的Fibonacci序列，在科學(xué)上對組合數(shù)學(xué)和圖論提供了一定參考．

四葉樹；t葉樹；S(n)-因子；Fibonacci數(shù)；Hosoya指標(biāo)

0 引 言

四葉草又名幸運(yùn)草，是三葉草或苜蓿草的稀有變種．苜蓿草，是多年生草本植物，一般只有三片小葉子，葉形呈心形，葉心較深色的部分亦是心形．最為有趣也最特別的是，在十萬株苜蓿草中，可能只會發(fā)現(xiàn)一株是四葉草，因?yàn)楦怕适鞘f分之一，四葉草成為國際公認(rèn)的幸運(yùn)的象征．

由四葉草引出四葉樹，四片葉子、頂點(diǎn)數(shù)為n的樹叫做四葉樹．

Fibonacci數(shù)列，也稱為“兔子數(shù)列”，其數(shù)列為0，1，1，2，3，5，8，13，21，34，55，89，144，…，滿足遞歸關(guān)系式Fn=Fn-1+Fn-2，初值F0=0，F(xiàn)1=1[1-3]．

本文研究四葉樹Hosoya指標(biāo)的顯式公式和序列．

1 定義和引理

1.1 定 義

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

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

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

1.2 基本引理

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

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

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

2 主要結(jié)果

2.1 四葉樹Hosoya指標(biāo)的顯式公式

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

定理1 如圖1所示n個頂點(diǎn)的四葉樹，它的Hosoya指標(biāo)為

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

圖1 四葉樹圖G1

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

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

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)

根據(jù)引理3就有

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

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

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點(diǎn)完全圖為vn-5vn-4，K2作為兩個點(diǎn)的一個完全分支，則S(n)-因子個數(shù)如下：

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

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

據(jù)引理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，通項(xiàng)fn=fn-1+fn-2，這好像是Fibonacci序列，只是初值不一樣．下面將證明這個規(guī)律是對的．

證明 因?yàn)閒n=5Fn-4+Fn-5，所以fn-1=5Fn-5+Fn-6，fn-2=5Fn-6+Fn-7，又因?yàn)閒n-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指標(biāo)的顯式公式

定理2 如圖2所示n個頂點(diǎn)、t片樹葉的t葉樹，它的Hosoya指標(biāo)為

圖2 t葉樹

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

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

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)

根據(jù)引理3有

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

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點(diǎn)完全圖為vn-tvn-t-1，K2作為兩個點(diǎn)的一個完全分支，則S(n)-因子個數(shù)如下：

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

據(jù)引理1得到

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

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

據(jù)引理4得到

n≥t+1，t≥2

圖3 二葉樹

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

因?yàn)閒n=3Fn-2+Fn-3，所以fn-1=3Fn-3+Fn-4，fn-2=3Fn-4+Fn-5，又因?yàn)閒n-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，通項(xiàng)fn=fn-1+fn-2，這好像是Fibonacci序列，只是初值不一樣．下面將證明這個規(guī)律是對的．

因?yàn)閒n=4Fn-3+Fn-4，所以fn-1=4Fn-4+Fn-5，fn-2=4Fn-5+Fn-6，又因?yàn)閒n-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葉樹，發(fā)現(xiàn)它的Hosoya指標(biāo)序列呈現(xiàn)同樣規(guī)律．初值f0=t+1，f1=t+2，通項(xiàng)fn=fn-1+fn-2．

證明 因?yàn)閒n=(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，又因?yàn)閒n-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指標(biāo)為

令t=5，五葉樹的Hosoya指標(biāo)與t葉樹的呈同樣規(guī)律，初值f0=6，f1=7，通項(xiàng)fn=fn-1+fn-2．

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

圖5 五葉樹

3 結(jié) 語

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

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

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

[2] Comtet L. 高等組合學(xué):有限和無限展開的藝術(shù)[M]. 譚明術(shù),楊利民,等譯. 大連:大連理工大學(xué)出版社, 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] 楊利民,王天明. 色多項(xiàng)式的顯示公式[J]. 數(shù)學(xué)進(jìn)展, 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}-因子數(shù)的遞歸關(guān)系式[J]. 數(shù)學(xué)研究與評論, 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數(shù)的圖論應(yīng)用[J]. 大理學(xué)院學(xué)報, 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]計數(shù)公式[J]. 大連理工大學(xué)學(xué)報, 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] 楊利民. 理想子圖計數(shù)及其應(yīng)用[J]. 大連理工大學(xué)學(xué)報, 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)-因子計數(shù)理論及其應(yīng)用[D]. 大連:大連理工大學(xué), 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．

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

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

1000-8608(2016)06-0657-05

O157.5

A

10.7511/dllgxb201606015