A randomized construction of high girth regular graphs
We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k\geq 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 \delta (G)<k$ choose, uniformly at random, two vertices $u,v \in V(G) of degree \delta(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( \Omega (n) \right){kn/2} labeled $k$ regular $n$ vertex graphs with girth at least $g$
Random Struct. Algorithms