algebraic connectivity of a graph


Let L(G) be the Laplacian matrix (http://planetmath.org/LaplacianMatrixOfAGraph) of a finite connected graphMathworldPlanetmath G with n vertices. Let the eigenvalues of L(G) be denoted by λ1λ2λn, which is the usual notation in spectral graph theory. The connectivity of G is λ2. The usual notation for the algebraic connectivityMathworldPlanetmath is a(G). The parameter is a measure of how well the graph is connected. For example, a(G)0 if and only if G is connected.

References

  • 1 Fieldler, M. Algebraic connectivity of graphs, Czech. Math. J. 23 (98) (1973) pp. 298-305.
  • 2 Merris, R. Laplacian matrices of graphs: a survey, Lin. Algebra and its Appl. 197/198 (1994) pp. 143-176.
Title algebraic connectivity of a graph
Canonical name AlgebraicConnectivityOfAGraph
Date of creation 2013-03-22 17:04:37
Last modified on 2013-03-22 17:04:37
Owner Mathprof (13753)
Last modified by Mathprof (13753)
Numerical id 9
Author Mathprof (13753)
Entry type Definition
Classification msc 05C50
Defines algebraic connectivity