The diameter and Laplacian eigenvalues of directed graphs (Q819189): Difference between revisions

Summary: 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 \left\lfloor \frac {2\min_x \log (1/\phi(x))}{\log\frac {2}{2-\lambda}}\right\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\).