An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree

A Bethe tree B_d,k is a rooted unweighted of k levels in which the root vertex has degree equal to d, the vertices at level j(2?j?k-1) have degree equal to (d+1) and the vertices at level k are the pendant vertices. In this paper, we first derive an explicit formula for the eigenvalues of the adjacency matrix of B_d,k. Moreover, we give the corresponding multiplicities. Next, we derive an explicit formula for the simple nonzero eigenvalues, among them the largest eigenvalue, of the Laplacian matrix of B_d,k. Finally, we obtain upper bounds on the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any tree T. These upper bounds are given in terms of the largest vertex degree and the radius of T, and they are attained if and only if T is a Bethe tree.     

The spectra of some trees and bounds for the largest eigenvalue of any tree

Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let n_k−j+1 and d_k−j+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of T for the case of two vertices in level 1 (n_k = 2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are , 2 ? j ? k, while the diagonal entries are 0, …, 0, ±1, in the case of the adjacency matrix, and d₁, d₂, …, d_k−1, d_k ± 1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree.     

The signless Laplacian spectral radius of tricyclic graphs and trees with k pendant vertices

In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at T_n,k, where T_n,k is a tree obtained from a star K_1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of T_n,k and give some results.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q₁(G). Then we present three sharp lower bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.     

Spectral characterization of some weighted rooted graphs with cliques

The level of a vertex in a rooted graph is one more than its distance from the root vertex. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. We characterize completely the eigenvalues of the Laplacian, signless Laplacian and adjacency matrices of a weighted rooted graph G obtained from a weighted generalized Bethe tree of k levels and weighted cliques in which

(1)

the edges connecting vertices at consecutive levels have the same weight,

(2)

each set of children, in one or more levels, defines a weighted clique, and

(3)

cliques at the same level are isomorphic.

These eigenvalues are the eigenvalues of symmetric tridiagonal matrices of order Moreover, we give results on the multiplicity of the eigenvalues, on the spectral radii and on the algebraic conectivity. Finally, we apply the results to the unweighted case and some particular graphs are studied.     

Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:

the generalized Bethe tree B,

a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,

a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,

a graph obtained from the cycle C_r by attaching B, by its root, to each vertex of the cycle, and

a tree obtained from the path P_r by attaching B, by its root, to each vertex of the path,

is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.

     

On the sum of the Laplacian eigenvalues of a tree

Given an n-vertex graph G=(V,E), the Laplacian spectrum of G is the set of eigenvalues of the Laplacian matrix L=D-A, where D and A denote the diagonal matrix of vertex-degrees and the adjacency matrix of G, respectively. In this paper, we study the Laplacian spectrum of trees. More precisely, we find a new upper bound on the sum of the k largest Laplacian eigenvalues of every n-vertex tree, where k∈{1,…,n}. This result is used to establish that the n-vertex star has the highest Laplacian energy over all n-vertex trees, which answers affirmatively to a question raised by Radenkovi? and Gutman [10].     

On the sum of Laplacian eigenvalues of graphs

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.     

On the signless Laplacian spectral radius of graphs with cut vertices

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 G_n,k, where G_n,k is obtained from the complete graph K_n-k by attaching paths of almost equal lengths to all vertices of K_n-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.     

On the Estrada and Laplacian Estrada indices of graphs

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of G. The Laplacian Estrada index of a graph G is defined as , where μ₁,μ₂,…,μ_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.     

Note the T-shape tree is determined by its Laplacian spectrum

A T-shape is a tree with exactly one of its vertices having maximal degree 3. It is proved in this paper that the T-shape tree is determined by its Laplacian spectrum.     

Universal adjacency matrices with two eigenvalues

Consider a graph Γ on n vertices with adjacency matrix A and degree sequence (d₁,…,d_n). A universal adjacency matrix of Γ is any matrix in Span {A,D,I,J} with a nonzero coefficient for A, where and I and J are the n×n identity and all-ones matrix, respectively. Thus a universal adjacency matrix is a common generalization of the adjacency, the Laplacian, the signless Laplacian and the Seidel matrix. We investigate graphs for which some universal adjacency matrix has just two eigenvalues. The regular ones are strongly regular, complete or empty, but several other interesting classes occur.     

Ordering trees with n vertices and matching number q by their largest Laplacian eigenvalues

Denote by T_n,q the set of trees with n vertices and matching number q. Guo [On the Laplacian spectral radius of a tree, Linear Algebra Appl. 368 (2003) 379-385] gave the tree in T_n,q with the greatest value of the largest Laplacian eigenvalue. In this paper, we give another proof of this result. Using our method, we can go further beyond Guo by giving the tree in T_n,q with the second largest value of the largest Laplacian eigenvalue.     

On the minimal number of edges in color-critical graphs

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.     

An efficient condition for a graph to be Hamiltonian

Let G=(V,E) be a 2-connected simple graph and let d_G(u,v) denote the distance between two vertices u,v in G. In this paper, it is proved: if the inequality d_G(u)+d_G(v)?|V(G)|-1 holds for each pair of vertices u and v with d_G(u,v)=2, then G is Hamiltonian, unless G belongs to an exceptional class of graphs. The latter class is described in this paper. Our result implies the theorem of Ore [Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55]. However, it is not included in the theorem of Fan [New sufficient conditions for cycles in graph, J. Combin. Theory Ser. B 37 (1984) 221-227].     

Generalization of matching extensions in graphs (II)

Proposed as a general framework, Liu and Yu [Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311-320.] introduced (n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,k and d be non-negative integers such that n+2k+d?|V(G)|-2 and |V(G)|-n-d is even. If when deleting any n vertices from G, the remaining subgraph H of G contains a k-matching and each such k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)-graph. Liu and Yu's Papee's paper, the recursive relations for distinct parameters n,k and d were presented and the impact of adding or deleting an edge also was discussed for the case d=0. In this paper, we continue the study begun by Liu and Yu and obtain new recursive results for (n,k,d)-graphs in the general case d?0.     

The Laplacian spectral radius of some bipartite graphs

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 K_1,k and one vertex of degree n of K_m,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.     

Distance Sequences In Locally Infinite Vertex-Transitive Digraphs

We prove that the out-distance sequence {f⁺(k)} of a vertex-transitive digraph of finite or infinite degree satisfies f⁺(k+1)≤f⁺(k)² for k≥1, where f⁺(k) denotes the number of vertices at directed distance k from a given vertex. As a corollary, we prove that for a connected vertex-transitive undirected graph of infinite degree d, we have f(k)=d for all k, 1≤k<diam(G). This answers a question by L. Babai.