Ordering trees by algebraic connectivity |
| |
Authors: | Robert Grone Russell Merris |
| |
Institution: | (1) Department of Mathematical Sciences, San Diego State University, 92182 San Diego, CA, USA;(2) Department of Mathematics and Computer Science, California State University, 94542 Hayward, CA, USA |
| |
Abstract: | LetG be a graph onn vertices. Denote byL(G) the difference between the diagonal matrix of vertex degrees and the adjacency matrix. It is not hard to see thatL(G) is positive semidefinite symmetric and that its second smallest eigenvalue,a(G) > 0, if and only ifG is connected. This observation led M. Fiedler to calla(G) thealgebraic connectivity ofG. Given two trees,T
1 andT
2, the authors explore a graph theoretic interpretation for the difference betweena(T
1) anda(T
2).Research supported by ONR contract 85K0335 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|