陳 萍, 何常香

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

控制數(shù)固定樹的鄰接譜半徑

陳 萍, 何常香

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

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

圖;樹;鄰接譜半徑;控制數(shù)

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

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

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

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

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

b.對(duì)所有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 預(yù)備知識(shí)

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

引理2[2]設(shè)u,v是樹T的頂點(diǎn),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]設(shè)v為圖G的一個(gè)懸掛點(diǎn),u是v的鄰點(diǎn),則Φ(G)=xΦ(G-v)-Φ(G-u-v).

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

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

2 定理1的證明

首先,給出如下兩個(gè)圖的控制數(shù)的關(guān)系:

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

圖2 H和WFig.2 H and W

證明

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

綜上,γ′=γ+1.

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

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

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

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

綜上及引理1,得到以下結(jié)論:

引理6 如果T′是由樹T經(jīng)Operation I得到的樹,則

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

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

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

定義

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

證明

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

情形1 t=0

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

情形2 t≠0

若s′≥2時(shí),u從v處所奪邊包含有懸掛邊,所以γ(Tu(1))≥γ.當(dāng)s′≤1時(shí),則t′≥1,u從v處所奪邊都是長(zhǎng)為2的懸掛路,此時(shí)γ(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 設(shè)T∈Γm,γ,如果r(T)≥3,則一定存在一棵樹T′滿足

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

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

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

圖4 樹T1和T2Fig.4 T1and T2

證明 由引理3,有

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

證明 因?yàn)閞(T)=1,T≠T(m,γ),T至少有一條長(zhǎng)度不小于3的懸掛路.根據(jù)引理1,λ(T)≤λ(T1),又由引理1,有λ(T1)＜λ(S(m,γ)),故有λ(T)＜λ(S(m,γ)).

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

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

情形1 如果uv?E(T)

因?yàn)閡v?E(T),所以u(píng)v?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′).設(shè)s、t分別為T′中從u出發(fā)的長(zhǎng)為1,2的懸掛路的條數(shù),s′、t′分別為從v出發(fā)的長(zhǎng)為1,2的懸掛路的條數(shù).

a.t≠0且t′≠0

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

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

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

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

b.t、t′中恰有一個(gè)為0

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

(a)s′=0

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

(b)s′≠0

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

c.t=t′=0

此時(shí)有γ=2,s≥2且s′≥2.由引理2,λ(T′)≤λ(S(m,2)),等號(hào)成立當(dāng)且僅當(dāng)T=S(m,2).

綜上所證,有λ(T)≤λ(T′)≤λ(S(m,γ)),等號(hào)成立當(dāng)且僅當(dāng)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,存在一個(gè)γ(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文獻(xiàn)標(biāo)示碼：A

1007-6735(2011)05-0485-04

2010-09-21

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

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