洪雅麗

(晉江市南僑中學(xué)，福建 泉州 362200)

設(shè)T 是一棵樹，它的一個(gè)連通的導(dǎo)出子圖稱為一個(gè)子樹。子樹的計(jì)數(shù)問題被廣泛研究，Székely與Wang［1］考慮了二元樹的子樹的計(jì)數(shù)問題，得到了具有最多子樹的二元樹，Yan 與Yeh［2］給出了兩個(gè)線性算法計(jì)算樹的子樹的數(shù)目，Li 與Wang［3］進(jìn)一步分析研究了樹的子樹的計(jì)數(shù)問題。有關(guān)計(jì)算樹的子樹數(shù)目見相關(guān)文獻(xiàn)。［4－10］一個(gè)自然的問題是:考慮單圈圖的連通子圖的計(jì)數(shù)問題。袁新梅［11］給出了一個(gè)線性算法計(jì)算單圈圖的連通子圖的數(shù)目。在此基礎(chǔ)上，下文主要考慮連通單圈圖的連通子圖數(shù)目的極值問題。

1 基本術(shù)語與基本結(jié)果

為了描述方便，采用文［2，11］中的符號(hào)與基本術(shù)語。

除特別說明外，假設(shè)G = {V(G)，E(G);f，g}為一帶權(quán)單圈圖，其中V(G)= {v1，v2，…，vn}為頂點(diǎn)集合，E(G)= {e1，e2…，en}為邊集合，頂點(diǎn)的帶權(quán)函數(shù)為f:V(G)→R，邊的帶權(quán)函數(shù)為g:E(G)→R(其中R 表示非負(fù)實(shí)數(shù)集)。如果一帶權(quán)單圈圖G = {V(G)，E(G);f，g}滿足f = g =1 ，稱G 為一簡單單圈圖。對(duì)于一個(gè)給定的帶權(quán)單圈圖G的連通子圖G1，定義G1的權(quán)是G1里所有頂點(diǎn)與邊的權(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)包含一個(gè)固定頂點(diǎn)vi的連通子圖的權(quán)和為包含頂點(diǎn)vi的G 的連通子圖的權(quán)的和，用F(G;f，g;vi)表示。假設(shè)G 是一個(gè)n 個(gè)頂點(diǎn)的簡單單圈圖，用χ(G)= F(G;1，1)來表示G 的連通子圖的數(shù)目，G 的包含頂點(diǎn)vi的連通子圖的數(shù)目表示為χ(G;vi)= F(G;1，1;vi)。

令G 是n(n ＞1)個(gè)頂點(diǎn)并且含一片葉子u 的單圈圖。假設(shè)G 的懸掛邊為e = (u，v)。定義頂點(diǎn)個(gè)數(shù)為n－1 的一個(gè)帶權(quán)單圈圖G' = (V(G')，E(G');f＇，g＇)，其中V(G')= V(G) {u}，E(G')= E(G) {e}，

對(duì)于任意的vs∈V(G')，對(duì)于任意的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 對(duì)應(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］給出了計(jì)算連通的單圈圖的連通子圖的計(jì)數(shù)方法。

定理1.2［11］令G = (V(G)，E(G))是有n(n＞1)個(gè)頂點(diǎn)的簡單單圈圖，其中圈上有l(wèi) 個(gè)頂點(diǎn)，記為v1，v2，…，vl，Ti(i = 1，2，…l)為附在圈上且包含頂點(diǎn)vi樹，則:

2 主要結(jié)果

在下文中，除特別說明外，單圈圖均為簡單圖。

圖3 由單圈圖G'1 與樹T'1 構(gòu)造得到的單圈圖G1

圖4 通過G'1 的頂點(diǎn)u

附上r 個(gè)懸掛邊而得到的圖G2

定理2.1 令G1和G2是如上定義的單圈圖，當(dāng)r ≥1 即有:χ ( G2)= F ( G2;1，1 )，等號(hào)成立當(dāng)且僅當(dāng)T'1= K1，r且dT'1( )v = r。

證明:令fi:V ( G'1)→R ( i = 1，2 )為兩個(gè)如下

定義的函數(shù):

其中F (T'1;1，1;V )是T'1中包含頂點(diǎn)v 的子樹數(shù)。

由定理2.1 得:

即:

注意到:T'1是含有r +1 個(gè)頂點(diǎn)的樹，有2r+r－F(T'1;1，1)≥0 ，等號(hào)成立當(dāng)且僅當(dāng)T'1= K1，r。因?yàn)門'1至少有r 個(gè)含一個(gè)頂點(diǎn)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(等號(hào)成立當(dāng)且僅當(dāng)T'1= K1，r且dT'1(v)= r)。

因此有χ(G1)= F(G1;1，1)≤χ(G2)= F(G2;1，1)。

等號(hào)成立當(dāng)且僅當(dāng)T'1= K1，r且dT'1(v)= r。即定理得證。

圖5 由單圈圖G'1 與樹T'1構(gòu)造得到的單圈圖G1

圖6 通過G'1 的頂點(diǎn)u 附上一條長為r 的路而得到的圖G3

定理2.2 令G1和G3是如上定義的單圈圖，且r ≥1 。則χ(G1)= F(G1;1，1)≥χ(G3) =F(G3;1，1)。

當(dāng)且僅當(dāng)T'1= Pr+1且dT'1(v)= 1 時(shí)等號(hào)成立。

令Gd是沒有葉子圈長為d 的單圈圖，G 是由Gd將ki個(gè)懸掛邊附于頂點(diǎn)vi而生成的，i = 1，2，... ，d(見圖7)。單圈圖G*是在沒有葉子的單圈圖Gd的頂點(diǎn)vh上附于個(gè)懸掛邊而生成的(如圖8)。

圖7 由Gd 將ki(i = 1，2，... ，d)個(gè)懸掛邊附于vi 而生成的單圈圖G = Gd(k1，k2，…，kd)

圖8 在沒有葉子的單圈圖Gd 的頂點(diǎn)vh 上附于個(gè)懸掛邊而生成的單圈圖G*

定理2.3 令G 和G*為如上定義的兩個(gè)單圈圖，k1，k2，…，kd至少有兩個(gè)不為零。則F(G;1，1)＜F(G*;1，1)。

證明:根據(jù)定理2.2，有

以此類推，可得

又因?yàn)?k1+k2+…+kd＞0 ，d ≥3 ，

所以F(G*;1，1)－ F(G;1，1)＞0 。

因此有F(G;1，1)＜F(G*;1，1)。

從而定理成立。

令G0是沒有葉子的單圈圖，其圈上有d 個(gè)頂點(diǎn)，分別為v1，v2，…，vd。現(xiàn)將每個(gè)頂點(diǎn)vi(1 ≤i ≤d)上附于一條有ki個(gè)頂點(diǎn)的路，生成G＆(如圖9)。vh是G0的一個(gè)頂點(diǎn)，在G0的頂點(diǎn)vh上附于一條有個(gè)頂點(diǎn)的路，生成G#(如圖10)。

圖9 單圈圖G＆

圖10 單圈圖G#

定理2.4 令G＆和G#為如上定義的單圈圖，且至少有兩個(gè)ki不為零，則χ(G＆)= F(G＆;1，1)＜χ(G#)= F(G#;1，1)。

成立當(dāng)且僅當(dāng)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］. 南開大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011，44(3):23－27.