algebraic connectivity of a graph
Let be the Laplacian matrix (http://planetmath.org/LaplacianMatrixOfAGraph)of a finite connected graph with vertices. Let the eigenvaluesof be denoted by, whichis the usual notation in spectral graph theory.The connectivity of is .The usual notation for the algebraic connectivity
is .The parameter is a measure of how well the graph is connected.For example, if and only if 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.