Conjecture on the structure of minimum-algebraic-connectivity regular graphs

Let $d\ge3$ be an integer, and let a $\mu$-minimal $d$-regular graph be a $d$-regular graph having the smallest algebraic connectivity among graphs of its order and degree. For odd $d$, the proposed structure is the one in Figure Mohar; for even $d$, it is the different structure shown in Figure d-even.

Regular extremal-structure conjecture. For every integer $d\ge3$, there exist constants $C_1$ and $C_2$ such that any $\mu$-minimal $d$-regular graph $G$ of order at least $C_1$ is path-like and, except for a limited number of blocks at either end containing at most $C_2$ vertices in total, has the same structure as Figure Mohar for odd $d$ and as Figure d-even for even $d$.

This conjecture is intended to describe the asymptotic block structure of regular graphs minimizing algebraic connectivity. The paper uses the corresponding structures to derive implications for the Aldous–Fill conjecture, but does not establish this full statement.