{"id":"arxiv/2609.26699","url":"https://arxiv.org/abs/2609.26699","tags":["math.CO"],"score":0,"title":"Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures","domain":"math.CO","source":"arxiv","authors":["Maryam Abdi","Ebrahim Ghorbani"],"reviews":0,"subject":"math.CO","summary":"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))\\frac{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\\ge 3$ and all sufficiently large orders, graphs with minimum algebraic…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}