Algebraic connectivity

From Wikipedia, the free encyclopedia

The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G.[1] This eigenvalue is greater than 0 if and only if G is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is, and has implications for properties such as synchronizability and clustering.

[edit] History

The original theory related to algebraic connectivity was done by Miroslav Fiedler.[2][3] In his honor the eigenvector associated with the algebraic connectivity has been named the Fiedler vector.

[edit] References

  1. ^ Weisstein, Eric W. "Algebraic Connectivity." From MathWorld--A Wolfram Web Resource.
  2. ^ M. Fiedler. Algebraic connectivity of Graphs, Czechoslovak Mathematical Journal: 23 (98), 1973
  3. ^ M. Fiedler. Laplacian of graphs and algebraic connectivity, Combinatorics and Graph Theory 25:57-70, 1989

[edit] Further reading

  • Chung, F. R. K. Spectral Graph Theory. Providence, RI: Amer. Math. Soc., 1997.