On Rayleigh-Ritz ratios of a generalized Laplacian matrix of directed graphs

Abstract

In [C.W. Wu, Algebraic connectivity of directed graphs, Linear and Multilinear Algebra, in press] a generalization of Fiedler's notion of algebraic connectivity to directed graphs was presented that inherits many properties of the algebraic connectivity of undirected graphs and has applications to the synchronization of coupled dynamical systems with both constant and time-varying coupling. However, it did not inherit nonnegativity and some of its bounds for combinatorial properties such as maximum directed cut and isoperimetric number are less strict that their undirected counterparts. In particular, these bounds do not have the corresponding bounds for undirected graphs as limiting cases. The purpose of this paper is to present a refinement of this algebraic connectivity which preserve nonnegativity for strongly connected graphs and have bounds which contain the undirected graphs as special cases. In particular, we study quantities related to a generalized Laplacian matrix of directed graphs and obtain bounds on combinatorial properties such as diameter, bandwidth, and bisection width for general directed graphs. Finally, we give an application to the synchronization of coupled dynamical systems with constant coupling. In particular, we show that strong enough cooperative coupling will synchronize a network of coupled systems if the underlying directed graph is strongly connected. © 2005 Elsevier Inc. All rights reserved.