Sprinkling with random regular graphs

2023/09/01 by Mikhail Isaev, Brendan D. McKay, Isaev, Mikhail +5 · 3 citations
Computer Science · Mathematics · #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2309.00190

openalex publication_date 2023/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We conjecture that the distribution of the edge-disjoint union of two random regular graphs on the same vertex set is asymptotically equivalent to a random regular graph of the combined degree, provided it grows as the number of vertices tends to infinity. We verify this conjecture for the cases when the graphs are sufficiently dense or sparse. We also prove an asymptotic formula for the expected number of spanning regular subgraphs in a random regular graph.

Cited by

• Sandwiching between random regular graphs and Erdős-Rényi graphs: configuration model and unions of perfect matchings
• Approximate Itai-Zehavi conjecture for random graphs
• Monotonicity and decompositions of random regular graphs

Related

• On random irregular subgraphs
• Subgraph distributions in dense random regular graphs
• Monotonicity and decompositions of random regular graphs
• On the maximum number of common neighbours in dense random regular graphs
• Triangles and subgraph probabilities in random regular graphs