Algebraic connectivity of directed graphs
- 1 June 2005
- journal article
- research article
- Published by Informa UK Limited in Linear and Multilinear Algebra
- Vol. 53 (3), 203-223
- https://doi.org/10.1080/03081080500054810
Abstract
We consider a generalization of Fiedler's notion of algebraic connectivity to directed graphs. We show that several properties of Fiedler's definition remain valid for directed graphs and present properties peculiar to directed graphs. We prove inequalities relating the algebraic connectivity to quantities such as the bisection width, maximum directed cut and the isoperimetric number. Finally, we illustrate an application to the synchronization in networks of coupled chaotic systems.Keywords
This publication has 16 references indexed in Scilit:
- The Probabilistic MethodPublished by Wiley ,2000
- Generalized matrix tree theorem for mixed graphsLinear and Multilinear Algebra, 1999
- Modern Graph TheoryGraduate Texts in Mathematics, 1998
- Synchronization in an array of linearly coupled dynamical systemsIEEE Transactions on Circuits and Systems I: Regular Papers, 1995
- The asymptotic behaviour of Fiedler's algebraic connectivity for random graphsDiscrete Mathematics, 1991
- Combinatorial Matrix TheoryPublished by Cambridge University Press (CUP) ,1991
- Matrix AnalysisPublished by Cambridge University Press (CUP) ,1985
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- The eigenvalues of random symmetric matricesCombinatorica, 1981
- Algebraic connectivity of graphsCzechoslovak Mathematical Journal, 1973