Q‐integral unicyclic,bicyclic and tricyclic graphs

A graph is called Q‐integral if its signless Laplacian spectrum consists of integers. In this paper, we characterize a class of k‐cyclic graphs whose second smallest signless Laplacian eigenvalue is less than one. Using this result we determine all the Q‐integral unicyclic, bicyclic and tricyclic graphs.     

恰有两个Q-主特征值的三圈图

图G的无符号拉普拉斯矩阵定义为图G的邻接矩阵与度对角矩阵的和,其特征值称为图G的Q-特征值.图G的一个Q-特征值称为Q-主特征值,如果它有一个特征向量其分量的和不等于零.确定了所有恰有两个Q-主特征值的三圈图.     

Split non-threshold Laplacian integral graphs

The aim of this article is to answer a question posed by Merris in European Journal of Combinatorics, 24 (2003) pp. 413 ? 430, about the possibility of finding split non-threshold graphs that are Laplacian integral, i.e. graphs for which the eigenvalues of the corresponding Laplacian matrix are integers. Using Kronecker products, balanced incomplete block designs, and solutions to certain Diophantine equations, we show how to build infinite families of these graphs.     

给定围长的三圈图的无符号拉普拉斯谱半径

A tricyclic graph G =（V（G）, E（G）） is a connected and simple graph such that｜E（G）｜ = ｜V（G）｜＋2. Let Tg nbe the set of all tricyclic graphs on n vertices with girth g. In this paper, we will show that there exists the unique graph which has the largest signless Laplacian spectral radius among all tricyclic graphs with girth g containing exactly three（resp., four）cycles. And at the same time, we also give an upper bound of the signless Laplacian spectral radius and the extremal graph having the largest signless Laplacian spectral radius in Tg n,where g is even.     

On graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Constructably Laplacian integral graphs

A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. We consider the class of constructably Laplacian integral graphs - those graphs that be constructed from an empty graph by adding a sequence of edges in such a way that each time a new edge is added, the resulting graph is Laplacian integral. We characterize the constructably Laplacian integral graphs in terms of certain forbidden vertex-induced subgraphs, and consider the number of nonisomorphic Laplacian integral graphs that can be constructed by adding a suitable edge to a constructably Laplacian integral graph. We also discuss the eigenvalues of constructably Laplacian integral graphs, and identify families of isospectral nonisomorphic graphs within the class.     

On the Laplacian energy of a graph

In this paper we consider the energy of a simple graph with respect to its Laplacian eigenvalues, and prove some basic properties of this energy. In particular, we find the minimal value of this energy in the class of all connected graphs on n vertices (n = 1, 2, ...). Besides, we consider the class of all connected graphs whose Laplacian energy is uniformly bounded by a constant α ⩾ 4, and completely describe this class in the case α = 40.     

几类多圈图的拉普拉斯谱刻画

设图G是一个简单连通图.如果任何一个与图G同拉普拉斯谱的图都与图G同构,则称图G是由其拉普拉斯谱确定的.定义了双圈图θ_n(p_1,p_2,…,p_t)和m圈图H_n(m·C_3;p_1,p_2,…,p_t).证明了双圈图θ_n(p)和θ_n(p,q),三圈图H_n(3·C_3;p)和H_n(3·C_3;p,q)分别是由它们的拉普拉斯谱确定的.     

Some constructions of integral graphs

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. Integral graphs are very rare and difficult to find. In this article, we introduce some general methods for constructing such graphs. As a consequence, some infinite families of integral graphs are obtained.