On the Laplacian integral tricyclic graphs

A graph is called Laplacian integral if all its Laplacian eigenvalues are integers. In this paper, we give an edge subdividing theorem for Laplacian eigenvalues of a graph (Theorem 2.1) and characterize a class of k-cyclic graphs whose algebraic connectivity is less than one. Using these results, we determine all the Laplacian integral tricyclic graphs. Furthermore, we show that all the Laplacian integral tricyclic graphs are determined by their Laplacian spectra.     

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

Indecomposable laplacian integral graphs

A graph that can be constructed from isolated vertices by the operations of union and complement is decomposable. Every decomposable graph is Laplacian integral. i.e., its Laplacian spectrum consists entirely of integers. An indecomposable graph is not decomposable. The main purpose of this note is to demonstrate the existence of infinitely many indecomposable Laplacian integral graphs.     

Laplacian integral graphs in S(a, b)

Let G_n,m be the family of graphs with n vertices and m edges, when n and m are previously given. It is well-known that there is a subset of G_n,m constituted by graphs G such that the vertex connectivity, the edge connectivity, and the minimum degree are all equal. In this paper, S(a, b)-classes of connected (a, b)-linear graphs with n vertices and m edges are described, where m is given as a function of a,b∈N/2. Some of them have extremal graphs for which the equalities above are extended to algebraic connectivity. These graphs are Laplacian integral although they are not threshold graphs. However, we do build threshold graphs in S(a, b).     

不含三圈的k圈图的拟拉普拉斯和拉普拉斯谱半径

k圈图是边数等于顶点数加k-1的简单连通图.文中确定了不含三圈的k圈图的拟拉普拉斯谱半径的上界,并刻画了达到该上界的极图.此外,文中确定了拟拉普拉斯谱半径排在前五位的不含三圈的单圈图,排在前八位的不含三圈的双圈图.最后说明文中所得结论对不含三圈的k圈图的拉普拉斯谱半径也成立.     

Maximality of the signless Laplacian energy

We study the problem of determining the graph with $n$ vertices having largest signless Laplacian energy. We conjecture it is the complete split graph whose independent set has (roughly) $2n∕3$ vertices. We show that the conjecture is true for several classes of graphs. In particular, the conjecture holds for the set of all complete split graphs of order $n$, for trees, for unicyclic and bicyclic graphs. We also give conditions on the number of edges, number of cycles and number of small eigenvalues so the graph satisfies the conjecture.     

Signless Laplacian spectral characterization of 4-rose graphs

A rose graph with p petals (or p-rose graph) is a graph obtained by taking p cycles with just a vertex in common. In this paper, we prove that all 4-rose graphs are determined by their signless Laplacian spectra.     

单圈图和双圈图的最大无符号拉普拉斯分离度

设G是一个n阶简单图,q_{1}(G)\geq q_{2}(G)\geq \cdots \geq q_{n}(G)是其无符号拉普拉斯特征值. 图G的无符号拉普拉斯分离度定义为S_{Q}(G)=q_{1}(G)-q_{2}(G). 确定了n阶单圈图和双圈图的最大的无符号拉普拉斯分离度,并分别刻画了相应的极图.     

On the Laplacian coefficients of bicyclic graphs

Let G be a graph of order n and let be the characteristic polynomial of its Laplacian matrix. Generalizing the approach in [D. Stevanovi?, A. Ili?, On the Laplacian coefficients of unicyclic graphs, Linear Algebra and its Applications 430 (2009) 2290-2300.] on graph transformations, we show that among all bicyclic graphs of order n, the kth coefficient c_k is smallest when the graph is B_n (obtained from C₄ by adding one edge connecting two non-adjacent vertices and adding n−4 pendent vertices attached to the vertex of degree 3).     

On graphs with the largest Laplacian index

Let G be a connected simple graph on n vertices. The Laplacian index of G, namely, the greatest Laplacian eigenvalue of G, is well known to be bounded above by n. In this paper, we give structural characterizations for graphs G with the largest Laplacian index n. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on n and k for the existence of a k-regular graph G of order n with the largest Laplacian index n. We prove that for a graph G of order n ⩾ 3 with the largest Laplacian index n, G is Hamiltonian if G is regular or its maximum vertex degree is Δ(G) = n/2. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results. The first author is supported by NNSF of China (No. 10771080) and SRFDP of China (No. 20070574006). The work was done when Z. Chen was on sabbatical in China.     

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

设图G是一个简单连通图. 如果任何一个与图G同拉普拉斯谱的图都与图G同构,则称图G是由其拉普拉斯谱确定的. 定义了双圈图\theta_{n}(p_1,p_2,\cdots,p_t) 和m 圈图H_n(m\cdot C_3;p_1,p_2,\cdots,p_t). 证明了双圈图\theta_{n}(p)和\theta_{n}(p,q),三圈图H_n(3\cdot C_3;p)和H_n(3\cdot 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.     

三圈图的无符号拉普拉斯谱半径

假设图G的点集是V(G)={v_1,v_2,…,v_n},用d_(v_i)(G)表示图G中点v_i的度,令A(G)表示G的邻接矩阵,D(G)是对角线上元素等于d_(v_i)(G)的n×n对角矩阵,Q(G)=D(G)+A(G)是G的无符号拉普拉斯矩阵,Q(G)的最大特征值是G的无符号拉普拉斯谱半径.现确定了所有点数为n的三圈图中无符号拉普拉斯谱半径最大的图的结构.     

On the Laplacian spectral radii of bicyclic graphs

A graph G of order n is called a bicyclic graph if G is connected and the number of edges of G is n+1. Let B(n) be the set of all bicyclic graphs on n vertices. In this paper, we obtain the first four largest Laplacian spectral radii among all the graphs in the class B(n) (n≥7) together with the corresponding graphs.     

Q整图新类

对于一个简单图G, 方阵Q(G)=D(G)+A(G)称为G的无符号拉普拉斯矩阵,其中D(G)和A(G)分别为G的度对角矩阵和邻接矩阵. 一个图是Q整图是指该图的无符号拉普拉斯矩阵的特征值全部为整数.首先通过Stanic 得到的六个顶点数目较小的Q整图,构造出了六类具有无穷多个的非正则的Q整图. 进而,通过图的笛卡尔积运算得到了很多的Q整图类. 最后, 得到了一些正则的Q整图.