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.