具有最多與最少連通子圖的單圈圖

洪雅麗

(晉江市南僑中學，福建 泉州 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ù)目的極值問題。

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

為了描述方便，采用文［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樹，則:

2 主要結(jié)果

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

圖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.