A randomized construction of high girth regular graphs.

We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k\geq 3$ and $c \in (0,1)$ be fixed. Let $n \in \mathbb{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 $\delta (G)

Keywords:

• Combinatorics
• Hamiltonian path
• Graph
• Mathematics
• Greedy algorithm
• Discrete mathematics
• Omega
• Vertex (geometry)
• high probability

• Correction
• Source
• Cite
• Save
• Machine Reading By IdeaReader