Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures
Abstract
Aldous and Fill (2002) conjectured that the maximum relaxation time of a random walk on a connected regular graph with n vertices is bounded above by (1+o(1))3n2/2π2, with asymptotic equality for even n. Since the relaxation time of a d-regular graph G is d/μ(G), where μ(G) denotes its algebraic connectivity, this conjecture is closely related to the problem of minimizing algebraic connectivity among regular graphs. Guiduli and Mohar (1996) conjectured that, for every fixed minimum degree δ=d≥ 3 and all sufficiently large orders, graphs with minimum algebraic connectivity are path-like and, apart from bounded portions near their two ends, have a prescribed block structure. For fixed odd degree d≥ 3, Abdi and Ghorbani (2004) conjectured that d-regular graphs with minimum algebraic connectivity have the same structure. We prove the Aldous--Fill conjecture and the Guiduli--Mohar conjecture, as well as the corresponding conjecture for d-regular graphs of fixed odd degree. Finally, we prove that, for every fixed odd degree d≥ 3, d-regular graphs, as well as graphs of fixed minimum degree d≥ 3, whose algebraic connectivity is asymptotically minimum have asymptotically maximum diameter. This establishes the corresponding cases of another conjecture of Abdi and Ghorbani.
Related
- Graphs with Minimum Algebraic Connectivity II: Regular Graphs of Even Degree
- On the structure of graphs with given odd girth and large algebraic connectivity
- Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree
- The Algebraic Connectivity and Laplacian Spectral Radius of Token Graphs
- Neither simpliciality nor mutation connectivity: conjectures of Las Vergnas and Cordovil-Las Vergnas fail
BibTeX
@misc{abdi2026graphs,
title = {{Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures}},
author = {Maryam Abdi and Ebrahim Ghorbani},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26699},
eprint = {2609.26699},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26699},
}
RIS
TY - UNPB
TI - Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures
AU - Maryam Abdi
AU - Ebrahim Ghorbani
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.26699
UR - https://arxiv.org/abs/2609.26699
AB - Aldous and Fill (2002) conjectured that the maximum relaxation time of a random walk on a connected regular graph with n vertices is bounded above by (1+o(1))3n^2/2π^2, with asymptotic equality for even n. Since the relaxation time of a d-regular graph G is d/μ(G), where μ(G) denotes its algebraic connectivity, this conjecture is closely related to the problem of minimizing algebraic connectivity among regular graphs. Guiduli and Mohar (1996) conjectured that, for every fixed minimum degree δ=d≥ 3 and all sufficiently large orders, graphs with minimum algebraic connectivity are path-like and, apart from bounded portions near their two ends, have a prescribed block structure. For fixed odd degree d≥ 3, Abdi and Ghorbani (2004) conjectured that d-regular graphs with minimum algebraic connectivity have the same structure. We prove the Aldous--Fill conjecture and the Guiduli--Mohar conjecture, as well as the corresponding conjecture for d-regular graphs of fixed odd degree. Finally, we prove that, for every fixed odd degree d≥ 3, d-regular graphs, as well as graphs of fixed minimum degree d≥ 3, whose algebraic connectivity is asymptotically minimum have asymptotically maximum diameter. This establishes the corresponding cases of another conjecture of Abdi and Ghorbani.
ER -