Doubly stochastic matrices of trees

In this paper, we obtain sharp upper and lower bounds for the smallest entries of doubly stochastic matrices of trees and characterize all extreme graphs which attain the bounds. We also present a counterexample to Merris’ conjecture on relations between the smallest entry of the doubly stochastic matrix and the algebraic connectivity of a graph in [R. Merris, Doubly stochastic graph matrices II, Linear Multilinear Algebr. 45 (1998) 275–285].     

Constructions for type I trees with nonisomorphic Perron branches

A tree is classified as being type I provided that there are two or more Perron branches at its characteristic vertex. The question arises as to how one might construct such a tree in which the Perron branches at the characteristic vertex are not isomorphic. Motivated by an example of Grone and Merris, we produce a large class of such trees, and show how to construct others from them. We also investigate some of the properties of a subclass of these trees. Throughout, we exploit connections between characteristic vertices, algebraic connectivity, and Perron values of 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。     

The Algebraic Connectivity of Graphs with Given Matching Number

The algebraic connectivity of a graph is the second smallest eigenvalue of the associated Laplacian matrix. In this paper, we not only characterize the extremal graphs with the maximal algebraic connectivity among all graphs of order n with given matching number, but also determine the extremal tree with the maximal algebraic connectivity among all trees of order n with given matching number.     

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.     

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

Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:

the generalized Bethe tree B,

a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,

a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,

a graph obtained from the cycle C_r by attaching B, by its root, to each vertex of the cycle, and

a tree obtained from the path P_r by attaching B, by its root, to each vertex of the path,

is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.

     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

树的变形与代数连通度

本文利用瓶颈矩阵的Perron值和代数连通度的二次型形式,系统地研究了当迁移或改变分支(边、点)和变动一些边的权重时无向赋权树的代数连通度的变化规律,认为代数连通度可用来描述树的边及其权重的某种中心趋势性.引入广义树和广义特征点概念,将II型树转换成具有相同代数连通度的I型树,使得树的代数连通度的讨论只须限于I型树的研究即可.     

A divide-and-conquer bound for aggregate’s quality and algebraic connectivity

We establish a divide-and-conquer bound for the aggregate’s quality and algebraic connectivity measures, as defined for weighted undirected graphs. Aggregate’s quality is defined on a set of vertices and, in the context of aggregation-based multigrid methods, it measures how well this set of vertices is represented by a single vertex. On the other hand, algebraic connectivity is defined on a graph, and measures how well this graph is connected. The considered divide-and-conquer bound for aggregate’s quality relates the aggregate’s quality of a union of two disjoint sets of vertices to the aggregate’s quality of the two sets. Likewise, the bound for algebraic connectivity relates the algebraic connectivity of the graph induced by a union of two disjoint sets of vertices to the algebraic connectivity of the graphs induced by the two sets.     

On the adjoint of a matrix associated with trees

Let Q denote the vertex-edge incidence matrix of a tree T. we give an elementary derivation of an extension of a result of Merris on a graph-theoretic interpretation of the entries in the adjoint of the matrix Q¹Q.     

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

Old and new results on algebraic connectivity of graphs

This paper is a survey of the second smallest eigenvalue of the Laplacian of a graph G, best-known as the algebraic connectivity of G, denoted a(G). Emphasis is given on classifications of bounds to algebraic connectivity as a function of other graph invariants, as well as the applications of Fiedler vectors (eigenvectors related to a(G)) on trees, on hard problems in graphs and also on the combinatorial optimization problems. Besides, limit points to a(G) and characterizations of extremal graphs to a(G) are described, especially those for which the algebraic connectivity is equal to the vertex connectivity.     

A lower bound for algebraic connectivity based on the connection-graph-stability method

This paper introduces the connection-graph-stability method and uses it to establish a new lower bound on the algebraic connectivity of graphs (the second smallest eigenvalue of the Laplacian matrix of the graph) that is sharper than the previously published bounds. The connection-graph-stability score for each edge is defined as the sum of the lengths of the shortest paths making use of that edge. We prove that the algebraic connectivity of the graph is bounded below by the size of the graph divided by the maximum connection-graph-stability score assigned to the edges.     

A sharp upper bound on algebraic connectivity using domination number

Let G be a connected graph of order n. The algebraic connectivity of G is the second smallest eigenvalue of the Laplacian matrix of G. A dominating set in G is a vertex subset S such that each vertex of G that is not in S is adjacent to a vertex in S. The least cardinality of a dominating set is the domination number. In this paper, we prove a sharp upper bound on the algebraic connectivity of a connected graph in terms of the domination number and characterize the associated extremal graphs.     

Characteristic vertices of weighted trees via perron values

We consider a weighted tree T with algebraic connectivity μ, and characteristic vertex v. We show that μ and its associated eigenvectors can be described in terms of the Perron value and vector of a nonnegative matrix which can be computed from the branches of T at v. The machinery of Perron-Frobenius theory can then be used to characterize Type I and Type II trees in terms of these Perron values, and to show that if we construct a weighted tree by taking two weighted trees and identifying a vertex of one with a vertex of the other, then any characteristic vertex of the new tree lies on the path joining the characteristic vertices of the two old trees.     

The six classes of trees with the largest algebraic connectivity

In this paper, we study the algebraic connectivity α(T) of a tree T. We introduce six Classes (C1)-(C6) of trees of order n, and prove that if T is a tree of order n?15, then if and only if , where the equality holds if and only if T is a tree in the Class (C6). At the same time we give a complete ordering of the trees in these six classes by their algebraic connectivity. In particular, we show that α(T_i)>α(T_j) if 1?i<j?6 and T_i is any tree in the Class (Ci) and T_j is any tree in the Class (Cj). We also give the values of the algebraic connectivity of the trees in these six classes. As a technique used in the proofs of the above mentioned results, we also give a complete characterization of the equality case of a well-known relation between the algebraic connectivity of a tree T and the Perron value of the bottleneck matrix of a Perron branch of T.     

On the adjoint of a matrix associated with trees

Let Q denote the vertex-edge incidence matrix of a tree T. we give an elementary derivation of an extension of a result of Merris on a graph-theoretic interpretation of the entries in the adjoint of the matrix Q ¹ Q.