  Aldous and Fill (2002) conjectured that the maximum relaxation time for the
random walk on a connected regular graph with $n$ vertices is
$(1+o(1))\frac{3n^2}{2\pi^2}$. A conjecture by Guiduli and Mohar (1997)
predicts the structure of graphs whose algebraic connectivity $\mu$ is the
smallest among all connected graphs whose minimum degree $\delta$ is a given
$d$. We prove that this conjecture implies Aldous--Fill conjecture for odd $d$.
We pose another conjecture on the structure of $d$-regular graphs with minimum
$\mu$, and show that this also implies Aldous--Fill conjecture for even $d$. In
the literature, it has been noted empirically that graphs with small $\mu$ tend
to have a large diameter. Guiduli asked if the cubic graphs with maximum
diameter have algebraic connectivity smaller than all others. We investigate
the interplay between the graphs with maximum diameter and those with minimum
algebraic connectivity. We show that the answer to Guiduli problem in its
general form, that is for $d$-regular graphs for every $d\ge3$ is negative. We
try to come up with an asymptotic formulation of the problem. We prove that for
$d=3,4$, $d$-regular graphs with asymptotic maximum diameter have
asymptotically smallest $\mu$. It is shown that this fails for $d$-regular
graphs with $d\ge5$ as well as graphs with $\delta=d$ with $d\ge4$. We
conjecture that $d$-regular graphs (or graphs with $\delta=d$) that have
asymptotically smallest $\mu$, should have asymptotically maximum diameter. The
above results rely heavily on our understanding of the structure as well as
optimal estimation of the algebraic connectivity of graphs with asymptotic
maximum diameter. As another by-product, we prove that the minimum algebraic
connectivity of $d$-regular graphs of order $n$ or graphs with $\delta=d$ is
$\Theta(d/n^2)$, and also settle Aldous--Fill conjecture for graphs with
asymptotic maximum diameter.
