关于双圈图的谱半径
- 格式：pdf
- 大小：179.04 KB
- 文档页数：10
273Vol.27,No.3 20078JOURNAL OF MATHEMATICAL RESEARCH AND EXPOSITION Aug.,2007 Article ID:1000-341X(2007)03-0445-10Document code:AOn the Spectral Radii of Bicyclic GraphsHE Chang-xiang,LIU Yue,SHAO Jia-yu(Department of Mathematics,Tongji University,Shanghai200092,China)(E-mail:changxianghe@)Abstract:A graph G of order n is called a bicyclic graph if G is connected and the numberof edges of G is n+1.Let B(n)be the set of all bicyclic graphs on n vertices.In this paper,thefirst three largest spectral radii in the class B(n)(n≥9)together with the correspondinggraphs are given.Key words:bicyclic graph;spectral radius;characteristic polynomial.MSC(2000):05C50CLC number:O157.51.IntroductionWe consider onlyfinite undirected graphs without loops or multiple edges.Let G be a graph with n vertices,and A(G)be the(0,1)-adjacent matrix of G.Since A(G)is symmetric and real,its eigenvalues are real.These eigenvalues of A(G)are independent of the ordering of the vertices of G,and consequently,without loss of generality,we can write them in non-increasing order asλ1(G)≥λ2(G)≥···≥λn(G)and call them the eigenvalues of G.The characteristic polynomial of G is just det(xI−A(G)),and denoted by P(G,x).The largest eigenvalueλ1(G) is called the spectral radius of G,denoted byρ(G).If G is connected,then A(G)is irreducible andρ(G)is simple and there exists a unique positive unit eigenvector corresponding toρ(G)by the Perron-Frobenius Theorem of non-negative matrices.The unique positive unit eigenvector corresponding toρ(G)is called the Perron vector of G.The investigation on the spectral radii of graphs is an important topic in the theory of graph spectral.For results on the spectral radii of graphs,one may refer to[1]–[10]and the reference therein.Bicyclic graphs are connected graphs in which the number of edges equals the number of vertices plus one.Yu and Tian[10]determined the graphs with the largest spectral radius among all the bicyclic graphs on n vertices with matching number m.In this paper,we study the spectral radii of bicyclic graphs,and give thefirst three largest spectral radii in the class B(n)(n≥9)together with the corresponding graphs.2.Three types of bicyclic graphsDefinition2.1A graph G of order n is called a bicyclic graph if G is connected and the number of edges of G is n+1.446Journal of Mathematical Research and Exposition Vol.27r p p p rr r r d d r r r p p p r r p p p rNo.3HE C X,et al:On the spectral radii of bicyclic graphs447∆(G).Theorem2.1Let G be a connected graph and u,v1,v2,...,v r(r≥1)be vertices of G.Suppose V1,V2,...,V r are pairwise disjoint vertex subsets of G,which are not all empty,andV i={v i1,v i2,...,v iki}⊆N(v i)\(N(u)∪{u})(i=1,2,...,r).Let G u(v1,...,v r)be the graph with V(G u(v1,...,v r))=V(G)andE(G u(v1,...,v r))=(E(G)\ri=1{v i v i1,...,v i v ik i})(ri=1{uv i1,...,uv ik i}).Let X be the Perron vector of G.Suppose we have X u≥max{X v1,...,X v r},where X u denotes the coordinates of X corresponding to the vertex u,thenρ(G u(v1,...,v r))>ρ(G).Proof Let G′=G u(v1,···,v r).From the well-known results of real symmetric matrices in linear algebra,we have X T A(G)X=ρ(G)andρ(G′)≥X T A(G′)X.So we haveρ(G′)−ρ(G)≥X T A(G′)X−X T A(G)X=X T[A(G′)−A(G)]X=ri=1(k ij=1(X u−X v i)X v ij)≥0.(2.1)Next we want to show the strict inequality holds in(2.1).Suppose not,then all the equalities hold in(2.1).In particular,we haveρ(G′)=ρ(G)=X T A(G′)X,which implies that X is also448Journal of Mathematical Research and Exposition Vol.27No.3HE C X,et al:On the spectral radii of bicyclic graphs449n−2,i.e.,P(G2,x)<0,which implies ρ(G2)>ρ(G3).24.The proof of(R3)Lemma4.1Let G∈B1(n)and G=B(p,q).If p+q≥7,thenρ(G)<ρ(B1)orρ(G)<ρ(B2) (B1and B2are the graphs shown in Fig.4.1).Proof By Lemma2.5,Corollary2.2and Theorem2.1,we haveρ(G)<ρ(B s,t)for some s,t with s,t≥1,(B s,t)is the graph shown in Fig.4.1).Let x be the perron vector of B s,t.If X u≥X v.By Theorem2.1,we haveρ(B s,t)<ρ(B2).450Journal of Mathematical Research and Exposition Vol.27n−2,p(x)>0,which impliesρ(B1)<ρ(G3).2The Proof of(R3)By Lemma4.1,it suffices to consider G=B(3,3).By Theorem2.1and Lemma2.5,we only need to consider G∈(B11(n)\{G1})∪B12(n).We distinguish the following two cases.Case1.G∈B11(n)\{G2}.Subcase1.1The common vertex of the two C3in G is the divarication-vertex.Suppose the unique divarication-vertex is v,and q(G)is the number of non-pendant vertices different from v in the tree attached to G.Since G=G2,q(G)>0.From the proof of Lemma 2.5,we know that if q(G)≥2,then there exists a graph G′∈B1(n)such that G′= G,q(G′)=1 andρ(G′)>ρ(G).So it suffices to consider the graph G with q(G)=ing u to denote the unique non-pendant vertex different from v in the tree attached to G.B′3B3Figure4.2The graphs B3and B′3(1)X v≥X u.By Theorem2.1,ρ(G)≤ρ(B3)(B3is the graph shown in Fig.4.2).By Lemma2.3,we obtainρ(B3)<ρ(B1)<ρ(G3),which impliesρ(G)<ρ(G3).No.3HE C X,et al:On the spectral radii of bicyclic graphs451452Journal of Mathematical Research and Exposition Vol.27n−3,h(x)>0,which impliesρ(B4)<ρ(G3).2 6.The proof of(R5)B6B7Figure6.1The graphs B6and B7Similar to the proof of Lemmas4.1and4.2,we haveLemma6.1Let G∈B3(n)and G=P(p,q,l).If p+q+l≥6,thenρ(G)<ρ(B6),ρ(G)<ρ(B7) orρ(G)<ρ(G3)(B6,B7are the graphs shown in Fig.6.1).Lemma6.2ρ(B6)<ρ(G3).Proof By Corollary2.1,we haveP(B6,x)=x n−6[x6−(n+1)x4−4x3+(3n−12)x2+2x+5−n]∆=x n−6f6(x). Combining the above equation and(3.1),we haveP(B6,x)−P(G3,x)=x n−5[x2+2x+5−n]∆=x n−5q(x).√When x=ρ(B6)≥No.3HE C X,et al:On the spectral radii of bicyclic graphs453n−1,f(x)>0,which implies ρ(G1)>ρ(G2).2454Journal of Mathematical Research and Exposition Vol.27。
