控制数固定树的邻接谱半径

陈 萍, 何常香

(上海理工大学理学院,上海 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发出的两条悬挂路,且按以下规则对邻点排序:

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出发的除P外的其它所有路都是长不超过2的悬挂路,则

证明

a.先证γ(Tu(1))≥γ.设s、t分别为T中从u出发的长为1,2的悬挂路的条数,s′、t′分别为从v出发的长为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出发的除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出发的长为1,2的悬挂路的条数,s′、t′分别为从v出发的长为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-),女,硕士研究生.研究方向:组合优化.E-mail:chenping691@126.com

何常香(联系人),女,讲师.研究方向:组合优化.E-mail:changxianghe@hotmail.com