The Diameter and Laplacian Eigenvalues of Directed Graphs

Fan Chung


For undirected graphs it has been known for some time that one can bound the diameter using the eigenvalues. In this note we give a similar result for the diameter of strongly connected directed graphs $G$, namely $$ D(G) \leq \bigg \lfloor {2\min_x \log (1/\phi(x))\over \log{2\over 2-\lambda}} \bigg\rfloor +1 $$ where $\lambda$ is the first non-trivial eigenvalue of the Laplacian and $\phi$ is the Perron vector of the transition probability matrix of a random walk on $G$.

Full Text: PDF