Premium
A randomized construction of high girth regular graphs
Author(s) -
Linial Nati,
Simkin Michael
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20976
Subject(s) - combinatorics , mathematics , vertex (graph theory) , girth (graph theory) , odd graph , discrete mathematics , graph , chordal graph , 1 planar graph
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 / 2labeled k ‐regular n ‐vertex graphs with girth at least g .