A randomized construction of high girth regular graphs. Issue 2 (18th November 2020) - Linial, Nati; Simkin, Michael
Abstract : We describe a new random greedy algorithm for generating regular graphs of high girth: Let k ≥ 3 and c ∈ (0, 1) be fixed. Let 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 δ ( G ) < k, choose, uniformly at random, two vertices u, v ∈ V ( G ) of degree δ ( 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 Ω ( n ) k n / 2 labeled k ‐regular n ‐vertex graphs with girth at least g .