楊 雨，惠志昊

(1.平頂山學(xué)院 國際教育交流學(xué)院,河南 平頂山 467000；2.平頂山學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院,河南 平頂山 467000)

如果樹T有一條路徑，使得T的每個(gè)頂點(diǎn)如果不在該路徑上，則一定與路徑上的某個(gè)頂點(diǎn)相鄰，則稱此樹為毛蟲樹；若T同時(shí)又是一棵BC樹，則稱T為一棵BC毛蟲樹，本文給出了BC毛蟲樹的概念，并用生成函數(shù)的方法來研究毛蟲BC樹的BC子樹數(shù)及它的特殊性質(zhì).

1 BC毛蟲樹的BC子樹數(shù)

定理1[3]n頂點(diǎn)星形BC樹K1,n-1有2n-1-n個(gè)BC子樹,比任一個(gè)n頂點(diǎn)BC樹所含的BC子樹都多；路徑BC樹Pn有(n-1)2/4個(gè)BC子樹, 比任一個(gè)n頂點(diǎn)BC樹所含的BC子樹都少.

定理2[3]星形BC樹K1,n-1中含頂點(diǎn)vi(i=1,2,…,n-1)的BC子樹的個(gè)數(shù)為2n-2-1.

圖1 直徑長度為l的BC毛蟲樹T′

證明用歸納假設(shè)證明,l=2時(shí)BC毛蟲樹即為星形BC樹，由定理1知其成立.

假定對(duì)于直徑為l-2的BC毛蟲樹T是成立的,

即:

(1)

直徑長度為l的BC毛蟲樹T′, 由BC毛蟲樹的特點(diǎn)可知,T′的BC子樹由四部分構(gòu)成.

1)T的所有BC子樹；

2)K1,nl/2-1的所有BC子樹；

3)T中的含頂點(diǎn)v的BC子樹與K1,nl/2-1的含頂點(diǎn)v的BC子樹相結(jié)合生成的BC子樹；

4)T的含頂點(diǎn)v的奇長路徑子樹與K1,nl/2-1的邊(v,w)合并形成的BC子樹, 經(jīng)計(jì)算此種類型的有(l-2)/2個(gè).

即η(T′)=η(T)+η(K1,nl/2-1)+η(T,v)×η(K1,nl/2-1,v)+(l-2)/2

由定理1和2可知:η(K1,nl/2-1)=2nl/2-1-nl/2，η(K1,nl/2-1,v)=2nl/2-2-1.

分析BC毛蟲樹的性質(zhì)，BC毛蟲樹T的含頂點(diǎn)v的BC子樹的個(gè)數(shù)為:

η(T,v)=(2nl/2-1-2-1)+2nl/2-1-3×(2nl/2-2-2-1)+2nl/2-1-3×2nl/2-2-3(2nl/2-3-2-1)+

結(jié)合式(1)可得:

(l-2)(l-4)/8+(2nl/2-1-nl/2)+(2nl/2-2-1)[(2nl/2-1-2-1)+

2nl/2-1-3×(2nl/2-2-2-1)+2nl/2-1-3×2nl/2-2-3(2nl/2-3-2-1)+

…+2nl/2-1-3×2nl/2-2-3×2nl/2-3-3…2n2-3(2n1-2-1)]+(l-2)/2=

定理得證.

2 BC毛蟲子樹數(shù)與直徑相關(guān)的一個(gè)性質(zhì)

定理4BC毛蟲樹T′同上, 葉子數(shù)按照區(qū)域進(jìn)行劃分，從左到右依次是X1,X2,…,Xl/2, 將前i部分的葉子全部移到X1之后, 所產(chǎn)生的BC毛蟲樹記為T″, 則直徑長度:

證明記由樹T′變換成T″后各部分的頂點(diǎn)數(shù)目為：

因此：

故:

(2)

式(2)小于等于0等價(jià)于:

即:

(3)

式(3)成立時(shí)η(T″)≤η(T′), 定理得證.

3 結(jié)束語

由于BC樹性質(zhì)比較特殊，國外有很多相關(guān)的研究[1，4-5]，同時(shí)毛蟲樹的相關(guān)研究也很多[7-8]，本文結(jié)合毛蟲樹和BC樹的特性，給出了BC毛蟲樹的概念，并對(duì)它的BC子樹數(shù)進(jìn)行了計(jì)算，同時(shí)給出了它的一個(gè)特殊性質(zhì).

參考文獻(xiàn):

[1]Harary F,Plummer M D.On the core of a graph[J].Proc London Math Soc,1967,17:305-314.

[2]Yan W,Yeh Y-N.Enumeration of subtrees of trees[J].Theoretical Computer Science,2006,369:256-268.

[3]楊雨，王德強(qiáng).兩類BC樹的BC樹的計(jì)數(shù)[J].大連海事大學(xué)學(xué)報(bào),2007,S1:62-65.

[4]Harary F,Prins G.The block-cutpoint-tree of a graph[J].Publ Math Debrecen,1966,13:103-107.

[5]Mkrtchyan V V.On trees with a maximum proper partial 0-1 coloring containing a maximum Matching[J]. Discrete Mathematics,2006,306: 456-459.

[6]Frank Harary, Allen J Schwenk.The number of caterpillars[J].Discrete Mathematics,1973,6(4):359-365.

[7]Slobodan K Simica, Enzo Maria Li Marzib, Belardob F.On the index of caterpillars[J].Discrete Mathematics,2008,308:324-330.

[8]卞瑞玲.毛蟲樹的性質(zhì)[J].山東大學(xué)學(xué)報(bào):理學(xué)版,2002,37(6):504-507.