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

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2007-05, Vol.423 (1), p.53-73
Main Author: de Abreu, Nair Maria Maia
Format: Article
Language:English
Subjects:
Algebra
Algebraic connectivity
Bounds for the algebraic connectivity
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Extremal graphs
Fiedler vectors
Graph theory
Laplacian integral graphs
Laplacian of graph
Limit points
Linear and multilinear algebra, matrix theory
Mathematics
Sciences and techniques of general use
Vertex and edge connectivities
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2006.08.017