A randomized construction of high girth regular graphs

DOI10.1002/RSA.20976MaRDI QIDQ6073632zbMATH OpenOpenAlexFDO

Authors Nathan Linial, Michael Simkin

Publication date 11 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.09640

zbMATH Keywords

graph processeshigh-girth graphsrandom greedy algorithms

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Abstract: We describe a new random greedy algorithm for generating regular graphs of high girth: Let $kgeq3$ and $cin(0,1)$ be fixed. Let $ninmathbbN$ be even and set $g=clo{g}_{k-1}(n)$. Begin with a Hamilton cycle $G$ on $n$ vertices. As long as the smallest degree $delta(G)<k$, choose, uniformly at random, two vertices $u,vinV(G)$ of degree $delta(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 $left(Omega(n)ight{)}^{kn/2}$ labeled $k$-regular $n$-vertex graphs with girth at least $g$.

Recommendations

• A High Girth Graph Construction
• Local algorithms, regular graphs of large girth, and random regular graphs
• Generating random graphs with large girth
• Generating Random Regular Graphs Quickly
• On regular hypergraphs of high girth

Cites work

• A High Girth Graph Construction
• A new series of dense graphs of high girth
• A proof of Alon’s second eigenvalue conjecture and related problems
• Concentration of multivariate polynomials and its applications
• Constrainted graph processes
• Constructions for cubic graphs with large girth
• Cubic Ramanujan graphs
• Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Generating random graphs with large girth
• Girths of bipartite sextet graphs
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• Large girth approximate Steiner triple systems
• On random greedy triangle packing
• On tail probabilities for martingales
• On the girth of random Cayley graphs
• On the method of typical bounded differences
• On the size of a random maximal graph
• Ramanujan graphs
• Random Graph Processes with Degree Restrictions
• Random maximalH-free graphs
• Regular graphs of large girth and arbitrary degree
• Short cycles in random regular graphs
• The C_ℓ‐free process
• The Final Size of the $C_{\ell}$-free Process
• The final size of the \(C_{4}\)-free process
• The random k-matching-free process
• The sextet construction for cubic graphs
• The triangle-free process

Cited in

(14)

• Greedy construction of nearly regular graphs
• Randomized construction of complexes with large diameter
• Kissing numbers of regular graphs
• Generating incidence structures with given girth
• On regular hypergraphs of high girth
• A High Girth Graph Construction
• scientific article; zbMATH DE number 1500656 (Why is no real title available?)
• Generating random graphs with large girth
• Regular graphs of large girth and arbitrary degree
• Riemann surfaces: random, flat, and hyperbolic geometry. Abstracts from the workshop held September 8--13, 2024
• Translation surfaces with large systoles
• High-girth near-Ramanujan graphs with lossy vertex expansion
• A unimodular random graph with large upper growth and no growth
• Random surfaces with large systoles

This page was built for publication: A randomized construction of high girth regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6073632)