algebraic connectivity of a graph
Let $L(G)$ be the Laplacian matrix (http://planetmath.org/LaplacianMatrixOfAGraph) of a finite connected graph^{} $G$ with $n$ vertices. Let the eigenvalues of $L(G)$ be denoted by ${\lambda}_{1}\le {\lambda}_{2}\le \mathrm{\cdots}\le {\lambda}_{n}$, which is the usual notation in spectral graph theory. The connectivity of $G$ is ${\lambda}_{2}$. The usual notation for the algebraic connectivity^{} is $a(G)$. The parameter is a measure of how well the graph is connected. For example, $a(G)\ne 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 |