共查询到20条相似文献,搜索用时 0 毫秒
1.
The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we provide structural and behavioral details of graphs with maximum Laplacian spectral radius among all bipartite connected graphs of given order and size. Using these results, we provide a unified approach to determine the graphs with maximum Laplacian spectral radii among all trees, and all bipartite unicyclic, bicyclic, tricyclic and quasi-tree graphs, respectively. 相似文献
2.
3.
The Estrada index of a graph G is defined as , where λ1,λ2,…,λn are the eigenvalues of G. The Laplacian Estrada index of a graph G is defined as , where μ1,μ2,…,μn are the Laplacian eigenvalues of G. An edge grafting operation on a graph moves a pendent edge between two pendent paths. We study the change of Estrada index of graph under edge grafting operation between two pendent paths at two adjacent vertices. As the application, we give the result on the change of Laplacian Estrada index of bipartite graph under edge grafting operation between two pendent paths at the same vertex. We also determine the unique tree with minimum Laplacian Estrada index among the set of trees with given maximum degree, and the unique trees with maximum Laplacian Estrada indices among the set of trees with given diameter, number of pendent vertices, matching number, independence number and domination number, respectively. 相似文献
4.
5.
Ji-Ming Guo 《Linear algebra and its applications》2008,429(7):1705-1718
The study of limit points of eigenvalues of adjacency matrices of graphs was initiated by Hoffman [A.J. Hoffman, On limit points of spectral radii of non-negative symmetric integral matrices, in: Y. Alavi et al. (Eds.), Lecture Notes Math., vol. 303, Springer-Verlag, Berlin, Heidelberg, New York, 1972, pp. 165-172]. There he described all of the limit points of the largest eigenvalue of adjacency matrices of graphs that are no more than . In this paper, we investigate limit points of Laplacian spectral radii of graphs. The result is obtained: Let , β0=1 and be the largest positive root of
6.
Kinkar Ch. Das 《Linear algebra and its applications》2010,432(11):3018-2584
Let G=(V,E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the Laplacian matrix of G is L(G)=D(G)-A(G) and the signless Laplacian matrix of G is Q(G)=D(G)+A(G). In this paper we obtain a lower bound on the second largest signless Laplacian eigenvalue and an upper bound on the smallest signless Laplacian eigenvalue of G. In [5], Cvetkovi? et al. have given a series of 30 conjectures on Laplacian eigenvalues and signless Laplacian eigenvalues of G (see also [1]). Here we prove five conjectures. 相似文献
7.
Xiaoling Zhang 《Linear algebra and its applications》2008,428(7):1610-1619
In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K1,k and one vertex of degree n of Km,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs. 相似文献
8.
W.H. Haemers A. Mohammadian B. Tayfeh-Rezaie 《Linear algebra and its applications》2010,432(9):2214-399
Let k be a natural number and let G be a graph with at least k vertices. Brouwer conjectured that the sum of the k largest Laplacian eigenvalues of G is at most , where e(G) is the number of edges of G. We prove this conjecture for k=2. We also show that if G is a tree, then the sum of the k largest Laplacian eigenvalues of G is at most e(G)+2k-1. 相似文献
9.
Motivated by a Mohar’s paper proposing “how to order trees by the Laplacian coefficients”, we investigate a partial ordering of trees with diameters 3 and 4 by the Laplacian coefficients. These results are used to determine several orderings of trees by the Laplacian coefficients. 相似文献
10.
Laplacian spectral characterization of 3-rose graphs 总被引:1,自引:0,他引:1
A 3-rose graph is a graph consisting of three cycles intersecting in a common vertex, J. Wang et al. showed all 3-rose graphs with at least one triangle are determined by their Laplacian spectra. In this paper, we complete the above Laplacian spectral characterization and prove that all 3-rose graphs are determined by their Laplacian spectra. 相似文献
11.
A note on the signless Laplacian eigenvalues of graphs 总被引:1,自引:0,他引:1
In this paper, we consider the signless Laplacians of simple graphs and we give some eigenvalue inequalities. We first consider an interlacing theorem when a vertex is deleted. In particular, let G-v be a graph obtained from graph G by deleting its vertex v and κi(G) be the ith largest eigenvalue of the signless Laplacian of G, we show that κi+1(G)-1?κi(G-v)?κi(G). Next, we consider the third largest eigenvalue κ3(G) and we give a lower bound in terms of the third largest degree d3 of the graph G. In particular, we prove that . Furthermore, we show that in several situations the latter bound can be increased to d3-1. 相似文献
12.
Using the AutoGraphiX system, we obtain conjectures of the form l(n)?q1⊕i(G)?u(n) where q1 denotes the signless Laplacian index of graph is one the four operations is another invariant chosen among minimum, average and maximum degree, average distance, diameter, radius, girth, proximity, remoteness, vertex, edge and algebraic connectivities, independence number, domination number, clique number, chromatic number and matching number, Randi? index, l(n) and u(n) are best possible lower and upper bounds function of the order n of G. Algebraic conjectures are obtained in 120 cases out of 152 and structural conjectures in 12 of the remaining cases. These conjectures are known, immediate or proved in this paper, except for 17 of them, which remain open. 相似文献
13.
Steve Kirkland 《Linear algebra and its applications》2007,423(1):3-21
A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. We consider the class of constructably Laplacian integral graphs - those graphs that be constructed from an empty graph by adding a sequence of edges in such a way that each time a new edge is added, the resulting graph is Laplacian integral. We characterize the constructably Laplacian integral graphs in terms of certain forbidden vertex-induced subgraphs, and consider the number of nonisomorphic Laplacian integral graphs that can be constructed by adding a suitable edge to a constructably Laplacian integral graph. We also discuss the eigenvalues of constructably Laplacian integral graphs, and identify families of isospectral nonisomorphic graphs within the class. 相似文献
14.
Bao-Xuan Zhu 《Linear algebra and its applications》2010,433(5):928-261
In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph Gn,k, where Gn,k is obtained from the complete graph Kn-k by attaching paths of almost equal lengths to all vertices of Kn-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius. 相似文献
15.
16.
Igor Shparlinski 《Linear algebra and its applications》2006,414(1):378-382
We give an explicit construction of circulant graphs of very high energy. This construction is based on Gauss sums. We also show the Littlewood conjecture can be used to establish new result for a certain class of circulant graphs. 相似文献
17.
The unique graphs with minimum and second-minimum distance (distance signless Laplacian, respectively) spectral radii are determined among bicyclic graphs with fixed number of vertices. 相似文献
18.
A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M-theory. We outline a spectral theory of graphs based on the signless Laplacians Q and compare it with other spectral theories, in particular to those based on the adjacency matrix A and the Laplacian L. As demonstrated in the first part, the Q-theory can be constructed in part using various connections to other theories: equivalency with A-theory and L-theory for regular graphs, common features with L-theory for bipartite graphs, general analogies with A-theory and analogies with A-theory via line graphs and subdivision graphs. In this part, we introduce notions of enriched and restricted spectral theories and present results on integral graphs, enumeration of spanning trees, characterizations by eigenvalues, cospectral graphs and graph angles. 相似文献
19.
Let G be a simple connected graph of order n with degree sequence d1,d2,…,dn in non-increasing order. The signless Laplacian spectral radius ρ(Q(G)) of G is the largest eigenvalue of its signless Laplacian matrix Q(G). In this paper, we give a sharp upper bound on the signless Laplacian spectral radius ρ(Q(G)) in terms of di, which improves and generalizes some known results. 相似文献
20.
The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. Bao, Tan and Fan [Y.H. Bao, Y.Y. Tan,Y.Z. Fan, The Laplacian spread of unicyclic graphs, Appl. Math. Lett. 22 (2009) 1011-1015.] characterize the unique unicyclic graph with maximum Laplacian spread among all connected unicyclic graphs of fixed order. In this paper, we characterize the unique quasi-tree graph with maximum Laplacian spread among all quasi-tree graphs in the set Q(n,d) with . 相似文献