The effect on the algebraic connectivity of a tree by grafting or collapsing of edges

Let G=(V,E) be a tree on n?2 vertices and let v∈V. Let L(G) be the Laplacian matrix of G and μ(G) be its algebraic connectivity. Let G_k,l, be the graph obtained from G by attaching two new paths P:vv₁v₂…v_k and Q:vu₁u₂…u_l of length k and l, respectively, at v. We prove that if l?k?1 then μ(G_k-1,l+1)?μ(G_k,l). Let (v₁,v₂) be an edge of G. Let be the tree obtained from G by deleting the edge (v₁,v₂) and identifying the vertices v₁ and v₂. Then we prove that As a corollary to the above results, we obtain the celebrated theorem on algebraic connectivity which states that among all trees on n vertices, the path has the smallest and the star has the largest algebraic connectivity.     

On algebraic connectivity augmentation

Suppose that G is an undirected graph, and that H is a spanning subgraph of G^c whose edges induce a subgraph on p vertices. We consider the expression α(G∪H)-α(G), where α denotes the algebraic connectivity. Specifically, we provide upper and lower bounds on α(G∪H)-α(G) in terms of p, and characterise the corresponding equality cases. We also discuss the density of the expression α(G∪H)-α(G) in the interval [0,p]. A bound on α(G∪H)-α(G) is provided in a special case, and several examples are considered.     

关于代数连通度的一个注记

图G=(V,E)的次小的拉普拉斯特征值称为G的代数连通度,记为α(G).设δ(G)为G的最小度.Fiedler早在1973年便证明了α(G)≤δ(G),但他未能给出等号成立的极图刻划.后来,我们在[6]中确定了当δ(G)≤1/2|V(G)|时α(G)=δ(G)的充要条件.本文中,我们将确定任意情况下α(G)=δ(G)成立的所有极图.     

Lower bounds of the Laplacian spectrum of graphs based on diameter

Let G be a connected graph of order n. The diameter of G is the maximum distance between any two vertices of G. In the paper, we will give some lower bounds for the algebraic connectivity and the Laplacian spectral radius of G in terms of the diameter of G.     

关于树的代数连通度的Fiedler不等式的新证明

设T为含n个顶点的树，L(T)为其Laplace矩阵，L(T)的次小特征值α(T)称为T的代数连通度，Fiedlcr给出如下关于α(T)的界的经典结论α(Pn)≤α(T)≤α(Sn)，其中Pn，Sn分别为含有n个顶点的路和星．Merris和Mass独立地证明了：α(T)=α(Sn)当且仅当T=Sn．通过重新组合由Fiedler向量所赋予的顶点的值，本给出上述不等式的新证明，并证明了：α(T)=α(Pn)当且仅当T=Pn。     

Doubly stochastic graph matrices, II

If G is a graph on n vertices, its Laplacian matrix L(G) = D(G) - A(G) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. The main purpose of this note is to continue the study of the positive definite, doubly stochastic graph matrix (I_n + L(G))-¹= ω(G) = (w_ij). If, for example, w(G) = min w_ij, then w(G)≥0 with equality if and only if G is disconnected and w(G) ≤ l/(n + 1) with equality if and only if G = K_n. If i¦j, then w_ii ≥2wij, with equality if and only if the ith vertex has degree n - 1. In a sense made precise in the note, max w,, identifies most remote vertices of G. Relations between these new graph invariants and the algebraic connectivity emerge naturally from the fact that the second largest eigenvalue of ω(G) is 1/(1 + a(G)).     

Algebraic connectivity of weighted trees under perturbation

We investigate how the algebraic connectivity of a weighted tree behaves when the tree is perturbed by removing one of its branches and replacing it with another. This leads to a number of results, for example the facts that replacing a branch in an unweighted tree by a star on the same number of vertices will not decrease the algebraic connectivity, while replacing a certain branch by a path on the same number of vertices will not increase the algebraic connectivity. We also discuss how the arrangement of the weights on the edges of a tree affects the algebraic connectivity, and we produce a lower bound on the algebraic connectivity of any unweighted graph in terms of the diameter and the number of vertices. Throughout, our techniques exploit a connection between the algebraic connectivity of a weighted tree and certain positive matrices associated with the tree.     

On the Eigenvalue Two and Matching Number of a Tree

In [6],Guo and Tan have shown that 2 is a Laplacian eigenvalue of any tree with perfect matchings.For trees without perfect matchings,we study whether 2 is one of its Laplacian eigenvalues.If the matchingnumber is 1 or 2,the answer is negative;otherwise,there exists a tree with that matching number which has (hasnot) the eigenvalue 2.In particular,we determine all trees with matching number 3 which has the eigenvalue2.     

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

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

Spectral properties of Pascal graphs

We obtain spectral properties of the Pascal graphs by exploring its spectral graph invariants such as the algebraic connectivity, the first three largest Laplacian eigenvalues and the nullity. Some open problems pertaining to the Pascal graphs are given.     

图的Laplacian特征值

本文研究了连通图的Laplacian特征值,利用图的Laplacian矩阵的特征多项式的行列式表示式,对存在两个不同顶点,但有相同邻集的一类图,得到了一个Laplacian特征值,并给出了它的应用.     

The ordering of unicyclic graphs with the smallest algebraic connectivity

Fielder [M. Fielder, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305] has turned out that G is connected if and only if its algebraic connectivity a(G)>0. In 1998, Fallat and Kirkland [S.M. Fallat, S. Kirkland, Extremizing algebraic connectivity subject to graph theoretic constraints, Electron. J. Linear Algebra 3 (1998) 48-74] posed a conjecture: if G is a connected graph on n vertices with girth g≥3, then a(G)≥a(C_n,g) and that equality holds if and only if G is isomorphic to C_n,g. In 2007, Guo [J.M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702-5711] gave an affirmatively answer for the conjecture. In this paper, we determine the second and the third smallest algebraic connectivity among all unicyclic graphs with vertices.