Geodesic
The diameter and Laplacian eigenvalues of directed graphs
The electronic journal of combinatorics, Tome 13 (2006)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 \bigg \lfloor {2\min_x \log (1/\phi(x))\over \log{2\over 2-\lambda}} \bigg\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$.
DOI : 10.37236/1142
Classification : 05C20, 05C50 
@article{10_37236_1142,
     author = {Fan Chung},
     title = {The diameter and {Laplacian} eigenvalues of directed graphs},
     journal = {The electronic journal of combinatorics},
     year = {2006},
     volume = {13},
     doi = {10.37236/1142},
     zbl = {1084.05031},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1142/}
}
TY  - JOUR
AU  - Fan Chung
TI  - The diameter and Laplacian eigenvalues of directed graphs
JO  - The electronic journal of combinatorics
PY  - 2006
VL  - 13
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1142/
DO  - 10.37236/1142
ID  - 10_37236_1142
ER  - 
%0 Journal Article
%A Fan Chung
%T The diameter and Laplacian eigenvalues of directed graphs
%J The electronic journal of combinatorics
%D 2006
%V 13
%U http://geodesic.mathdoc.fr/articles/10.37236/1142/
%R 10.37236/1142
%F 10_37236_1142
Fan Chung. The diameter and Laplacian eigenvalues of directed graphs. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1142

Cité par Sources :