The diameter and Laplacian eigenvalues of directed graphs (Q819189): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users 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 | |||
links / mardi / name | links / mardi / name | ||
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