Algebraic Connectivity

The algebraic connectivity of a graph is the numerically second smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of a graph . In other words, it is the second smallest root of the graph's Laplacian polynomial. This eigenvalue is greater than 0 iff is a connected graph.

The ratio of the Laplacian spectral radius to algebraic connectivity is known as the Laplacian spectral ratio.

See also

Connected Graph, Fiedler Vector, Graph Eigenvalue, Graph Spectrum, Laplacian Matrix, Laplacian Polynomial, Laplacian Spectral Radius, Laplacian Spectral Ratio

Explore with Wolfram|Alpha

More things to try:

References

Chung, F. R. K. Spectral Graph Theory. Providence, RI: Amer. Math. Soc., 1997.Demmel, J. "CS 267: Notes for Lecture 23, April 9, 1999. Graph Partitioning, Part 2." http://www.cs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html.Lin, Z.; Wang, J.; and Cai, M. "The Laplacian Spectral Ratio of Connected Graphs." 21 Feb 2023. https://arxiv.org/abs/2302.10491v1.

Referenced on Wolfram|Alpha

Algebraic Connectivity

Cite this as:

Weisstein, Eric W. "Algebraic Connectivity." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AlgebraicConnectivity.html

Subject classifications