A randomized construction of high girth regular graphs. Issue 2 (18th November 2020)

• Record Type: Journal Article
• Authors: Linial, Nati; Simkin, Michael
• Is Part Of: Random structures & algorithms. Volume 58:Issue 2(2021)
• Page Start: 345
• Page End: 369
• Publication Date: 2020-11-18
• Subjects: graph processes -- high‐girth graphs -- random greedy algorithms; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20976
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .