On the characteristic and Laplacian polynomials of trees

We find the characteristic polynomials of adjacency and Laplacian matrices of arbitrary unweighted rooted trees in term of vertex degrees, using the concept of the rooted product of graphs. Our result generalizes a result of 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] on a special class of rooted unweighted trees, namely the trees such that their vertices in the same level have equal degrees.     

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.     

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

Commutativity of the adjacency matrices of graphs

We say that two graphs G₁ and G₂ with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers n such that the complete bipartite graph K_n,n is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most n−1 linearly independent commuting adjacency matrices of size n; and if this bound occurs, then there exists a Hadamard matrix of order n. Finally, we determine the centralizers of some families of graphs.     

On the characteristic polynomial of the adjacency matrix of the subdivision graph of a graph

The characteristic polynomial of the adjacency matrix of the subdivision graph G is related to the characteristic polynomials of the adjacency matrices of g and its line graph.     

Characteristic polynomial of a generalized complete product of matrices

For a simple graph G, let denote the complement of G relative to the complete graph and let P_G(x)=det(xI-A(G)) where A(G) denotes the adjacency matrix of G. The complete product G∇H of two simple graphs G and H is the graph obtained from G and H by joining every vertex of G to every vertex of H. In [2]P_G∇H(x) is represented in terms of P_G, , P_H and . In this paper we extend the notion of complete product of simple graphs to that of generalized complete product of matrices and obtain their characteristic polynomials.     

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.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

The lollipop graph is determined by its Q-spectrum

A graph G is said to be determined by its Q-spectrum if with respect to the signless Laplacian matrix Q, any graph having the same spectrum as G is isomorphic to G. The lollipop graph, denoted by H_n,p, is obtained by appending a cycle C_p to a pendant vertex of a path P_n−p. In this paper, it is proved that all lollipop graphs are determined by their Q-spectra.     

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.     

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.     

A relation between the Laplacian and signless Laplacian eigenvalues of a graph

Let G be a graph of order n such that \(\sum_{i=0}^{n}(-1)^{i}a_{i}\lambda^{n-i}\) and \(\sum_{i=0}^{n}(-1)^{i}b_{i}\lambda^{n-i}\) are the characteristic polynomials of the signless Laplacian and the Laplacian matrices of G, respectively. We show that a _i ≥b _i for i=0,1,…,n. As a consequence, we prove that for any α, 0<α≤1, if q ₁,…,q _n and μ ₁,…,μ _n are the signless Laplacian and the Laplacian eigenvalues of G, respectively, then \(q_{1}^{\alpha}+\cdots+q_{n}^{\alpha}\geq\mu_{1}^{\alpha}+\cdots+\mu _{n}^{\alpha}\).     

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].     

Bi-resolving Graph Homomorphisms and Extensions of Bi-closing codes

Given two graphs G and H, there is a bi-resolving (or bi-covering) graph homomorphism from G to H if and only if their adjacency matrices satisfy certain matrix relations. We investigate the bi-covering extensions of bi-resolving homomorphisms and give several sufficient conditions for a bi-resolving homomorphism to have a bi-covering extension with an irreducible domain. Using these results, we prove that a bi-closing code between subshifts can be extended to an n-to-1 code between irreducible shifts of finite type for all large n.     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

The largest eigenvalue of unicyclic graphs

Let G be a simple graph. Let λ₁(G) and μ₁(G) denote the largest eigenvalue of the adjacency matrix and the Laplacian matrix of G, respectively. Let Δ denote the largest vertex degree. If G has just one cycle, then

     

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.     

On the construction of cospectral nonisomorphic bipartite graphs

In this article, we construct bipartite graphs which are cospectral for both the adjacency and normalized Laplacian matrices using the notion of partitioned tensor products. This extends the construction of Ji, Gong, and Wang [9]. Our proof of the cospectrality of adjacency matrices simplifies the proof of the bipartite case of Godsil and McKay's construction [4], and shows that the corresponding normalized Laplacian matrices are also cospectral. We partially characterize the isomorphism in Godsil and McKay's construction, and generalize Ji et al.'s characterization of the isomorphism to biregular bipartite graphs. The essential idea in characterizing the isomorphism uses Hammack's cancellation law as opposed to Hall's marriage theorem used by Ji et al.     

On conjectures involving second largest signless Laplacian eigenvalue of graphs

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.