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.     

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.     

A conjecture on the algebraic connectivity of connected graphs with fixed girth

In this paper, we completely solve a conjecture on the minimum algebraic connectivity of connected graphs with fixed girth (see [S. Fallat, S. Kirkland, Extremizing algebraic connectivity subject to graph theoretic constraints, Electron. J. Linear Algebra 3 (1998) 48-74]).     

The smallest values of algebraic connectivity for unicyclic graphs

The algebraic connectivity of G is the second smallest eigenvalue of its Laplacian matrix. Let U_n be the set of all unicyclic graphs of order n. In this paper, we will provide the ordering of unicyclic graphs in U_n up to the last seven graphs according to their algebraic connectivities when n≥13. This extends the results of Liu and Liu [Y. Liu, Y. Liu, The ordering of unicyclic graphs with the smallest algebraic connectivity, Discrete Math. 309 (2009) 4315-4325] and Guo [J.-M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702-5711].     

The smallest values of algebraic connectivity for trees

The algebraic connectivity of a graph G is the second smallest eigenvalue of its Laplacian matrix. Let ■n be the set of all trees of order n. In this paper, we will provide the ordering of trees in ■n up to the last eight trees according to their smallest algebraic connectivities when n ≥ 13. This extends the result of Shao et al. [The ordering of trees and connected graphs by algebraic connectivity. Linear Algebra Appl., 428, 1421-1438 (2008)].     

On algebraic connectivity as a function of an edge weight

We consider the Laplacian matrix of a weighted graph, and how the algebraic connectivity, α, behaves when considered as a function of a single edge weight. Under suitable differentiability conditions, we bound the first derivative of α from above, show that α is necessarily concave down, and produce a lower bound on the second derivative of α. When α is simple, we discuss the effect of increasing an edge weight on the corresponding Fiedler vector. We also compute the limiting value of α as the edge weight increases to infinity.     

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

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

关于树的代数连通度的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。     

On the first passage time of a simple random walk on a tree

We consider a simple random walk on a tree. Exact expressions are obtained for the expectation and the variance of the first passage time, thereby recovering the known result that these are integers. A relationship of the mean first passage matrix with the distance matrix is established and used to derive a formula for the inverse of the mean first passage matrix.     

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.     

The effect on the Laplacian spectral radius of a graph by adding or grafting edges

This paper investigates how the Laplacian spectral radius behaves when the graph is perturbed by adding or grafting edges.     

Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality

Let G be a connected graph, suppose that v is a vertex of G, and denote the subgraph formed from G by deleting vertex v by G?v. Denote the algebraic connectivities of G and G?v by α(G) and α(G?v), respectively. In this paper, we consider the functions ?(v)=α(G)−α(G?v) and , provide attainable upper and lower bounds on both functions, and characterise the equality cases in those bounds. The function κ yields a measure of vertex centrality, and we apply that measure to analyse certain graphs arising from food webs.     

图的代数连通度的界(英文)

本文首先给出了简单图的度序列的平方和的上界,利用这些结果,求出了简单图的代数连通度的几个上下界并确定了它们的临界图。另外,文章也给出了加权图的代数连通度的一个下界。     

Inverses of -distance matrices of a tree

The determinant and the inverse of the distance matrix of a tree have been investigated in the literature, following the classical formulas due to Graham and Pollak for the determinant, and due to Graham and Lovász for the inverse. We consider two q-analogs of the distance matrix of a tree and obtain formulas for the inverses of the two distance matrices. Yan and Yeh have previously obtained expressions for the determinants of the two distance matrices. Some related results are proved.