On the least eigenvalue of a unicyclic mixed graph

Using the result on Fiedler vectors of a simple graph, we obtain a property on the structure of the eigenvectors of a nonsingular unicyclic mixed graph corresponding to its least eigenvalue. With the property, we get some results on minimizing and maximizing the least eigenvalue over all nonsingular unicyclic mixed graphs on n vertices with fixed girth. In particular, the graphs which minimize and maximize, respectively, the least eigenvalue are given over all such graphs with girth 3.     

First eigenvalue and first eigenvectors of a nonsingular unicyclic mixed graph

Let G be a mixed graph and let L(G) be the Laplacian matrix of the graph G. The first eigenvalue and the first eigenvectors of G are respectively referred to the least nonzero eigenvalue and the corresponding eigenvectors of L(G). In this paper we focus on the properties of the first eigenvalue and the first eigenvectors of a nonsingular unicyclic mixed graph (abbreviated to a NUM graph). We introduce the notion of characteristic set associated with the first eigenvectors, and then obtain some results on the sign structure of the first eigenvectors. By these results we determine the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order and fixed girth, and the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order.     

单圈图的最大特征值序

主要讨论了单圈图按其最大特征值进行排序的问题，确定了该序的前六个图。     

具有五个不同于0和1的Laplacian特征值的单圈图

设$U$是$n$阶单圈图, $m_{U}(1)$是$U$的拉普拉斯特征值1的重数.众所周知,0是连通图重数为1的拉普拉斯特征值.这意味着如果$U$有五个不同于0和1的拉普拉斯特征值,那么$m_U(1)=n-6$.本文完整刻画了$m_U(1)=n-6$的所有单圈图.     

单圈图依最大特征值的进一步排序

文[3]中确定了单圈图的最大特征值序中的前六个图,本文确定了该序中第七个至第十一个图.     

On thek-th largest eigenvalue of the Laplacian matrix of a graph

In this paper, we give the upper bound and lower bound ofk-th largest eigenvalue λk of the Laplacian matrix of a graphG in terms of the edge number ofG and the number of spanning trees ofG. This research is supported by the National Natural Science Foundation of China (Grant No.19971086) and the Doctoral Program Foundation of State Education Department of China.     

Minimizing the least eigenvalue of unicyclic graphs with fixed diameter

Let U(n,d) be the set of unicyclic graphs on n vertices with diameter d. In this article, we determine the unique graph with minimal least eigenvalue among all graphs in U(n,d). It is found that the extremal graph is different from that for the corresponding problem on maximal eigenvalue as done by Liu et al. [H.Q. Liu, M. Lu, F. Tian, On the spectral radius of unicyclic graphs with fixed diameter, Linear Algebra Appl. 420 (2007) 449-457].     

谱半径前六位的n阶单圈图

恰含一个圈的简单连通图称为单圈图。Cn记n个顶点的圈。△（i,j,κ）记C3的三个顶点上分别接出i,j,κ条悬挂边所得的图,其中i≥j≥κ≥0.Sl^n-l记Cl的某一顶点上接出n-l条悬挂边所得到的图。△（n-4 1,0,0)记△（n-4,0,0)的某个悬挂点上接出一条悬挂边所得到的图。本文证明了：若把所有n(n≥12）阶单圈图按其最大特征值从大到小的顺序排列,则排在前六位的依次是S3^n-3,△（n-4,1,0),△（n-4 1,0,0),S4^n-4,△（n-5,2,0),△（n-5,1,1)。     

Several sharp upper bounds for the largest laplacian eigenvalue of a graph

Let K be the quasi-Laplacian matrix of a graph G and B be the adjacency matrix of the line graph of G,respectively.In this paper,we first present two sharp upper bounds for the largest Laplacian eigenvalue of G by applying the non-negative matrix theory to the similar matrix D~(-1/2) KD~(1/2) and U~(-1/2)BU~(1/2),respectively,where D is the degree diagonal matrix of G and U=diag(d_u,d_v,:uv∈E(G)). And then we give another type of the upper bound in terms of the degree of the vertex and the edge number of G.Moreover,we determine all extremal graphs which achieve these upper bounds.Finally, some examples are given to illustrate that our results are better than the earlier and recent ones in some sense.     

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.     

Non-bipartite Graphs with Third Largest Laplacian Eigenvalue Less Than Three

All bipartite graphs whose third largest Laplacian eigenvalue is less than 3 have been characterized by Zhang. In this paper, all connected non-bipartite graphs with third largest Laplacian eigenvalue less than three are determined.     

单圈混合图的极大谱半径

设U＊为一个未定向的n个顶点上的单圈混合图,它是由一个三角形在其某个顶点上附加”一3个悬挂边而获得．在文[Largest eigenvalue of aunicyclic mixed graph,Applied Mathematics A Journal of Chinese Universities （Ser．B）,2004,19（2）：140-J48]中,作者证明了：在相差符号同构意下,在所有n个顶点上的单圈混合图中,U＊是唯一的达到最大Laplace谱半径的混合图．本文应用非负矩阵的Perron向量,给出上述结论的一个简单的证明．     

单圈混合图的极大谱半径(英文)

设U*为一个未定向的n个顶点上的单圈混合图,它是由一个三角形在其某个顶点上附加n-3个悬挂边而获得.在文[Largest eigenvalue of a unicyclic mixed graph,Applied Mathematics A Journal of Chinese Universities(Ser.B),2004,19(2):140-148]中,作者证明了:在相差符号同构意下,在所有n个顶点上的单圈混合图中,U*是唯一的达到最大Laplace谱半径的混合图.本文应用非负矩阵的Perron向量,给出上述结论的一个简单的证明.     

一类混合图的结构及其特征空间

主要讨论具有如下性质的一类连通混合图G:其所有非奇异圈恰有一条公共边,且除了该公共边的端点外,任意两个非奇异圈没有其它交点.本文给出了图G的结构性质,建立了其最小特征值λ1(G)(以及相对应的特征向量)与某个简单图的代数连通度(以及Fiedler向量)之间联系,并应用上述联系证明了λ1(■)≤α(G),其中G是由G通过对其所有无向边定向而获得,α(■)为■的代数连通度.     

Lower bounds on the third smallest laplacian eigenvalue of a graph

We introduce a new graph-theoretic invariant ω(G) for a simple graph G, and relate it to the third smallest Laplace eigenvalue of G.     

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.     

The maximum multiplicity of the largest k-th eigenvalue in a matrix whose graph is acyclic or unicyclic

Given a graph $G$ we are interested in studying the symmetric matrices associated to $G$ with a fixed number of negative eigenvalues. For this class of matrices we focus on the maximum possible nullity. For trees this parameter has already been studied and plenty of applications are known. In this work we derive a formula for the maximum nullity and completely describe its behavior as a function of the number of negative eigenvalues. In addition, we also carefully describe the matrices associated with trees that attain this maximum nullity. The analysis is then extended to the more general class of unicyclic graphs. Further our work is applied to re-describing all possible partial inertias associated with trees, and is employed to study an instance of the inverse eigenvalue problem for certain trees.     

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

设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阶单圈图和双圈图的最大的无符号拉普拉斯分离度,并分别刻画了相应的极图.