Graphs whose normalized Laplacian has three eigenvalues

We give a combinatorial characterization of graphs whose normalized Laplacian has three distinct eigenvalues. Strongly regular graphs and complete bipartite graphs are examples of such graphs, but we also construct more exotic families of examples from conference graphs, projective planes, and certain quasi-symmetric designs.     

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.     

On graphs with three distinct Laplacian eigenvalues

In this paper,an equivalent condition of a graph G with t(2≤t≤n)distinct Laplacian eigenvalues is established.By applying this condition to t=3,if G is regular(neces- sarily be strongly regular),an equivalent condition of G being Laplacian integral is given.Also for the case of t=3,if G is non-regular,it is found that G has diameter 2 and girth at most 5 if G is not a tree.Graph G is characterized in the case of its being triangle-free,bipartite and pentagon-free.In both cases,G is Laplacian integral.     

A note on the signless Laplacian eigenvalues of graphs

In this paper, we consider the signless Laplacians of simple graphs and we give some eigenvalue inequalities. We first consider an interlacing theorem when a vertex is deleted. In particular, let G-v be a graph obtained from graph G by deleting its vertex v and κ_i(G) be the ith largest eigenvalue of the signless Laplacian of G, we show that κ_i+1(G)-1?κ_i(G-v)?κ_i(G). Next, we consider the third largest eigenvalue κ₃(G) and we give a lower bound in terms of the third largest degree d₃ of the graph G. In particular, we prove that . Furthermore, we show that in several situations the latter bound can be increased to d₃-1.     

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

Graph properties for splitting with grounded Laplacian matrices

With any undirected, connected graphG containing no self-loops one can associate the Laplacian matrixL(G). It is also the (singular) admittance matrix of a resistive network with all conductances taken to be unity. While solving the linear system involved, one of the vertices is grounded, so the coefficient matrix is a principal submatrix ofL which we will call the grounded Laplacian matrixL ₁. In this paper we consider iterative solutions of such linear systems using certain regular splittings ofL ₁ and derive an upper bound for the spectral radius of the iteration matrix in terms of the properties of the graphG.This work was supported by the Academy of Finland     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

On products and line graphs of signed graphs, their eigenvalues and energy

In this article we examine the adjacency and Laplacian matrices and their eigenvalues and energies of the general product (non-complete extended p-sum, or NEPS) of signed graphs. We express the adjacency matrix of the product in terms of the Kronecker matrix product and the eigenvalues and energy of the product in terms of those of the factor graphs. For the Cartesian product we characterize balance and compute expressions for the Laplacian eigenvalues and Laplacian energy. We give exact results for those signed planar, cylindrical and toroidal grids which are Cartesian products of signed paths and cycles.We also treat the eigenvalues and energy of the line graphs of signed graphs, and the Laplacian eigenvalues and Laplacian energy in the regular case, with application to the line graphs of signed grids that are Cartesian products and to the line graphs of all-positive and all-negative complete graphs.     

On split graphs with three or four distinct (normalized) Laplacian eigenvalues

It is well known to us that a graph of diameter $l$ has at least $l+1$ eigenvalues. A graph is said to be Laplacian (resp, normalized Laplacian) $l$‐extremal if it is of diameter $l$ having exactly $l+1$ distinct Laplacian (resp, normalized Laplacian) eigenvalues. A graph is split if its vertex set can be partitioned into a clique and a stable set. Each split graph is of diameter at most 3. In this paper, we completely classify the connected bidegreed Laplacian (resp, normalized Laplacian) 2‐extremal (resp, 3‐extremal) split graphs using the association of split graphs with combinatorial designs. Furthermore, we identify connected bidegreed split graphs of diameter 2 having just four Laplacian (resp, normalized Laplacian) eigenvalues.     

On bipartite graphs with small number of laplacian eigenvalues greater than two and three

All connected bipartite graphs with exactly two Laplacian eigenvalues greater than two are determined. Besides, all connected bipartite graphs with exactly one Laplacian eigenvalue greater than three are determined.     

On upper bounds for Laplacian graph eigenvalues

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

     

On limit points of Laplacian spectral radii of graphs

The study of limit points of eigenvalues of adjacency matrices of graphs was initiated by Hoffman [A.J. Hoffman, On limit points of spectral radii of non-negative symmetric integral matrices, in: Y. Alavi et al. (Eds.), Lecture Notes Math., vol. 303, Springer-Verlag, Berlin, Heidelberg, New York, 1972, pp. 165-172]. There he described all of the limit points of the largest eigenvalue of adjacency matrices of graphs that are no more than . In this paper, we investigate limit points of Laplacian spectral radii of graphs. The result is obtained: Let , β₀=1 and be the largest positive root of

     

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.     

Bounding the gap between extremal Laplacian eigenvalues of graphs

Let G be a graph whose Laplacian eigenvalues are 0 = λ₁ ? λ₂ ? ? ? λ_n. We investigate the gap (expressed either as a difference or as a ratio) between the extremal non-trivial Laplacian eigenvalues of a connected graph (that is λ_n and λ₂). This gap is closely related to the average density of cuts in a graph. We focus here on the problem of bounding the gap from below.     

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.     

Large families of laplacian isospectral graphs

Two graphs are isomorphic only if they are Laplacian isospectral, that is, their Laplacian matrices share the same multiset of eigenvalues. Large families of nonisomorphic Laplacian isospectral graphs are exhibited for which the common multiset of eigenvalues consists entirely of integers.     

Large families of laplacian isospectral graphs

Two graphs are isomorphic only if they are Laplacian isospectral, that is, their Laplacian matrices share the same multiset of eigenvalues. Large families of nonisomorphic Laplacian isospectral graphs are exhibited for which the common multiset of eigenvalues consists entirely of integers.