\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Fan Chung}
%
%
\medskip
\noindent
%
%
{\bf The Diameter and Laplacian Eigenvalues of Directed Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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$.
\bye