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

《控制数固定树的邻接谱半径.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上海理工大学学报第33卷第5期J．UniversityofShanghaiforScienceandTechnologyVo1．33No．52011文章编号：1007—6735(2011)05—0485—04控制数固定树的邻接谱半径陈萍，何常香(上海理工大学理学院，上海200093)摘要：研究定义在r(n≥27+1，y≥2)中的树，借助夺邻、嫁接等移边定理，通过构造一种新的移边运算OperationI，给出了I1中前两大谱半径，并证明了T(n，)，S(n，)是达到前两大谱半径的图．关键词：图；树；邻接谱半径；控制数中图分类号：01

2、57．5文献标志码：AOnthespectralradiusoftreeswithgivendominationnumberCHENPing，HEChano—xiang(CollegeofScience，UniversityofShanghaifoScienceandTechnology，Shanghai200093，China)Abstract：ThetreesdefinedonF(n≥2y+1，y≥2)werediscussed．Byusingthetheoremsofmovingedges，anewoperationofmo

3、vingedgeswasconstructed．Thefirsttwolargestspectralradi-usesintheclassF，y，togetherwiththecorrespondinggraphsweregiven．Keywords：graph；tree；spectralradius；dominationnumber仅考虑简单连通图，设G=(V，E)是一个以有n个点的路，G中度数为1的点叫悬挂点．悬挂V={V，，⋯，)为顶点的集合，E为边集合的路是指内部顶点度数为2，端点度数为1的路．对简单连通图．G的邻接矩阵A

4、(G)为一个nx矩于图G=(V，E)，用NG()或N()来表示G中阵，设A(G)=(a订)，其中当V与J相邻时，a巧=1；与相邻的点的集合．称ucv为G的一个控制当V与V不相邻时，a甜=0．G的特征多项式定义集，若【厂UN(U)：V，其中N(【，)=U∈uN(U)．为(G，)：det(∞I一A(G))，简记为中(G)．由于控制数是指G中所有控制集的最小基数，用y(G)G是一个简单图，A(G)是一个实对称(0，1)一矩表示．如果G没有孤立点，则y(G)≤n／2．恰有)，阵，其所有特征值都为实数．不失一般性，可以假设个点的控制集叫做y

5、—set．在本文中，用l(G)≥2(G)≥⋯≥(G)r⋯(n≥27+1，)，≥2)表示阶数为n，控制数为7且称(G)为G的第k大特征值．特别地，(G)的树的集合．称为G的谱半径，记为(G)．文献[1]曾提出，在给定的一类图的集合G中，令d=d(V)表示G中点V的度数，P表示寻找谱半径的上界与下界，并刻画达到了上界或下收稿日期：2010—09—21作者简介：陈萍(1986一)，女，硕士研究生．研究方向：组合优化．E-mail：chenping691@126．corn何常香(联系人)，女，讲师．研究方向：组合优化．E-mail：cha

6、ngxianghe@hotmail．com上海理工大学学报2011年第33卷界的图．此问题提出后，掀起了对特殊图类的谱半径T札=T—1一2一⋯一一s+的研究的热潮．比如树，文献[2]研究了悬挂点数固1+?ZV2+⋯+s定的树的谱半径，所有阶数为，有个悬挂点的T=T—钆1一2⋯一￡+树中，T是唯一具有最大谱的树，其中T是在1+2十⋯十fjt星图K．的每个悬挂点处引出一条长度几乎相等的贝0max{(T)，(T)}>(T)．悬挂路所得的图．文献[3]研究了割点数固定的树的引理3E加]设V为图G的一个悬挂点，是V谱半径，证明了在所有阶数为

7、，有k条割边的连的邻点，则(G)=(G一)一(G一一)．通图中，K是唯一具有最大谱的图．其中K是在引理4Esl设G是一连通图，G是G的连通真完全图K一的某个顶点上引出条悬挂边而得到子图．则对任意≥(G)有(G，)>(G，)．的图，文献[4]研究了割边数固定的图的谱半径，证记△(G)为G的最大度．由引理4，有(G)≥明了在所有阶数，有条割边的连通图中，K是(K1．△(G)U(竹一△(G)一1)K1)=~／△(G)．唯一具有最大谱的图，其中K是在完全图K一的某个顶点上引出k条悬挂边而得到的图．更多关于2定理1的证明树的谱半径的研究见文

8、献[5—7]．笔者主要研究在控制数固定的条件下树的谱半径问题，并得到如下首先，给出如下两个图的控制数的关系：结论：引理5设G是一个连通图，∈(G)，H是定理1设T∈r⋯(≥27+1，7≥2)，由G通过点加一条悬挂路钆钆U。得到的图，T(，y)，S(