On the Laplacian spectral radii of bipartite graphs

The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we provide structural and behavioral details of graphs with maximum Laplacian spectral radius among all bipartite connected graphs of given order and size. Using these results, we provide a unified approach to determine the graphs with maximum Laplacian spectral radii among all trees, and all bipartite unicyclic, bicyclic, tricyclic and quasi-tree graphs, respectively.     

On the spectral radii and the signless Laplacian spectral radii of c-cyclic graphs with fixed maximum degree

If G is a connected undirected simple graph on n vertices and n+c-1 edges, then G is called a c-cyclic graph. Specially, G is called a tricyclic graph if c=3. Let Δ(G) be the maximum degree of G. In this paper, we determine the structural characterizations of the c-cyclic graphs, which have the maximum spectral radii (resp. signless Laplacian spectral radii) in the class of c-cyclic graphs on n vertices with fixed maximum degree . Moreover, we prove that the spectral radius of a tricyclic graph G strictly increases with its maximum degree when , and identify the first six largest spectral radii and the corresponding graphs in the class of tricyclic graphs on n vertices.     

On the distance and distance signless Laplacian spectral radii of bicyclic graphs

The unique graphs with minimum and second-minimum distance (distance signless Laplacian, respectively) spectral radii are determined among bicyclic graphs with fixed number of vertices.     

Laplacian spectral characterization of 3-rose graphs

A 3-rose graph is a graph consisting of three cycles intersecting in a common vertex, J. Wang et al. showed all 3-rose graphs with at least one triangle are determined by their Laplacian spectra. In this paper, we complete the above Laplacian spectral characterization and prove that all 3-rose graphs are determined by their Laplacian spectra.     

The Laplacian spectral radii of trees with degree sequences

In this paper, we characterize all extremal trees with the largest Laplacian spectral radius in the set of all trees with a given degree sequence. Consequently, we also obtain all extremal trees with the largest Laplacian spectral radius in the sets of all trees of order n with the largest degree, the leaves number and the matching number, respectively.     

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.     

The Laplacian spectral radius for unicyclic graphs with given independence number

In this paper, we give a complete characterization of the extremal graphs with maximal Laplacian spectral radius among all unicyclic graphs with given order and given number of pendent vertices. Then we study the Laplacian spectral radius of unicyclic graphs with given independence number and characterize the extremal graphs completely.     

Laplacian and signless Laplacian spectral radii of graphs with fixed domination number

We determine the maximal Laplacian and signless Laplacian spectral radii for graphs with fixed number of vertices and domination number, and characterize the extremal graphs.     

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.     

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.     

A sharp upper bound on the signless Laplacian spectral radius of graphs

Let G be a simple connected graph of order n   with degree sequence _d1,_d2,…,_dn$d_1,d_2,\dots ,d_n$ in non-increasing order. The signless Laplacian spectral radius ρ(Q(G))$\rho (Q(G))$ of G   is the largest eigenvalue of its signless Laplacian matrix Q(G)$Q(G)$. In this paper, we give a sharp upper bound on the signless Laplacian spectral radius ρ(Q(G))$\rho (Q(G))$ in terms of _di$d_i$, which improves and generalizes some known results.     

The smallest signless Laplacian spectral radius of graphs with a given clique number

The signless Laplacian spectral radius of a graph G is the largest eigenvalue of its signless Laplacian matrix. In this paper, the first four smallest values of the signless Laplacian spectral radius among all connected graphs with maximum clique of size greater than or equal to 2 are obtained.     

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.     

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.     

Graphs whose signless Laplacian spectral radius does not exceed the Hoffman limit value

For a graph matrix M, the Hoffman limit value H(M) is the limit (if it exists) of the largest eigenvalue (or, M-index, for short) of M(H_n), where the graph H_n is obtained by attaching a pendant edge to the cycle C_n-1 of length n-1. In spectral graph theory, M is usually either the adjacency matrix A or the Laplacian matrix L or the signless Laplacian matrix Q. The exact values of H(A) and H(L) were first determined by Hoffman and Guo, respectively. Since H_n is bipartite for odd n, we have H(Q)=H(L). All graphs whose A-index is not greater than H(A) were completely described in the literature. In the present paper, we determine all graphs whose Q-index does not exceed H(Q). The results obtained are determinant to describe all graphs whose L-index is not greater then H(L). This is done precisely in Wang et al. (in press) [21].     

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.     

Extremal graph characterization from the upper bound of the Laplacian spectral radius of weighted graphs

We consider weighted graphs, where the edge weights are positive definite matrices. In this paper, we obtain two upper bounds on the spectral radius of the Laplacian matrix of weighted graphs and characterize graphs for which the bounds are attained. Moreover, we show that some known upper bounds on the Laplacian spectral radius of weighted and unweighted graphs can be deduced from our upper bounds.