The diameter and Laplacian eigenvalues of directed graphs (Q819189): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q920938 |
||
Property / author | |||
Property / author: Fan R. K. Chung / rank | |||
Revision as of 18:05, 21 February 2024
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