控制數固定樹的鄰接譜半徑

陳 萍, 何常香

(上海理工大學理學院,上海 200093)

控制數固定樹的鄰接譜半徑

陳 萍, 何常香

(上海理工大學理學院,上海 200093)

研究定義在Γm,γ(m≥2γ+1,γ≥2)中的樹,借助奪鄰、嫁接等移邊定理,通過構造一種新的移邊運算Operation I,給出了Γm,γ中前兩大譜半徑,并證明了T(m,r),S(m,r)是達到前兩大譜半徑的圖.

圖;樹;鄰接譜半徑;控制數

僅考慮簡單連通圖,設G=(V,E)是一個以V={v1,v2,…,vm}為頂點的集合,E為邊集合的簡單連通圖.G的鄰接矩陣A(G)為一個m×m矩陣,設A(G)=(aij),其中當vi與vj相鄰時,aij=1；當vi與vj不相鄰時,aij=0.G的特征多項式定義為Φ(G,x)=det(x Im-A(G)),簡記為Φ(G).由于G是一個簡單圖,A(G)是一個實對稱(0,1)-矩陣,其所有特征值都為實數.不失一般性,可以假設

且稱λk(G)為G的第k大特征值.特別地,λ1(G)稱為G的譜半徑,記為λ(G). ____令_di=d(vi)表示G中點vi的度數,Pm表示有m個點的路,G中度數為1的點叫懸掛點.懸掛路是指內部頂點度數為2,端點度數為1的路.對于圖G=(V,E),用NG(u)或N(u)來表示G中與u相鄰的點的集合.稱U?V為G的一個控制集,若U∪N(U)=V,其中N(U)=∪u∈UN(u).控制數是指G中所有控制集的最小基數,用γ(G)表示.如果G沒有孤立點,則γ(G)≤m/2.恰有γ個點的控制集叫做γ-set.在本文中,用Γm,γ(m≥2γ+1,γ≥2)表示階數為m,控制數為γ的樹的集合.

文獻[1]曾提出,在給定的一類圖的集合G中,尋找譜半徑的上界與下界,并刻畫達到了上界或下界的圖.此問題提出后,掀起了對特殊圖類的譜半徑的研究的熱潮.比如樹,文獻[2]研究了懸掛點數固定的樹的譜半徑,所有階數為m,有k個懸掛點的樹中,Tm,k是唯一具有最大譜的樹,其中Tm,k是在星圖K1,k的每個懸掛點處引出一條長度幾乎相等的懸掛路所得的圖.文獻[3]研究了割點數固定的樹的譜半徑,證明了在所有階數為m,有k條割邊的連通圖中,是唯一具有最大譜的圖.其中是在完全圖Km-k的某個頂點上引出k條懸掛邊而得到的圖,文獻[4]研究了割邊數固定的圖的譜半徑,證明了在所有階數m,有k條割邊的連通圖中,是唯一具有最大譜的圖,其中是在完全圖Km-k的某個頂點上引出k條懸掛邊而得到的圖.更多關于樹的譜半徑的研究見文獻[5-7].筆者主要研究在控制數固定的條件下樹的譜半徑問題,并得到如下結論:

定理1 設T∈Γm,γ(m≥2γ+1,γ≥2), T(m,γ),S(m,γ)如圖1所示,則

a.λ(T(m,γ))＞λ(S(m,γ))；

b.對所有T?{T(m,γ),S(m,γ)}均有λ(S(m,γ))＞λ(T)成立；

c.λ(T(m,γ))是方程的最大根

d.λ(S(m,γ))是方程的最大根

圖1 T(n，γ)和S(n，γ)Fig.1 T(n，γ)and S(n，γ)

1 預備知識

引理1[8-9]設G是階數為m的連通二部圖(m≥2),v∈V(G).Gk,l是通過在v點處加兩條長度分別為k、l的懸掛路所得到的圖.若k≥l≥1,則λ(Gk,l)＞λ(Gk+1,l-1).

引理2[2]設u,v是樹T的頂點,v1,v2,…, vs(1≤s≤d(v))和u1,u2,…,ut(1≤t≤d(u))分別屬于NT(v){u},NT(u){v}.記

則max{λ(Tu),λ(Tv)}＞λ(T).

引理3[10]設v為圖G的一個懸掛點,u是v的鄰點,則Φ(G)=xΦ(G-v)-Φ(G-u-v).

引理4[8]設G是一連通圖,G′是G的連通真子圖.則對任意x≥λ(G)有Φ(G′,x)＞Φ(G,x).

記Δ(G)為G的最大度.由引理4,有λ(G)≥ λ(K1,Δ(G)∪(m-Δ(G)-1)K1)=.

2 定理1的證明

首先,給出如下兩個圖的控制數的關系:

引理5 設G是一個連通圖,u∈V(G),H是由G通過u點加一條懸掛路uu1u2u3得到的圖, W是由G通過u點加一條懸掛邊uu1和一條懸掛路uu2u3得到的圖(見圖2).則

圖2 H和WFig.2 H and W

證明

a.設γ(G)=γ,γ(H)=γ′,M是G的一個γ-set.不難看出,M∪{u2}是H的一個控制集,于是γ′≤γ+1.由于u3是一個懸掛點,H中一定存在一個包含u2的γ′-set,記為M′,于是M′{u2}是G的一個控制集,則有γ′-1≥γ.

綜上,γ′=γ+1.

b.不難看出,W中任意γ個頂點都不能控制W,因此γ(W)≥γ(G)+1=γ(H).

為了方便起見,把圖G中度數不小于3的點的個數用r(G)來表示.設u是T中度數不小于3的點,uu1…u3l+i(l≥0,0≤i≤2)是T的一條懸掛路.如果T′是將T中懸掛路uu1…u3l+i用l條P3,l條懸掛邊和一條懸掛路Pi+1代替得到的新圖,就說T′是由T經Operation I得到的(見圖3).

為了說明γ(T)和γ(T′)的大小關系,設H= T-ui+1-…-ui+3l,不難看出T是由H通過在ui點加一條長為3l的懸掛路P3l+1所得的圖.若記T″是由H經u點加l條懸掛路P4所得的圖.根據引理5,γ(T)=γ(T″)=γ(H)+l且γ(T′)≥γ(T″).于是有γ(T′)≥γ(T).

圖3 Operation I(從T到T′)Fig.3 Operation I(from T to T′)

綜上及引理1,得到以下結論:

引理6 如果T′是由樹T經Operation I得到的樹,則

定義1 設u,v是樹T度數不小于3的頂點. uuiui1…uili(i=1,…,s,其中s=d(u)-1)和vvjvj1…vjlj(j=1,…,t,其中t=d(v)-1)是分別從u,v發(fā)出的兩條懸掛路,且按以下規(guī)則對鄰點排序:

a.包含ui+1的懸掛路的長度大于等于包含ui的懸掛路的長度,i=1,…,s-1；

b.包含vj+1的懸掛路的長度大于等于包含vj的懸掛路的長度,j=1,…,t-1.

定義

引理7 設T∈Γm,γ,T∈Γm,γv是T中度數不小于3的頂點,P是從u到v的路.若從u、v出發(fā)的除P外的其它所有路都是長不超過2的懸掛路,則

證明

a.先證γ(Tu(1))≥γ.設s、t分別為T中從u出發(fā)的長為1,2的懸掛路的條數,s′、t′分別為從v出發(fā)的長為1,2的懸掛路的條數.分別證明:

情形1 t=0

由于u是T中度數不小于3的頂點,故有s≥2,此時u屬于T的任一γ-set.因此γ(Tu(1))≥γ；

情形2 t≠0

若s′≥2時,u從v處所奪邊包含有懸掛邊,所以γ(Tu(1))≥γ.當s′≤1時,則t′≥1,u從v處所奪邊都是長為2的懸掛路,此時γ(Tu(1))=γ.綜上有,γ(Tu(1))≥γ.同理可證,γ(Tv(1))≥γ.

b.從定義1,容易得出r(Tu(1))=r(Tv(1))=r (T)-1；

c.由引理2,有max{λ(Tu(1)),λ(Tv(1))}＞λ(T).

引理8 設T∈Γm,γ,如果r(T)≥3,則一定存在一棵樹T′滿足

證明 設u、v是T中距離最遠的兩個度數不小于3的點,P是從u到v的路.從u、v出發(fā)的除P外的其它所有路都是懸掛路.對u、v分別進行Operation I,并記得到的新樹為F,由引理6, γ(F)≥γ(T),r(F)=r(T),λ(F)≥λ(T).對F,由引理7,引理1和定義1,有

于是Fu(1)、Fv(1)中鄰接譜半徑最大的那個樹就是滿足條件的樹T′.

引理9 設S(m,γ)如圖1所示,T2如圖4所示.則λ(S(m,γ))＞λ(T2).

圖4 樹T1和T2Fig.4 T1and T2

證明 由引理3,有

引理10 設T∈Γm,γ{T(m,γ)}且r(T)= 1,則λ(T)＜λ(S(m,γ)).

證明 因為r(T)=1,T≠T(m,γ),T至少有一條長度不小于3的懸掛路.根據引理1,λ(T)≤λ(T1),又由引理1,有λ(T1)＜λ(S(m,γ)),故有λ(T)＜λ(S(m,γ)).

引理11 設T∈Γm,γ且r(T)=2,則λ(T)≤λ(S(m,γ)),等號成立的充要條件是T=S(m,γ).

證明 設u、v是T的兩個度數不小于3的點.分別對u、v進行Operation I,記得到的樹為T′,則r(T′)=2,γ(T′)≥γ(T)且λ(T′)≥λ(T).

情形1 如果uv?E(T)

因為uv?E(T),所以uv?E(T′).由引理7,可知max{λ(T′u(1)),λ(T′v(1))}＞λ(T′)且min{γ(T′u(1)),γ(T′v(1))}≥γ.由引理1, max{λ(T′u(1)),λ(T′v(1))}≤λ(T1).于是

λ(T)≤λ(T′)＜max{λ(T′u(1)),λ(T′v(1))}≤λ(T1)＜λ(S(m,γ))

情形2 如果uv∈E(T)

uv∈E(T)于是有uv∈E(T′).設s、t分別為T′中從u出發(fā)的長為1,2的懸掛路的條數,s′、t′分別為從v出發(fā)的長為1,2的懸掛路的條數.

a.t≠0且t′≠0

由引理2,λ(T′)≤λ(T2)＜λ(S(m,γ)).

(b)s,s′中恰有一個為0

由引理2,λ(T′)＜max{λ(T1),λ(T2)}＜λ(S(m,γ),故λ(T)＜λ(S(m,γ)).

由引理2,λ(T′)＜λ(T1),于是即有λ(T)＜λ(S(m,γ)).

b.t、t′中恰有一個為0

不失一般性,假設t=0,則s≥2.

(a)s′=0

由引理2,λ(T′)≤max{λ(T1),λ(S(m,γ))}= λ(S(m,γ)),等號成立當且僅當T=S(m,γ).

(b)s′≠0

由引理2,λ(T′)≤max{λ(T2),λ(S(m,γ))}= λ(S(m,γ)),等號成立當且僅當T=S(m,γ).

c.t=t′=0

此時有γ=2,s≥2且s′≥2.由引理2,λ(T′)≤λ(S(m,2)),等號成立當且僅當T=S(m,2).

綜上所證,有λ(T)≤λ(T′)≤λ(S(m,γ)),等號成立當且僅當T=S(m,γ).

定理1的證明

a.在引理2中,取T=S(m,γ),u=u,v=v, s=1且t=m-γ-3,則

則 max{λ(Tu),λ(Tv)}=λ(T(m,γ))＞λ(S(m,γ)).

b.分4種情形考慮

(a)r(T)=0

如果r(T)=0,則T是一條路,λ(T)＜λ(S(m, γ))顯然成立.

(b)r(T)=1

由引理10,λ(T)＜λ(S(m,γ)).

(c)r(T)=2

由引理11,λ(T)＜λ(S(m,γ)).

(d)r(T)≥3

由引理8,存在一個γ(T′)=2的樹T′,γ(T′)≥γ,且λ(T′)＞λ(T).再由(b),λ(T′)≤λ(S(m, γ(T′)))≤λ(S(m,γ)),于是有λ(T)＜λ(T′)≤λ(S(m,γ)).

c.由引理3,有

故λ(T(m,γ))是方程x4-(m-γ+1)x2+m-2γ+1=0的最大根.

d.由引理3,有

故λ(S(m,γ))是方程x6+(-m-2+γ)x4+(3m-4γ-1)x2-2m+4γ=0的最大根.

[1] BRUALDI R A,SOLHEID E S.On the spectral radius of complementary acyclic matrices of zeros and ones[J].SIAM JAlgebra Discrete Method,1986,7(2):265-272.

[2] WU B F,XIAO E L,HONG Y.The spectral radius of trees on k pendent vertices[J].Linear Algebra Appl, 2005,395:343-349.

[3] BERMAN A,ZHANG X D.On the spectral radius of graphs with cut vertices[J].J Combin Theory Ser B, 2001,83(2):233-240.

[4] LIU H,LU M,TIAN F.On the spectral radius of graphs with cut edges[J].Linear Algebra Appl,2004, 389:139-145.

[5] GUO J M.On the specral radius of trees[J].Linear Algebra Appl,2001,329(1):1-8.

[6] GUO J M.On the spectral radius of trees with fixed diameter[J].Linear Algebra Appl,2006,413(1): 131-147.

[7] FENG L H,YU G H,ZHANG X D.Spectral radius of graphs with given matching number[J].Linear Algebra Appl,2007,422(1):133-138.

[8] LI Q,FENG K Q.On the largest eigenvalue of a graph [J].Acta Math Appl Sinica,1979,2:167-175.

[9] CVETKOVIC D,ROWLINSON P,SIMIC S.Eigenspaces of Graphs[M].Cambridge:Cambridge University Press,1997.

[10] CVETKOVIC D,DOOB M,SACHS H.Spectral of Graphs[M].New York:Academic Press,1980.

On the spectral radius of trees with given domination number

CHENPing, HEChang-xiang
(College of Sciemce,Umiversity of Shamghai for Sciemce amd Techmology,Shamghai 200093,Chima)

The trees defined onΓm,γ(m≥2γ+1,γ≥2)were discussed.By using the theorems of moving edges,a new operation of moving edges was constructed.The first two largest spectral radiuses in the classΓm,γ,together with the corresponding graphs were given.

graph；tree；spectral radius；domimatiommumber

O 157.5文獻標示碼：A

1007-6735(2011)05-0485-04

2010-09-21

陳 萍(1986-),女,碩士研究生.研究方向:組合優(yōu)化.E-mail:chenping691@126.com

何常香(聯系人),女,講師.研究方向:組合優(yōu)化.E-mail:changxianghe@hotmail.com