The algebraic connectivity of a graph is the numerically second smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian
matrix of a graph 
. In other words, it is the second smallest root of the graph's
Laplacian polynomial. This eigenvalue is
greater than 0 iff 
is a connected graph.
The ratio of the Laplacian spectral radius to algebraic connectivity is known as the Laplacian spectral ratio.
For a connected 
-regular graph 
, the relaxation time of the random
walk on 
is 
,
where 
is the algebraic connectivity. Abdi and Ghorbani (2026) proved that the maximum relaxation
time among connected regular
graphs on 
vertices is at most
 |
with asymptotic equality for even 
. For every fixed minimum vertex
degree 
,
they also proved that graphs of sufficiently large order
having minimum algebraic connectivity have the conjectured path-like block structure.
They proved the corresponding statement for fixed odd 
-regular graphs and showed
that asymptotically minimum algebraic connectivity entails asymptotically maximum
diameter in these cases.
