Bounds for the Least Laplacian Eigenvalue of a Signed Graph

A signed graph is a graph with a sign attached to each edge. This paper extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the relationships between the least Laplacian eigenvalue and the unbalancedness of a signed graph are investigated.     

On the second largest Laplacian eigenvalues of graphs

The second largest Laplacian eigenvalue of a graph is the second largest eigenvalue of the associated Laplacian matrix. In this paper, we study extremal graphs for the extremal values of the second largest Laplacian eigenvalue and the Laplacian separator of a connected graph, respectively. All simple connected graphs with second largest Laplacian eigenvalue at most 3 are characterized. It is also shown that graphs with second largest Laplacian eigenvalue at most 3 are determined by their Laplacian spectrum. Moreover, the graphs with maximum and the second maximum Laplacian separators among all connected graphs are determined.     

双圈图的无符号拉普拉斯谱半径和谱展

The signless Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the smallest eigenvalue of its signless Laplacian matrix. In this paper, we determine the first to llth largest signless Laplacian spectral radii in the class of bicyclic graphs with n vertices. Moreover, the unique bicyclic graph with the largest or the second largest signless Laplacian spread among the class of connected bicyclic graphs of order n is determined, respectively.     

An eigenvalue bound for the Laplacian of a graph

We present a lower bound for the smallest non-zero eigenvalue of the Laplacian of an undirected graph. The bound is primarily useful for graphs with small diameter.     

双圈图的Laplace谱跨度

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. In our recent work, we have determined the graphs with maximal Laplacian spreads among all trees of fixed order and among all unicyclic graphs of fixed order, respectively. In this paper, we continue the work on Laplacian spread of graphs, and prove that there exist exactly two bicyclic graphs with maximal Laplacian spread among all bicyclic graphs of fixed order, which are obtained from a star by adding two incident edges and by adding two nonincident edges between the pendant vertices of the star, respectively.     

围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径

图的谱半径和Laplacian谱半径分别是图的邻接矩阵和Laplacian矩阵的最大特征值.本文中,我们分别刻画了围长为g且有k个悬挂点的单圈图的谱半径和Laplacian谱半径达到最大时的极图.     

The Laplacian spread of unicyclic 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. In a recent work the trees with maximal Laplacian spread and with minimal Laplacian spread among all trees of fixed order are separately determined. In this work, we characterize the unique unicyclic graph with maximal Laplacian spread among all connected unicyclic graphs of fixed order.     

The minimum Laplacian spread of unicyclic graphs

The Laplacian spread of a graph [1] is defined as the difference between the largest eigenvalue and the second-smallest eigenvalue of the associated Laplacian matrix. In this paper, the minimum Laplacian spread of unicyclic graphs with given order is determined.     

On the extremal values of the second largest Q-eigenvalue

We study extremal graphs for the extremal values of the second largest Q-eigenvalue of a connected graph. We first characterize all simple connected graphs with second largest signless Laplacian eigenvalue at most 3. The second part of the present paper is devoted to the study of the graphs that maximize the second largest Q-eigenvalue. We construct families of such graphs and prove that some of theses families are minimal for the fact that they maximize the second largest signless Laplacian eigenvalue.     

Some results on the Laplacian eigenvalues of unicyclic graphs

In this paper, we provide the smallest value of the second largest Laplacian eigenvalue for any unicyclic graph, and find the unicyclic graphs attaining that value. And also give an “asymptotically good” upper bounds for the second largest Laplacian eigenvalues of unicyclic graphs. Using this results, we can determine unicyclic graphs with maximum Laplacian separator. And unicyclic graphs with maximum Laplacian spread will also be determined.     

The Laplacian spectral radius of graphs

The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we improve Shi’s upper bound for the Laplacian spectral radius of irregular graphs and present some new bounds for the Laplacian spectral radius of some classes of graphs.     

A note on the second largest eigenvalue of the laplacian matrix of a graph ∗

In this note, a lower bound for the second largest eigenvalue of the Laplacian matrix of a graph is given in terms of the second largest degree of the graph.     

A note on the second largest eigenvalue of the laplacian matrix of a graph

In this note, a lower bound for the second largest eigenvalue of the Laplacian matrix of a graph is given in terms of the second largest degree of the graph.     

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.     

Connected signed graphs of fixed order,size, and number of negative edges with maximal index

In this paper we focus on connected signed graphs of fixed number of vertices, positive edges and negative edges that maximize the largest eigenvalue (also called the index) of their adjacency matrix. In the first step we determine these signed graphs in the set of signed generalized theta graphs. Concerning the general case, we use the eigenvector techniques for getting some structural properties of resulting signed graphs. In particular, we prove that positive edges induce nested split subgraphs, while negative edges induce double nested signed subgraphs. We observe that our concept can be applied when considering balancedness of signed graphs (the property that is extensively studied in both mathematical and non-mathematical context).     

拟树图按第二大无符号拉普拉斯特征值排序

A connected graph G=(V,E) is called a quasi-tree graph if there exists a vertex v_0∈V(G) such that G-v_0 is a tree.In this paper,we determine all quasi-tree graphs of order n with the second largest signless Laplacian eigenvalue greater than or equal to n-3.As an application,we determine all quasi-tree graphs of order n with the sum of the two largest signless Laplacian eigenvalues greater than to 2 n-5/4.     

Torsion formulas for signed graphs

Following our recent exposition on the algebraic foundations of signed graphs, we introduce bond (circuit) basis matrices for the tension (flow) lattices of signed graphs, and compute the torsions of such matrices and Laplacians. We present closed formulas for the torsions of the incidence matrix, the Laplacian, bond basis matrices, and circuit basis matrices. These formulas show that the torsions of all such matrices are powers of 2, and so imply that the matroids of signed graphs are representable over any field of characteristic not 2. A notable feature of using torsion is that the Matrix-Tree formula for ordinary graphs and Zaslavsky’s formula for unbalanced signed graphs are unified into one Matrix-Basis formula in terms of the torsion of its Laplacian matrix, rather than in terms of its determinant, which vanishes for an ordinary graph unless one row is deleted from the incidence matrix.     

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.     

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 .     

The largest two Laplacian eigenvalues of a graph

In this article, we present lower bounds for the largest eigenvalue, the second largest eigenvalue and the sum of the two largest eigenvalues of the Laplacian matrix of a graph.