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.     

Towards a spectral theory of graphs based on the signless Laplacian, II

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.     

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.     

Graphs with maximal signless Laplacian spectral radius

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. It is known that connected graphs G that maximize the signless Laplacian spectral radius ρ(Q(G)) over all connected graphs with given numbers of vertices and edges are (degree) maximal. For a maximal graph G with n vertices and r distinct vertex degrees δ_r>δ_r-1>?>δ₁, it is proved that ρ(Q(G))<ρ(Q(H)) for some maximal graph H with n+1 (respectively, n) vertices and the same number of edges as G if either G has precisely two dominating vertices or there exists an integer such that δ_i+δ_r+1-i?n+1 (respectively, δ_i+δ_r+1-i?δ_l+δ_r-l+1). Graphs that maximize ρ(Q(G)) over the class of graphs with m edges and m-k vertices, for k=0,1,2,3, are completely determined.     

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.     

Unicyclic graphs with bicyclic inverses

A graph is nonsingular if its adjacency matrix A(G) is nonsingular. The inverse of a nonsingular graph G is a graph whose adjacency matrix is similar to A(G)^?1 via a particular type of similarity. Let H denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in H which possess unicyclic inverses. We present a characterization of unicyclic graphs in H which possess bicyclic inverses.     

The Laplacian spread of quasi-tree graphs

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 .     

Some further bounds for the Q-index of nested split graphs

The Q-index of a simple graph is the largest eigenvalue of its signless Laplacian, or Q-matrix. In our previous paper [1] we gave three lower and three upper bounds for the Q-index of nested split graphs, also known as threshold graphs. In this paper, we give another two upper bounds, which are expressed as solutions of cubic equations (in contrast to quadratics from [1]). Some computational results are also included.     

On spectral characterizations and embeddings of graphs

The least eigenvalue of the 0-1 adjacency matrix of a graph is denoted λ G. In this paper all graphs with λ(G) greater than ?2 are characterized. Such a graph is a generalized line graph of the form L(T;1,0,…,0), L(T), L(H), where T is a tree and H is unicyclic with an odd cycle, or is one of 573 graphs that arise from the root system E₈. If G is regular with λ(G)>?2, then Gis a clique or an odd circuit. These characterizations are used for embedding problems; λ_R(H) = sup{λ(G)z.sfnc;HinG; Gregular}. H is an odd circuit, a path, or a complete graph iff λ_R(H)> ?2. For any other line graph H, λ_R(H) = ?2. A similar result holds for complete multipartite graphs.     

On the signless Laplacian spectral characterization of the line graphs of T-shape trees

A graph is determined by its signless Laplacian spectrum if no other nonisomorphic graph has the same signless Laplacian spectrum (simply G is DQS). Let T (a, b, c) denote the T-shape tree obtained by identifying the end vertices of three paths P _a+2, P _b+2 and P _c+2. We prove that its all line graphs L(T(a, b, c)) except L(T(t, t, 2t+1)) (t ? 1) are DQS, and determine the graphs which have the same signless Laplacian spectrum as L(T(t, t, 2t + 1)). Let µ₁(G) be the maximum signless Laplacian eigenvalue of the graph G. We give the limit of µ₁(L(T(a, b, c))), too.     

On the polynomial of a path

Let A(P_n) be the adjacency matrix of the path on n vertices. Suppose that r(λ) is a polynomial of degree less than n, and consider the matrix M = r(A>/(P_n)). We determine all polynomials for which M is the adjacency matrix of a graph.     

Trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues

The signless Laplacian matrix of a graph G is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called Q-eigenvalues of G. A Q-eigenvalue of a graph G is called a Q-main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. In this work, all trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues are determined.     

Bounds on the index of the signless Laplacian of a graph

Let G=(V,E) be a simple, undirected graph of order n and size m with vertex set V, edge set E, adjacency matrix A and vertex degrees Δ=d₁≥d₂≥?≥d_n=δ. The average degree of the neighbor of vertex v_i is . Let D be the diagonal matrix of degrees of G. Then L(G)=D(G)−A(G) is the Laplacian matrix of G and Q(G)=D(G)+A(G) the signless Laplacian matrix of G. Let μ₁(G) denote the index of L(G) and q₁(G) the index of Q(G). We survey upper bounds on μ₁(G) and q₁(G) given in terms of the d_i and m_i, as well as the numbers of common neighbors of pairs of vertices. It is well known that μ₁(G)≤q₁(G). We show that many but not all upper bounds on μ₁(G) are still valid for q₁(G).     

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.     

The Laplacian energy of random graphs

Gutman et al. introduced the concepts of energy E(G) and Laplacian energy EL(G) for a simple graph G, and furthermore, they proposed a conjecture that for every graph G, E(G) is not more than EL(G). Unfortunately, the conjecture turns out to be incorrect since Liu et al. and Stevanovi? et al. constructed counterexamples. However, So et al. verified the conjecture for bipartite graphs. In the present paper, we obtain, for a random graph, the lower and upper bounds of the Laplacian energy, and show that the conjecture is true for almost all graphs.     

Strongly self-dual graphs

We present a class of graphs whose adjacency matrices are nonsingular with integral inverses, denoted h-graphs. If the h-graphs G and H with adjacency matrices M(G) and M(H) satisfy M(G)^-1=SM(H)S, where S is a signature matrix, we refer to H as the dual of G. The dual is a type of graph inverse. If the h-graph G is isomorphic to its dual via a particular isomorphism, we refer to G as strongly self-dual. We investigate the structural and spectral properties of strongly self-dual graphs, with a particular emphasis on identifying when such a graph has 1 as an 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.     

Abelian group matrices over the p-adic and rational integers

Let G be a finite abelian group of order n. Let Z and Q denote the rational integers and rationals, respectively. A group matrix for G over Z (or Q) is an n-square matrix of the form Σ_{g ∈ G}a_gP(g), where a_g ∈ Z (or Q) and P is the regular representation of G so that P(g) is an n-square permutation matrix and P(gh) = P(g)P(h) for all g, h ∈ G. It is known that if M is an arbitrary positive definite unimodular matrix over Z then there exists a matrix A over Q such that M = A^τA, where τ denotes transposition. This paper proves that the exact analogue of this theorem holds if one demands that M and A be group matrices for G over Z and Q, respectively. Furthermore, if M is a group matrix for G over the p-adic integers then necessary and sufficient conditions are given for the existence of a group matrix A for G over the p-adic numbers such that M = A^τA.     

On the spectral characterization of some unicyclic graphs

Let H(n;q,n₁,n₂) be a graph with n vertices containing a cycle C_q and two hanging paths P_n1 and P_n2 attached at the same vertex of the cycle. In this paper, we prove that except for the A-cospectral graphs H(12;6,1,5) and H(12;8,2,2), no two non-isomorphic graphs of the form H(n;q,n₁,n₂) are A-cospectral. It is proved that all graphs H(n;q,n₁,n₂) are determined by their L-spectra. And all graphs H(n;q,n₁,n₂) are proved to be determined by their Q-spectra, except for graphs with a being a positive even number and with b≥4 being an even number. Moreover, the Q-cospectral graphs with these two exceptions are given.