A randomized construction of high girth regular graphs

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=clogk−1(n). Begin with a Hamilton cycle G on n vertices. As long as the smallest degree δ(G)

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2021-03, Vol.58 (2), p.345-369
Main Authors: Linial, Nati, Simkin, Michael
Format: Article
Language:English
Subjects:
Apexes
graph processes
Graphs
Greedy algorithms
high‐girth graphs
random greedy algorithms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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=clogk−1(n). Begin with a Hamilton cycle G on n vertices. As long as the smallest degree δ(G)
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20976