洪雅麗
(晉江市南僑中學,福建 泉州 362200)
設(shè)T 是一棵樹,它的一個連通的導(dǎo)出子圖稱為一個子樹。子樹的計數(shù)問題被廣泛研究,Székely與Wang[1]考慮了二元樹的子樹的計數(shù)問題,得到了具有最多子樹的二元樹,Yan 與Yeh[2]給出了兩個線性算法計算樹的子樹的數(shù)目,Li 與Wang[3]進一步分析研究了樹的子樹的計數(shù)問題。有關(guān)計算樹的子樹數(shù)目見相關(guān)文獻。[4-10]一個自然的問題是:考慮單圈圖的連通子圖的計數(shù)問題。袁新梅[11]給出了一個線性算法計算單圈圖的連通子圖的數(shù)目。在此基礎(chǔ)上,下文主要考慮連通單圈圖的連通子圖數(shù)目的極值問題。
為了描述方便,采用文[2,11]中的符號與基本術(shù)語。
除特別說明外,假設(shè)G = {V(G),E(G);f,g}為一帶權(quán)單圈圖,其中V(G)= {v1,v2,…,vn}為頂點集合,E(G)= {e1,e2…,en}為邊集合,頂點的帶權(quán)函數(shù)為f:V(G)→R,邊的帶權(quán)函數(shù)為g:E(G)→R(其中R 表示非負實數(shù)集)。如果一帶權(quán)單圈圖G = {V(G),E(G);f,g}滿足f = g =1 ,稱G 為一簡單單圈圖。對于一個給定的帶權(quán)單圈圖G的連通子圖G1,定義G1的權(quán)是G1里所有頂點與邊的權(quán)的乘積,用ω(G1)來表示。帶權(quán)單圈圖G= (V(G),E(G);f,g)的所有連通子圖的權(quán)之和用F(G;f,g)表示。定義帶權(quán)單圈圖G = (V(G),E(G);f,g)包含一個固定頂點vi的連通子圖的權(quán)和為包含頂點vi的G 的連通子圖的權(quán)的和,用F(G;f,g;vi)表示。假設(shè)G 是一個n 個頂點的簡單單圈圖,用χ(G)= F(G;1,1)來表示G 的連通子圖的數(shù)目,G 的包含頂點vi的連通子圖的數(shù)目表示為χ(G;vi)= F(G;1,1;vi)。
令G 是n(n >1)個頂點并且含一片葉子u 的單圈圖。假設(shè)G 的懸掛邊為e = (u,v)。定義頂點個數(shù)為n-1 的一個帶權(quán)單圈圖G' = (V(G'),E(G');f',g'),其中V(G')= V(G) {u},E(G')= E(G) {e},
對于任意的vs∈V(G'),對于任意的e ∈E(G'),有g(shù)'(e)= g(e)。圖1 與圖2 說明了由G構(gòu)造G' 的過程。
圖1 權(quán)單圈圖G = (V(G),E(G);f,g)及其一懸掛邊e = (u,v)
圖2 對應(yīng)的權(quán)單圈圖G' = (V(G'),E(G');f',g')
定理1.1[11]根據(jù)上面的記法,有F(G;f,g)= F(G';f',g')+ f(u)。
利用此結(jié)果,袁[11]給出了計算連通的單圈圖的連通子圖的計數(shù)方法。
定理1.2[11]令G = (V(G),E(G))是有n(n>1)個頂點的簡單單圈圖,其中圈上有l(wèi) 個頂點,記為v1,v2,…,vl,Ti(i = 1,2,…l)為附在圈上且包含頂點vi樹,則:
在下文中,除特別說明外,單圈圖均為簡單圖。
圖3 由單圈圖G'1 與樹T'1 構(gòu)造得到的單圈圖G1
圖4 通過G'1 的頂點u
附上r 個懸掛邊而得到的圖G2
定理2.1 令G1和G2是如上定義的單圈圖,當r ≥1 即有:χ ( G2)= F ( G2;1,1 ),等號成立當且僅當T'1= K1,r且dT'1( )v = r。
證明:令fi:V ( G'1)→R ( i = 1,2 )為兩個如下
定義的函數(shù):
其中F (T'1;1,1;V )是T'1中包含頂點v 的子樹數(shù)。
由定理2.1 得:
即:
注意到:T'1是含有r +1 個頂點的樹,有2r+r-F(T'1;1,1)≥0 ,等號成立當且僅當T'1= K1,r。因為T'1至少有r 個含一個頂點vi(vi≠v)的子樹,則F(T'1;1,1)≥F(T'1;1,1;v)+ r。
注 意 到,F(xiàn)(K1,r;1,1) = 2r+ r,即:0 ≤F(K1,r;1,1)- F(T'1;1,1)≤2r-F(T'1;1,1;v)。
所以2r-F(T'1;1,1;v)≥0(等號成立當且僅當T'1= K1,r且dT'1(v)= r)。
因此有χ(G1)= F(G1;1,1)≤χ(G2)= F(G2;1,1)。
等號成立當且僅當T'1= K1,r且dT'1(v)= r。即定理得證。
圖5 由單圈圖G'1 與樹T'1構(gòu)造得到的單圈圖G1
圖6 通過G'1 的頂點u 附上一條長為r 的路而得到的圖G3
定理2.2 令G1和G3是如上定義的單圈圖,且r ≥1 。則χ(G1)= F(G1;1,1)≥χ(G3) =F(G3;1,1)。
當且僅當T'1= Pr+1且dT'1(v)= 1 時等號成立。
令Gd是沒有葉子圈長為d 的單圈圖,G 是由Gd將ki個懸掛邊附于頂點vi而生成的,i = 1,2,... ,d(見圖7)。單圈圖G*是在沒有葉子的單圈圖Gd的頂點vh上附于個懸掛邊而生成的(如圖8)。
圖7 由Gd 將ki(i = 1,2,... ,d)個懸掛邊附于vi 而生成的單圈圖G = Gd(k1,k2,…,kd)
圖8 在沒有葉子的單圈圖Gd 的頂點vh 上附于個懸掛邊而生成的單圈圖G*
定理2.3 令G 和G*為如上定義的兩個單圈圖,k1,k2,…,kd至少有兩個不為零。則F(G;1,1)<F(G*;1,1)。
證明:根據(jù)定理2.2,有
以此類推,可得
又因為2k1+k2+…+kd>0 ,d ≥3 ,
所以F(G*;1,1)- F(G;1,1)>0 。
因此有F(G;1,1)<F(G*;1,1)。
從而定理成立。
令G0是沒有葉子的單圈圖,其圈上有d 個頂點,分別為v1,v2,…,vd?,F(xiàn)將每個頂點vi(1 ≤i ≤d)上附于一條有ki個頂點的路,生成G&(如圖9)。vh是G0的一個頂點,在G0的頂點vh上附于一條有個頂點的路,生成G#(如圖10)。
圖9 單圈圖G&
圖10 單圈圖G#
定理2.4 令G&和G#為如上定義的單圈圖,且至少有兩個ki不為零,則χ(G&)= F(G&;1,1)<χ(G#)= F(G#;1,1)。
成立當且僅當G = G*。
[1]Székely LA,Wang H.On subtrees of trees[J].Adv.Appl.Math,2005,34(1):138-155.
[2]Yan WG,Yeh YN.Enumeration of subtrees of trees[J].Theoretical Computer Science,2006,369:256-268.
[3]Li SC,Wang SJ.Further Analysis on the Total Number of Subtrees of Trees[J].The Electronic Journal of Combinatorics,2012,(19):48.
[4]Székely LA,Wang H.Binary trees with the largest number of subtrees with at least one leaf[J].Congr.Numer.,2005,177:147-169.
[5]Wang H.Some results on trees[M].Ph.D.Thesis,Department of Mathematics,University of South Carolina,2005.
[6] Wagon S.A bound on the chronmatic number of graphs without certain induced subgraphs[J].J.Combin.Theory.Ser.B,1980,29:245-246.
[7]Walter JR.Representations of chordal graphs as subtrees of a tree[J].J.Graph Theory,1978,(2):265-267.
[8]Wang DL,Kleitman DJ.On the existence of n-connected graphs with prescribed degrees(n ≥2)[J].Networks,1973,(3):225-239.
[9]Bondy J.A,Murty U.S.R.Graph Theory with Applications[M].Macmillan Press LTD,1976.
[10]袁新梅. 單圈圖的連通子圖的數(shù)目[J]. 南開大學學報(自然科學版),2011,44(3):23-27.