{"id":"arxiv/2609.26700","url":"https://arxiv.org/abs/2609.26700","tags":["math.CO"],"score":0,"title":"Graphs with Minimum Algebraic Connectivity II: Regular Graphs of Even Degree","domain":"math.CO","source":"arxiv","authors":["Maryam Abdi","Ebrahim Ghorbani"],"reviews":0,"subject":"math.CO","summary":"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\\ge3$ 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}