The diameter and Laplacian eigenvalues of directed graphs (Q819189): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
(2 intermediate revisions by one other user not shown) | |||
Property / author | |||
Property / author: Fan R. K. Chung / rank | |||
Property / author | |||
Property / author: Fan R. K. Chung / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 02:17, 5 March 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