A randomized construction of high girth regular graphs

Abstract

We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k\ge 3$ and $c\in (0,1)$ be fixed. Let $n\in \mathbb{N}$ be even and set $g=c{\log }_{k-1}(n)$. Begin with a Hamilton cycle $G$ on $n$ vertices. As long as the smallest degree $\hat{I}´(G)<k$, choose, uniformly at random, two vertices $u,v\in V(G)$ of degree $\hat{I}´(G)$ whose distance is at least $g-1$. If there are no such vertex pairs, abort. Otherwise, add the edge $uv$ to $E(G)$. We show that with high probability this algorithm yields a $k$-regular graph with girth at least $g$. Our analysis also implies that there are ${\left(\hat{I}\text{c◯}(n)\right)}^{kn/2}$ labeled $k$-regular $n$-vertex graphs with girth at least $g$.

26 pages. Corrected minor typos. Added remarks to improve exposition