Graphs with Minimum Algebraic Connectivity II: Regular Graphs of Even Degree
Abstract
Aldous and Fill (2002) conjectured the asymptotic maximum relaxation time of a random walk on a connected regular graph. 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. Abdi and Ghorbani (2024) proposed an analogous structural conjecture for d-regular graphs with minimum algebraic connectivity and fixed degree d≥3. In Part~I, we proved the Aldous--Fill conjecture, the Guiduli--Mohar conjecture, and for odd degrees, the Abdi Ghorbani conjecture. In this paper, we settle the remaining even-degree case, thereby completing the structural characterization of regular graphs with minimum algebraic connectivity. We also prove that, for every fixed even d≥4, the minimum algebraic connectivity at order n is 2(d−2)π2/n2+Od(n−3), and that every minimizing graph has diameter 3n/(d+1)+Od(1). For every fixed even d≥6, d-regular graphs whose algebraic connectivity is asymptotically minimum have asymptotically maximum diameter. Finally, we obtain a sharp normalized-gap bound for all even regular degrees, including degrees that grow with n.
Related
- Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures
- Connectivity and Diameter of Friends and Strangers Graphs Using Minimum Degree
- Positive Square Energy of Graphs with Minimum Degree at Least Two
- An improved minimum degree threshold for fractional clique decompositions in partite graphs
- Polynomial minimum degree stability for $3$-chromatic graphs
BibTeX
@misc{abdi2026graphs,
title = {{Graphs with Minimum Algebraic Connectivity II: Regular Graphs of Even Degree}},
author = {Maryam Abdi and Ebrahim Ghorbani},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26700},
eprint = {2609.26700},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26700},
}
RIS
TY - UNPB
TI - Graphs with Minimum Algebraic Connectivity II: Regular Graphs of Even Degree
AU - Maryam Abdi
AU - Ebrahim Ghorbani
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.26700
UR - https://arxiv.org/abs/2609.26700
AB - Aldous and Fill (2002) conjectured the asymptotic maximum relaxation time of a random walk on a connected regular graph. 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. Abdi and Ghorbani (2024) proposed an analogous structural conjecture for d-regular graphs with minimum algebraic connectivity and fixed degree d≥3. In Part~I, we proved the Aldous--Fill conjecture, the Guiduli--Mohar conjecture, and for odd degrees, the Abdi Ghorbani conjecture. In this paper, we settle the remaining even-degree case, thereby completing the structural characterization of regular graphs with minimum algebraic connectivity. We also prove that, for every fixed even d≥4, the minimum algebraic connectivity at order n is 2(d−2)π^2/n^2+O_d(n^−3), and that every minimizing graph has diameter 3n/(d+1)+O_d(1). For every fixed even d≥6, d-regular graphs whose algebraic connectivity is asymptotically minimum have asymptotically maximum diameter. Finally, we obtain a sharp normalized-gap bound for all even regular degrees, including degrees that grow with n.
ER -