单圈图的代数连通度的排序

n阶图G称为是一个单圈图,如果G是连通的,并且G的边数也是n.用U(n)表示所有n阶单圈图所成的集合.给出了当阶数n≥25时,代数连通度为前九大的n阶单圈图及它们的代数连通度.     

The ordering of trees and connected graphs by algebraic connectivity

In this paper, we first determine that the first four trees of order n?9 with the smallest algebraic connectivity are P_n,Q_n,W_n and Z_n with α(P_n)<α(Q_n)<α(W_n)<α(Z_n)<α(T), where T is any tree of order n other than P_n, Q_n, W_n, and Z_n. Then we consider the effect on the Laplacian eigenvalues of connected graphs by suitably adding edges. By using these results and methods, we finally determine that the first six connected graphs of order n?9 with the smallest algebraic connectivity are and , with , where G is any connected graph of order n other than P_n, Q_n, , W_n, and .     

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

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.     

Ordering trees by their spectral radii

Let T be a tree with n vertices and let A（T） be the adjacency matrix of T. Spectral radius of T is the largest eigenvalue of A（T）. Wu et al. [Wu, B.F., Yuan, X.Y, and Xiao, E.L. On the spectral radii of trees, Journal of East China Normal University （Natural Science）, 3：22-28 （2004）] determined the first seven trees of order n with the smallest spectral radius. In this paper, we extend this ordering by determining the trees with the eighth to the tenth smallest spectral radius among all trees with n vertices.     

Ordering trees by the Laplacian coefficients

Motivated by a Mohar’s paper proposing “how to order trees by the Laplacian coefficients”, we investigate a partial ordering of trees with diameters 3 and 4 by the Laplacian coefficients. These results are used to determine several orderings of trees by the Laplacian coefficients.     

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 algebraic connectivity of lollipop graphs

Let C_n,g be the lollipop graph obtained by appending a g-cycle C_g to a pendant vertex of a path on n-g vertices. In 2002, Fallat, Kirkland and Pati proved that for and g?4, α(C_n,g)>α(C_n,g-1). In this paper, we prove that for g?4, α(C_n,g)>α(C_n,g-1) for all n, where α(C_n,g) is the algebraic connectivity of C_n,g.     

Maximum algebraic connectivity augmentation is NP-hard

The algebraic connectivity of a graph, which is the second-smallest eigenvalue of the Laplacian of the graph, is a measure of connectivity. We show that the problem of adding a specified number of edges to an input graph to maximize the algebraic connectivity of the augmented graph is NP-hard.     

Atom-bond connectivity index of trees

The recently introduced atom-bond connectivity (ABC) index has been applied up to now to study the stability of alkanes and the strain energy of cycloalkanes. Here, mathematical properties of the ABC index of trees are studied. Chemical trees with extremal ABC values are found. In addition, it has been proven that, among all trees, the star tree, S_n, has the maximal ABC value.     

Lower bounds for algebraic decision trees

A topological method is given for obtaining lower bounds for the height of algebraic decision trees. The method is applied to the knapsack problem where an $\text{Ω(n}{}^2\text{)}$ bound is obtained for trees with bounded-degree polynomial tests, thus extending the Dobkin-Lipton result for linear trees. Applications to the convex hull problem and the distinct element problem are also indicated. Some open problems are discussed.     

An algebraic metric for phylogenetic trees

The definition of similarity measures for phylogenetic trees has been motivated by the computation of consensus trees, the search by similarity in databases, and the assessment of phylogenetic reconstruction methods. The transposition distance for fully resolved trees is a recent addition to the extensive collection of available metrics for comparing phylogenetic trees. In this work, we generalize the transposition metric from fully resolved to arbitrary phylogenetic trees, through a construction that involves an embedding of the set of phylogenetic trees (up to isomorphisms) with a fixed number of labeled leaves into a symmetric group. We also show that this transposition distance can be computed in linear time and we establish some of its basic properties.     

The algebraic connectivity of graphs under perturbation

In this paper, we investigate how the algebraic connectivity of a connected graph behaves when the graph is perturbed by separating or grafting an edge.     

Ordering of trees with fixed matching number by the Laplacian coefficients

Let G be a simple undirected graph with the characteristic polynomial of its Laplacian matrix L(G), . Aleksandar Ili? [A. Ili?, Trees with minimal Laplacian coefficients, Comput. Math. Appl. 59 (2010) 2776-2783] identified n-vertex trees with given matching number q which simultaneously minimize all Laplacian coefficients. In this paper, we give another proof of this result. Generalizing the approach in the above paper, we determine n-vertex trees with given matching number q which have the second minimal Laplacian coefficients. We also identify the n-vertex trees with a perfect matching having the largest and the second largest Laplacian coefficients, respectively. Extremal values on some indices, such as Wiener index, modified hyper-Wiener index, Laplacian-like energy, incidence energy, of n-vertex trees with matching number q are obtained in this paper.     

Perron components and algebraic connectivity for weighted graphs

The algebraic connectivity of a connected graph is the second-smallest eigenvalue of its Laplacian matrix, and a remarkable result of Fiedler gives information on the structure of the eigenvectors associated with that eigenvalue. In this paper, we introduce the notion of a perron component at a vertex in a weighted graph, and show how the structure of the eigenvectors associated with the algebraic connectivity can be understood in terms of perron components. This leads to some strengthening of Fiedler's original result, gives some insights into weighted graphs under perturbation, and allows for a discussion of weighted graphs exhibiting tree-like structure.     

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.     

Algebraic connectivity and degree sequences of trees

We investigate the structure of trees that have minimal algebraic connectivity among all trees with a given degree sequence. We show that such trees are caterpillars and that the vertex degrees are non-decreasing on every path on non-pendant vertices starting at the characteristic set of the Fiedler vector.