Algebraic Connectivity of Directed Graphs

We consider a generalization of Fiedler's notion of algebraic connectivity to directed graphs. We show that several properties of Fiedler's de nition 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.

By: Chai Wah Wu

Published in: Linear and Multilinear Algebra, volume 53, (no 3), pages 203-23 in 2005

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .