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.     

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.     

Hamiltonian graphs of given order and minimum algebraic connectivity

In this paper, we study the algebraic connectivity of a Hamiltonian graph, and determine all Hamiltonian graphs whose algebraic connectivity attain the minimum among all Hamiltonian graphs on n vertices.     

具有完美匹配树的代数连通度的排序

Jason等确定了阶数为n的具有完美匹配树的最大的代数连通度以及相应的极图．本文确定了阶数为n的具有完美匹配树的第二大到第五大的代数连通度以及达到这些数值的图（或图类）．     

A Lower Bound for the Algebraic Connectivity of a Graph in Terms of the Domination Number

We investigate how the algebraic connectivity of a graph changes by relocating a connected branch from one vertex to another vertex, and then minimize the algebraic connectivity among all connected graphs of order n with fixed domination number \(\gamma\leq\frac{n+2}{3}\), and finally present a lower bound for the algebraic connectivity in terms of the domination number. We also characterize the minimum algebraic connectivity of graphs with domination number half their order.     

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

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

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

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

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.     

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.     

On the Laplacian integral tricyclic graphs

A graph is called Laplacian integral if all its Laplacian eigenvalues are integers. In this paper, we give an edge subdividing theorem for Laplacian eigenvalues of a graph (Theorem 2.1) and characterize a class of k-cyclic graphs whose algebraic connectivity is less than one. Using these results, we determine all the Laplacian integral tricyclic graphs. Furthermore, we show that all the Laplacian integral tricyclic graphs are determined by their Laplacian spectra.     

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.     

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.     

Algebraic Connectivity of Connected Graphs with Fixed Number of Pendant Vertices

In this paper, we consider the following problem. Over the class of all simple connected graphs of order n with k pendant vertices (n, k being fixed), which graph maximizes (respectively, minimizes) the algebraic connectivity? We also discuss the algebraic connectivity of unicyclic graphs.     

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

Algebraic structures on graphs

In this paper we consider directed graphs with algebraic structures: group-graphs, ringgraphs, involutorial graphs, affine graphs, graphs of morphisms between graphs, graphs of reduced paths of an involutorial graph, etc. We show also how several well-known algebraic constructions can be carried over to graphs. As a typical example we generalize the construction of the group of automorphisms of a set, by constructing a group-graph associated with any given graphΓ. It is the group-graph of reduced paths of the involutorial graph associated to the graph of automorphisms ofΓ.     

Coincidence of the sets of minimal and irreducible join graphs over primary structure of algebraic Bayesian networks

An algebraic Bayesian network (ABN) is a probabilistic-logic graphical model of bases of knowledge patterns with uncertainty. A primary structure of an ABN is a set of knowledge patterns, that are ideals of conjunctions of positive literals except the empty conjunction endowed with scalar or interval probability estimates. A secondary ABN structure is represented by a graph constructed over the primary structure, which is called a join graph. From the point of view of learning of a global ABN structure, of interest are join graphs with the minimum number of edges and irreducible join graphs. A theorem on the coincidence of the sets of minimal and irreducible join graphs over the same primary structure is proved. A greedy algorithm constructing an arbitrary minimal join graph from a given primary structure is described. A theorem expressing the number of edges in a minimal join graph as the sum of the ranks of the incidence matrices of strong restrictions of a maximal join graph minus the number of significant weights is stated and proved. A generalized graph of maximal knowledge patterns (GGMKP) is a graph with the same vertex set as the join graph which is not subject to any constraints concerning the possibility of joining two vertices by an edge. It is proved that the pair consisting of the edge set of a maximal GGMKP and the set of all subsets of this graph such that the subtraction of any such subset from the maximal GGMKP yields an edge of the join graph on the same vertex set is a matroid.     

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

Graphs of given order and size and minimum algebraic connectivity

The structure of connected graphs of given size and order that have minimal algebraic connectivity is investigated. It is shown that they must consist of a chain of cliques. Moreover, an upper bound for the number of maximal cliques of size 2 or larger is derived.