The diameter and Laplacian eigenvalues of directed graphs (Q819189)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The diameter and Laplacian eigenvalues of directed graphs |
scientific article |
Statements
The diameter and Laplacian eigenvalues of directed graphs (English)
0 references
22 March 2006
0 references
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\).
0 references