有关一类树的最大特征值

有关一类树的最大特征值 2011年2月 第27卷第1期 江苏教育学院(自然科学) JournalofJiangsuInstituteofEducation(NaturalSciences) Feb.,2011 Vo1.27No.1 有关一类树的最大特征值 邵霞徐新萍 (1.江苏省宜兴第一中学,江苏宜兴214200; 江苏教育学院与信息技术学院,江苏南京210013) 2. [摘要]设为n个顶点的树的集合,关于的特征值的排序到目前为止已经得到许多 结论,本文主要讨论 了树类,等的最大特征值的上界. [关键词]树;特征值;上界 [中图分类号]O157.5[文献标识码]A[文章编号]1671—1696(2011)01—0021一o3 一 ,引言 设G是有?个顶点{.,,,…,}的简单连 通图_l,G的邻接矩阵A=(a)是(0,1)矩阵,其 中a=1当且仅当与相邻,G的特征多项式det (AI—A)记为(G,A)J.由于A是实对称矩阵,所以 它的特征值全是实数.我们总假定它们按不升的次 序排歹U,即A(G)?A.(G)?…?A(G). 定理1.1_2G是有n个顶点的简单图,令 (G,A)=A+clA一+c2A+…+c,贝0 (1)c=0;(2)一c:等于图G的边数;(3)一c, 等于图G中三角形个数的两倍. 定理1.2G是有个顶m点条边的图,则 l A?f'\n/ 定理1.3_2如果G是树,则A(G)=一A…+ (G),i=1,2,…,【n/2]. 设为n个顶点的树的集合,关于的特征值 的排序到目前为止已经得到许多结论,对于n个顶 点的树的最大特征值的上界我们列出有关前九位的 图i,具体的相关结果见([3],[4],[5]).注:兰S 或T--s时,最大特征值相同. 设={r,E,且中恰有i条非悬挂边}, 则=t_J.显然,分别只包含星树与 一 5一4 :二 s:6 图1图类中最大特征值前9位的树 路JP,与中的树具有如图2所示的形状,其中 +:n一2,I???一3;r+s+t=n一3,I?r?, t?0. 图2, 中包含如图3所示的两种形状的树,分别记为 [收稿日期]2010—10—18 [作者简介]邵霞(1982一),女,江苏省宜兴市第一中学二级教师 一 21一 ?1: 其中P1+q1+l1+m1=n一4,Pl>/0,q1?11?ml P2+q2+l2+m2=n一4,P2,q2t>0,l2?m2?1; 日 ..轧f1J L. 珏b 图3中的树 中包含如图4所示的3种形状的树,分别记为 e rlIfl'胁.r2,%", 其中P1+g1+r1+ l+tl=rt一5,PlI>0,q1?r1?s1?t1?1;p2+q2+r2+ 2+t2=/7,一5,P2,q2?0,2?s2?t2?1;P3+q3+ 3+3+t3=n一5,3?t3?1,P3,q3,r3?0. Pl lmLh%b ptq b 图4中的树 定理1.4设?\{.s:,5:,s:,一.},则 A1()?n-1+~/nz-14n+53. ,n?10,当且 仅当兰一..时等号成立. 本文关于树类,一 ,_6.0.1,.和_9.,, I1l的最 大特征值得到如下结果. 定理1.5对于树一6,_6_o,lI1和_9'1,1,1,1 有 AI(一6.0.1.1)>Al(,一6),nI>12;A1(,,6)> Al(rl-9.1.1.1.1),?lO. 定理1.6当n?lO时,A(一6.o.1.)>A1 (. - 5,0). 定理1.7设T?\{S,S,S:,S:,S:,S:,, |s,Js:}.当n?12时, 有A()?Y,其中Y是A.一(n一1)A+ (3n一12)A一(2n一11)=0的最大根, 当且仅当T=_6l..1.1时等号成立. 二,主要引理 因为图的特征多项式的根是实数,因此约定本 文讨论的多项式f()都是首1多项式,且它的根都 是实数,a(和A(f)分别示f()的次数和最大 根.定理证明将用到以下引理. 一 22一 引理2.1设G是由G,G连结//,,tl而成,其 中///?GI,?G2,则 (G,A)=(G.,A)(G,A)-X(G.\",A)(G2\ ,A) 引理2.2[6设是图C的度为1的点,是 的邻接点,则 (G,A)=^(G\v,A)-X(G\{",},A) 引理2.3[4设G是连通图,若G是G的真子 图,则A1(G)>A1(G). 引理2.4设多项式f(),g()是首1的根 都是实数,且a(-厂)?0(g). 若f()=q()g()+r(),且r()=0或 o(g)>o(g),其中q(x)也是首1多项式. 若A(g)?A.(q),贝4 (1)当r()=0时,A(=A(g), (2)当?A.(g)时,r()>0,贝0A(f)<A (g), (3)当r(A(g))<0时,A.(>A(g). 弓l理2.5设?\5:,n?8,贝0A1()?1, 当且仅当T:..?时等号成立. 其中1为A一(rt一1)A+(3n一12)A一(2n 一 11):0的最大根. 弓I理2.6[4设T?rn,ii>4,?10,贝0A(T)? /n一4+~/(n一4)一(/7,一9) ?2' 当且仅当T=.时等号成立. 引理2.7中按树的最大特征值排序如 下: Al(r1.一3)>A1(.一4)>A1(,一5)>Al (,)>…>A(,n-2). 三,主要结论的证明 定理1.4的证明:首先由引理2.1,2.2,树 . .的特征多项式为 (.一..,A)=A一[A一(n一1)A+(3n一 13)] 由求根,易得其最大根为 r———————=;========= ./?,定理2.1得证.^/,,'—Jq. 定理1.5的证明由引理2.1和引理2.2,得 (一6,0,1.1.,A)=A一[A一(n一1)A+(3n一 12)A一(2n一11)]=A一^(A) (. 一 ,A):A一[A一(凡一1)A+4(n一6)]= Ag(A) (_9ll-1.1.1,A)=Am(A一1).[A一(n一4)A一 (n一4)A+(n一9)]=A加(A一1)h(A) A):AZg(A)一(一12)A一(2n一11)=A2g (A)+r,(A), 显然当n?12时,r(A.(.一))<0,由引理2. 4知,A1(_6lo.1I1)>A(,一6). h(A)=g(A)+3A一3(n一5)=g(A)+r(A). 因为. 一中至少含有n一4个顶点的星树,故 由引理2.3知 A(. 一)>,当时A?A(,一)(> n一5)时,r(A)>0. 由引理2.4得,A(. 一 6)>A.(.9llI1,l,1). 定理1.6的证明由引理2.1和引理2.2可得 (_6'.,l1I,,A)=A[A一(n一1)A+(3n一 12)A一(2n一11)]=A一^(A) (.一5.o,A)=A一4[A4一(一1)A.+(3n一 13)]=A"-4g(A), l厂(A)=A2g(A)+A一(2n一11)=A2g(A)+r (A), 因为r(A1(,一 5,o ))=I(n一1+ 丽一(2n一11)= [一3(n一7)+]<o(因为?l0) 二 所以由引理2.4有,A(_6'.,l,1)>A (. - 5,0). 定理1.7的证明由定理1.4至定理1.6以及引 理2.5到引理2.7,可直接得证. [参考文献] [1]J.A.Bondy,U.S.R.Murty.GraphTheorywithAppli— cations[M].NewYork:LondonandElservier,1976. [2]R.J.Wilson.Introductiontographtheory[M].Oliver andBoyd,Edinburgh,1972. [3]M.Hofmeister.Onthetwolargesteigenvaluesoftrees, LinearAlgebraanditsApplications[J].1997,260. [4]AnChang,QunxiangHuang,Orderingtreesbytheir largesteigenvalues,LinearAlgebraanditsApplications [J].2003,370. [5]梁修东,树的最大特征值的序[J].江南大学, 2007,(5). [6]D.Cvetkovi,M.Doob,H.Sachs.SpectraofGraph— TheoryandApplication[M].AcademicPress,New York,1980. [7]AnChang,Onthelargesteigenvalueofatreewithper— feetmatchings,DiscreteMathematics[J].2003,269. (责任编辑印亚静) 一 23—