On the characteristic polynomial of a special class of graphs and spectra of balanced trees

Let H be a simple graph with n vertices and G be a sequence of n rooted graphs G₁,G₂,…,G_n. Godsil and McKay [C.D. Godsil, B.D. McKay, A new graph product and its spectrum, Bull. Austral. Math. Soc. 18 (1978) 21-28] defined the rooted product H(G), of H by G by identifying the root vertex of G_i with the ith vertex of H, and determined the characteristic polynomial of H(G). In this paper we prove a general result on the determinants of some special matrices and, as a corollary, determine the characteristic polynomials of adjacency and Laplacian matrices of H(G).Rojo and Soto [O. Rojo, R. Soto, The spectra of the adjacency matrix and Laplacian matrix for some balanced trees, Linear Algebra Appl. 403 (2005) 97-117] computed the characteristic polynomials and the spectrum of adjacency and Laplacian matrices of a class of balanced trees. As an application of our results, we obtain their conclusions by a simple method.     

图的无号Laplace矩阵的最大特征值

The signless Laplacian matrix of a graph is the sum of its diagonal matrix of vertex degrees and its adjacency matrix. Li and Feng gave some basic results on the largest eigenvalue and characteristic polynomial of adjacency matrix of a graph in 1979. In this paper, we translate these results into the signless Laplacian matrix of a graph and obtain the similar results.     

围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径

图的谱半径和Laplacian谱半径分别是图的邻接矩阵和Laplacian矩阵的最大特征值.本文中,我们分别刻画了围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径达到最大时的极图.     

On a signless Laplacian spectral characterization of -shape trees

Let M be an associated matrix of a graph G (the adjacency, Laplacian and signless Laplacian matrix). Two graphs are said to be cospectral with respect to M if they have the same M spectrum. A graph is said to be determined by M spectrum if there is no other non-isomorphic graph with the same spectrum with respect to M. It is shown that T-shape trees are determined by their Laplacian spectra. Moreover among them those are determined by their adjacency spectra are characterized. In this paper, we identify graphs which are cospectral to a given T-shape tree with respect to the signless Laplacian matrix. Subsequently, T-shape trees which are determined by their signless Laplacian spectra are identified.     

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.     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

On the weighted trees with given degree sequence and positive weight set

We determine the (unique) weighted tree with the largest spectral radius with respect to the adjacency and Laplacian matrix in the set of all weighted trees with a given degree sequence and positive weight set. Moreover, we also derive the weighted trees with the largest spectral radius with respect to the matrices mentioned above in the sets of all weighted trees with a given maximum degree or pendant vertex number and so on.     

Spectra of graphs obtained by a generalization of the join graph operation

Taking a Fiedler’s result on the spectrum of a matrix formed from two symmetric matrices as a motivation, a more general result is deduced and applied to the determination of adjacency and Laplacian spectra of graphs obtained by a generalized join graph operation on families of graphs (regular in the case of adjacency spectra and arbitrary in the case of Laplacian spectra). Some additional consequences are explored, namely regarding the largest eigenvalue and algebraic connectivity.     

Semiregular trees with minimal Laplacian spectral radius

A semiregular tree is a tree where all non-pendant vertices have the same degree. Among all semiregular trees with fixed order and degree, a graph with minimal (adjacency/Laplacian) spectral radius is a caterpillar. Counter examples show that the result cannot be generalized to the class of trees with a given (non-constant) degree sequence.     

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 Laplacian coefficients of graphs under some transformations

We generalize three approaches on graph transformations, respectively, from Stevanovi? and Ili? (2009) [16] and Tan (2011) [19]. We also generalize an approach of graph transformations on the spectral radius of adjacency matrix into the Laplacian coefficients of graphs from Li and Feng (1979) [26]. Moreover, we determine the unique tree having the third maximal Laplacian coefficients among all n-vertex trees.     

A sharp upper bound for the spectral radius of a nonnegative matrix and applications

We obtain a sharp upper bound for the spectral radius of a nonnegative matrix. This result is used to present upper bounds for the adjacency spectral radius, the Laplacian spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance Laplacian spectral radius, the distance signless Laplacian spectral radius of an undirected graph or a digraph. These results are new or generalize some known results.     

Bounds for the signless Laplacian energy

The energy of a graph G is the sum of the absolute values of the eigenvalues of the adjacency matrix of G. The Laplacian (respectively, the signless Laplacian) energy of G is the sum of the absolute values of the differences between the eigenvalues of the Laplacian (respectively, signless Laplacian) matrix and the arithmetic mean of the vertex degrees of the graph. In this paper, among some results which relate these energies, we point out some bounds to them using the energy of the line graph of G. Most of these bounds are valid for both energies, Laplacian and signless Laplacian. However, we present two new upper bounds on the signless Laplacian which are not upper bounds for the Laplacian energy.     

The spectral characterization of graphs of index less than 2 with no path as a component

A graph is said to be determined by the adjacency and Laplacian spectrum (or to be a DS graph, for short) if there is no other non-isomorphic graph with the same adjacency and Laplacian spectrum, respectively. It is known that connected graphs of index less than 2 are determined by their adjacency spectrum. In this paper, we focus on the problem of characterization of DS graphs of index less than 2. First, we give various infinite families of cospectral graphs with respect to the adjacency matrix. Subsequently, the results will be used to characterize all DS graphs (with respect to the adjacency matrix) of index less than 2 with no path as a component. Moreover, we show that most of these graphs are DS with respect to the Laplacian matrix.     

Spectra of Corona Based on the Total Graph

For two simple connected graphs $G_1$ and $G_2$, we introduce a new graph operation called the total corona $G_1⊛G_2$ on $G_1$ and $G_2$ involving the total graph of $G_1.$ Subsequently, the adjacency (respectively, Laplacian and signless Laplacian) spectra of $G_1⊛G_2$ are determined in terms of these of a regular graph $G_1$ and an arbitrary graph $G_2.$ As applications, we construct infinitely many pairs of adjacency (respectively, Laplacian and signless Laplacian) cospectral graphs. Besides we also compute the number of spanning trees of $G_1⊛G_2.$     

On the spectra of certain rooted trees

Let T be an unweighted tree with vertex root v which is the union of two trees T₁=(V₁,E₁), T₂=(V₂,E₂) such that V₁ ∩ V₂ = {v} and T₁ and T₂ have the property that the vertices in each of their levels have equal degree. We characterize completely the eigenvalues of the adjacency matrix and of the Laplacian matrix of T. They are the eigenvalues of symmetric tridiagonal matrices whose entries are given in terms of the vertex degrees. Moreover, we give some results about the multiplicity of the eigenvalues. Applications to some particular trees are developed.     

给定最大度的树的最大谱半径

In this paper, we characterize the trees with the largest Laplacian and adjacency spectral radii among all trees with fixed number of vertices and fixed maximal degree, respectively.     

The perturbed laplacian matrix of a graph

For a graph G, we define its perturbed Laplacian matrix as D?A(G) where A(G) is the adjacency matrix of G and D is an arbitrary diagonal matrix. Both the Laplacian matrix and the negative of the adjacency matrix are special instances of the perturbed Laplacian. Several well-known results, contained in the classical work of Fiedler and in more recent contributions of other authors are shown to be true, with suitable modifications, for the perturbed Laplacian. An appropriate generalization of the monotonicity property of a Fiedler vector for a tree is obtained. Some of the results are applied to interval graphs.     

Signless Laplacians of finite graphs

We survey properties of spectra of signless Laplacians of graphs and discuss possibilities for developing a spectral theory of graphs based on this matrix. For regular graphs the whole existing theory of spectra of the adjacency matrix and of the Laplacian matrix transfers directly to the signless Laplacian, and so we consider arbitrary graphs with special emphasis on the non-regular case. The results which we survey (old and new) are of two types: (a) results obtained by applying to the signless Laplacian the same reasoning as for corresponding results concerning the adjacency matrix, (b) results obtained indirectly via line graphs. Among other things, we present eigenvalue bounds for several graph invariants, an interpretation of the coefficients of the characteristic polynomial, a theorem on powers of the signless Laplacian and some remarks on star complements.