Line graph of combinations of generalized Bethe trees: Eigenvalues and energy

We characterize the eigenvalues and energy of the line graph L(G) whenever G is (i) a generalized Bethe tree, (ii) a Bethe tree, (iii) a tree defined by generalized Bethe trees attached to a path, (iv) a tree defined by generalized Bethe trees having a common root, (v) a graph defined by copies of a generalized Bethe tree attached to a cycle and (vi) a graph defined by copies of a star attached to a cycle; in this case, explicit formulas for the eigenvalues and energy of L(G) are derived.     

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.     

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 upper bounds for Laplacian graph eigenvalues

In this paper, we obtain the following upper bound for the largest Laplacian graph eigenvalue λ(G):

     

The spectral radii of a graph and its line graph

The spectral radius of a (directed) graph is the largest eigenvalue of adjacency matrix of the (directed) graph. We give the relation on the characteristic polynomials of a directed graph and its line graph, and obtain sharp bounds on the spectral radius of directed graphs. We also give the relation on the spectral radii of a graph and its line graph. As a consequence, the spectral radius of a connected graph does not exceed that of its line graph except that the graph is a path.     

Energy of line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. The energy of a matrix is equal to the sum of its singular values. We establish relations between the energy of the line graph of a graph G and the energies associated with the Laplacian and signless Laplacian matrices of G.     

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.     

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.     

Spectra of generalized Bethe trees attached to a path

A generalized Bethe tree is a rooted tree in which vertices at the same distance from the root have the same degree. Let P_m be a path of m vertices. Let {B_i:1?i?m} be a set of generalized Bethe trees. Let P_m{B_i:1?i?m} be the tree obtained from P_m and the trees B₁,B₂,…,B_m by identifying the root vertex of B_i with the i-th vertex of P_m. We give a complete characterization of the eigenvalues of the Laplacian and adjacency matrices of P_m{B_i:1?i?m}. In particular, we characterize their spectral radii and the algebraic conectivity. Moreover, we derive results concerning their multiplicities. Finally, we apply the results to the case B₁=B₂=…=B_m.     

Laplacian energy of a graph

Let G be a graph with n vertices and m edges. Let λ₁, λ₂, … , λ_n be the eigenvalues of the adjacency matrix of G, and let μ₁, μ₂, … , μ_n be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences.     

Zeta functions of line, middle, total graphs of a graph and their coverings

We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G.     

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.     

New upper bounds on the spectral radius of unicyclic graphs

Let G=(V(G),E(G)) be a unicyclic simple undirected graph with largest vertex degree Δ. Let C_r be the unique cycle of G. The graph G-E(C_r) is a forest of r rooted trees T₁,T₂,…,T_r with root vertices v₁,v₂,…,v_r, respectively. Let

     

Large matchings from eigenvalues

We find lower bounds on the difference between the spectral radius λ₁ and the average degree of an irregular graph G of order n and size e. In particular, we show that, if n ? 4, then

     

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.

     

Interlacing eigenvalues on some operations of graphs

In this paper, we focus on some operations of graphs and give a kind of eigenvalue interlacing in terms of the adjacency matrix, standard Laplacian, and normalized Laplacian. Also, we explore some applications of this interlacing.     

Perturbing non-real eigenvalues of non-negative real matrices

Let σ=(ρ,b+ic,b-ic,λ₄,…,λ_n) be the spectrum of an entry non-negative matrix and t?0. Laffey [T. J. Laffey, Perturbing non-real eigenvalues of nonnegative real matrices, Electron. J. Linear Algebra 12 (2005) 73-76] has shown that σ=(ρ+2t,b-t+ic,b-t-ic,λ₄,…,λ_n) is also the spectrum of some nonnegative matrix. Laffey (2005) has used a rank one perturbation for small t and then used a compactness argument to extend the result to all nonnegative t. In this paper, a rank two perturbation is used to deduce an explicit and constructive proof for all t?0.     

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.     

Potentially nilpotent and spectrally arbitrary even cycle sign patterns

An n × n sign pattern S_n is potentially nilpotent if there is a real matrix having sign pattern S_n and characteristic polynomial xⁿ. A new family of sign patterns C_n with a cycle of every even length is introduced and shown to be potentially nilpotent by explicitly determining the entries of a nilpotent matrix with sign pattern C_n. These nilpotent matrices are used together with a Jacobian argument to show that C_n is spectrally arbitrary, i.e., there is a real matrix having sign pattern C_n and characteristic polynomial for any real μ_i. Some results and a conjecture on minimality of these spectrally arbitrary sign patterns are given.