c Birkhauser Verlag, Basel, 2005 Annals of Combinatorics Laplacians and the Cheeger Inequality for Directed Graphs

AMS Subject Classication: 05C20, 05C50, 15A42, 60J05 Abstract. We consider Laplacians for directed graphs and examine their eigenvalues. We intro-duce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then dene a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems