Name
Abstract | ||
|---|---|---|
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) <= [log(2-lambda)/(2)/2 min(x)log(1/phi(x))] + 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. |
Year | Venue | Keywords |
|---|---|---|
2006 | ELECTRONIC JOURNAL OF COMBINATORICS | eigenvalues,directed graph |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Stochastic matrix,Random walk,Directed graph,Hessenberg variety,Strongly connected component,Eigenvalues and eigenvectors,Mathematics,Lambda,Laplace operator | Journal | 13.0 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 13 |
PageRank | References | Authors |
0.97 | 1 | 1 |