A randomized construction of high girth regular graphs

2019/11/21 by Linial, Nati, Simkin, Michael · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1911.09640

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)

Cited by

• Topological weak containment
• Halfway to induced saturation for even cycles

Related

• Local algorithms, regular graphs of large girth, and random regular graphs
• New small regular graphs of given girth: the cage problem and beyond
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three
• Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections