劉雪姿， 梁小影, 卜月華

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

含有2個(gè)最大度點(diǎn)的樹的極大獨(dú)立集個(gè)數(shù)*

劉雪姿， 梁小影, 卜月華

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

研究了限制條件下圖的極大獨(dú)立集的計(jì)數(shù)問題.運(yùn)用數(shù)學(xué)歸納法，給出了含有2個(gè)最大度點(diǎn)的樹的極大獨(dú)立集個(gè)數(shù)的最大值,同時(shí)刻畫了取得最大值時(shí)的樹.

極大獨(dú)立集;樹;最大度;計(jì)數(shù)

0 引 言

給定圖G,V(G)的一個(gè)子集S稱為獨(dú)立集,若S中的任何2個(gè)頂點(diǎn)在V(G)中都不相鄰;如果一個(gè)獨(dú)立集不真包含于其他任一獨(dú)立集,就稱該獨(dú)立集為極大獨(dú)立集;用mi(G)表示G中極大獨(dú)立集的個(gè)數(shù).

圖的極大獨(dú)立集的計(jì)數(shù)問題對(duì)于算法設(shè)計(jì)有重要的意義.Moon和Moser[1]解決了n階圖G中mi(G)的最大值,以及何時(shí)達(dá)到最大值的問題;隨后,學(xué)者們針對(duì)這個(gè)問題,對(duì)許多特殊圖進(jìn)行了研究[2-7].筆者研究了含有2個(gè)最大度點(diǎn)的樹的極大獨(dú)立集的個(gè)數(shù)問題,得到了最大值,并刻畫了極圖的情況.

1 引 理

引理1[4]對(duì)G中的任一頂點(diǎn)x,有

(1)mi(G)≤mi(G-x)+mi(G-N[x]);

(2)如果x是與y相鄰的葉子點(diǎn),那么mi(G)=mi(G-N[x])+mi(G-N[y]).

引理2[4]對(duì)任何2個(gè)不相交的圖G和H,mi(G∪H)=mi(G)mi(H).

明顯地,有引理3成立.

引理3設(shè)G是一個(gè)n階的圖,如果G含有2個(gè)頂點(diǎn)x和y,其中d(x)=d(y)=1,N(x)=N(y),那么mi(G)=mi(G-x).

引理4[6]如果T是一棵n階的樹,那么mi(G)≤t1(n),等號(hào)成立當(dāng)且僅當(dāng)

引理5[8]如果F是一個(gè)n(n≥1)階的森林,那么mi(F)≤f(n),等號(hào)成立當(dāng)且僅當(dāng)

圖1 樹B(l;i1,j1;i2,j2)

引理6[9]如果T是一棵n階的樹,TT1(n),那么mi(T)≤t2(n),并且等式成立當(dāng)且僅當(dāng)T?T2(n).

B(l;i1,j1;i2,j2)(如圖1所示)表示一棵樹:給定一條有l(wèi)個(gè)頂點(diǎn)的路P,在路P的一個(gè)端點(diǎn)u1下掛有i1條長為2的路和j1條長為1的路，另一個(gè)端點(diǎn)u2下掛有i2條長為2的路和j2條長為1的路.當(dāng)j1=0且j2=0時(shí),把B(l;i1,j1;i2,j2)簡記為B(l;i1;i2).

利用引理1易得引理7和引理8.

引理7若l≥2,i1≥1,j1≥1,則

mi(B(l;i1+1,j1-1;i2,j2))≥mi(B(l+1;i1,j1;i2,j2)),

等號(hào)成立當(dāng)且僅當(dāng)l=2,i2=0,j2=0.

引理8若l≥1,d≥1,則

mi(B(4l+1;d+1;d+1))gt;mi(B(4l+5;d;d));

mi(B(4l-1;d+1;d+1))gt;mi(B(4l+3;d;d)).

2 主要結(jié)果

定理1若T是一棵含有2個(gè)最大度點(diǎn)的樹,則

等號(hào)成立當(dāng)且僅當(dāng)T?T(n).其中

證明 當(dāng)n=4k+2和n=4k+4時(shí),由引理4知,定理1顯然成立,所以只需證明n=4k+1和n=4k+3的情況.對(duì)n進(jìn)行歸納.由于n=4k+3與n=4k+1的證明思路完全類似,因此只證明n=4k+1的情況.

當(dāng)n≤12時(shí),定理1顯然成立.令n≥13,假設(shè)當(dāng)n′lt;n時(shí)結(jié)論成立.令T為一棵階為n,且含有2個(gè)最大度點(diǎn)的樹.為方便起見,令T為平面中的有根樹且至少含有2層,w為只有2層子孫的頂點(diǎn),y為w的一個(gè)兒子,x為y的兒子.顯然,x是T中的一個(gè)葉子點(diǎn).令n=4k+1.

若d(y)≥3,則

情形1d(w)≠Δ

如果w有1個(gè)葉子兒子,由歸納假設(shè)可得

假設(shè)T′?T1(n-2d(w)+1),那么T′為圖2中的一棵樹.不失一般性, 假設(shè)a,b,c,d,e,f,g中的一個(gè)是w的父親.顯然

mi(T-N[y])=r2(d(w)-2)(rn-2d(w)+1-2+1)=rn-5+r2(d(w)-2).

圖2 樹T′ 的可能情形

bw∈E(T);cw∈E(T);dw∈E(T);ew∈E(T);fw∈E(T);gw∈E(T).

若T′T(n-2d(w)+1),由歸納假設(shè)及引理6有

不失一般性,假設(shè)只含有2層子孫的頂點(diǎn)是T中的最大度點(diǎn).

令另外一個(gè)最大度點(diǎn)為w′,可以假設(shè)w′的不包含w的子孫分支恰好有2層.令P為T中唯一的w-w′路.

(1)P中有1個(gè)內(nèi)點(diǎn)的度至少為3

令z為P中一個(gè)度至少為3的內(nèi)點(diǎn).由于T中包含2個(gè)最大度點(diǎn),因此d(z)≠Δ.令T以z為根(如圖3所示),用A表示T-z中不包含w和w′的分支的點(diǎn)集.由情形1知,A中的任何一個(gè)點(diǎn)至多含有1層子孫.因此,z與A中的任何一個(gè)點(diǎn)的距離至多為2.分別用T(w)和T(w′)表示T-z中包含w和w′的分支.令|T(w)|=n1, |T(w′)|=n2.

圖3 以z 為根的樹T

假設(shè)z沒有葉子兒子,那么n1+n2=n-2d(z)+3.令a為A中的一個(gè)葉子點(diǎn),由歸納假設(shè)及引理1有

若d(z)≥4,即z中除了x的子孫形成一個(gè)匹配.令a為A-x中的一個(gè)葉子點(diǎn),由歸納假設(shè)及引理1有

①zw?E(T)

由引理1及引理4可得

因?yàn)閚≥13,d(w)=d(w′),所以n1lt;n-6.若w有1個(gè)葉子兒子,則由|T(w)|=n1≡1(mod 2)可得w至少含有2個(gè)葉子兒子.由引理1及引理4得

此時(shí)T?B(l;i1,j1;i2,j2),其中l(wèi)+2i1+2i2+j1+j2=4k+1,i1+j1=i2+j2.

①l-2lt;j1+j2

由引理7得,mi(T)≤mi(B(2;i1+j1,0;i2+(l-2-j1),j1+j2-(l-2))).

②l-2≥j1+j2

由引理7得,mi(T)≤mi(B(l-(j1+j2);i1+j1;i2+j2)).

由于l+2i1+2i2+j1+j2=4k+1,i1+j1=i2+j2,所以

(l-2)-(j1+j2)=4k-1-4(i1+j1)=4[k-(i1+j1)]-1≥0.

令k-(i1+j1)=t,t≥1,則l-(j1+j2)=4t+1,t≥1.由引理8可得

等號(hào)成立當(dāng)且僅當(dāng)T?B(5;k-1;k-1).定理1得證.

[1]Moon J W,Moser L.On cliques in graphs[J].Israel J Math,1965,3(1):23-28.

[2]Füredi Z.The number of maximal independent sets in connected graphs[J].J Graph Theory,1987,11(4):463-470.

[3]Griggs J R,Grinstead C M,Guichard D R.The number of maximal independent sets in a connected graph[J].Discrete Math,1988,68(2/3):211-220.

[4]Hujter M,Tuza Z.The number of maximal independent sets in triangle-free graphs[J].SIAM J Discrete Math,1993,6(2):284-288.

[5]Meir A,Moon J W.On maximal independent sets of nodes in trees[J].J Graph Theory,1988,12(2):265-283.

[6]Sagan B E.A note on independent sets in trees[J].SIAM J Discrete Math,1988,1(1):105-108.

[7]Wilf H S.The number of maximal independent sets in a tree[J].SIAM J Algebraic Discrete Methods,1986,7(1):125-130.

[8]Jou M J.The number of maximal independent sets in graphs[D].Taibei:National Center University,1991.

[9]Jou M J,Lina J J.Trees with the second largest number of maximal independent sets[J].Discrete Math,2009,309(13):4469-4474.

(責(zé)任編輯 陶立方)

Countingthemaximalindependentsetsintreeswithtwomaximumdegreevertices

LIU Xuezi, LIANG Xiaoying, BU Yuehua

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

It was studied the number of maximal independent sets in trees with constrained conditions. Using the mathematical induction, the largest value ofmi(T) for trees with two maximum degree vertices was obtained. Extremal trees achieving these values were also characterized.

maximal independent sets; trees; maximum degree; counting

1001-5051(2010)01-0045-05

2009-05-07

國家自然科學(xué)基金資助項(xiàng)目(10701065);浙江省自然科學(xué)基金資助項(xiàng)目(Y607467)

劉雪姿(1986-),女,浙江溫州人,碩士研究生.研究方向:運(yùn)籌學(xué)與控制論.

O157.5

A