Hamiltonicity of graphs perturbed by a random regular graph

DOI10.1002/RSA.21122MaRDI QIDQ6076213zbMATH OpenOpenAlexFDO

Authors Alberto Espuny Díaz, António Girão

Publication date 23 October 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Hamiltonicitypancyclicityrandom regular graphsrandomly perturbed graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study Hamiltonicity and pancyclicity in the graph obtained as the union of a deterministic $n$-vertex graph $H$ with $delta(H)geqalphan$ and a random $d$-regular graph $G$, for $din1,2$. When $G$ is a random $2$-regular graph, we prove that a.a.s. $HcupG$ is pancyclic for all $alphain(0,1]$, and also extend our result to a range of sublinear degrees. When $G$ is a random $1$-regular graph, we prove that a.a.s. $HcupG$ is pancyclic for all $alphain(sqrt2-1,1]$, and this result is best possible. Furthermore, we show that this bound on $delta(H)$ is only needed when $H$ is `far' from containing a perfect matching, as otherwise we can show results analogous to those of random $2$-regular graphs. Our proofs provide polynomial-time algorithms to find cycles of any length.

Recommendations

• Cycle lengths in randomly perturbed graphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Random perturbation of sparse graphs

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A threshold result for loose Hamiltonicity in random regular uniform hypergraphs
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Dirac's theorem for random regular graphs
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• Hamilton -cycles in randomly perturbed hypergraphs
• Hamiltonicity in randomly perturbed hypergraphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• High powers of Hamiltonian cycles in randomly augmented graphs
• How many random edges make a dense graph hamiltonian?
• scientific article; zbMATH DE number 3632537 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• Powers of Hamiltonian cycles in randomly augmented graphs
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Random perturbation of sparse graphs
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Random regular graphs of high degree
• Some Theorems on Abstract Graphs
• Spanning trees in randomly perturbed graphs
• Sprinkling a few random edges doubles the power
• Tilings in randomly perturbed dense graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Triangles in randomly perturbed graphs
• Universality for bounded degree spanning trees in randomly perturbed graphs

Cited in

(7)

• On the Hamiltonicity of random bipartite graphs
• On Hamiltonicity of uniform random intersection graphs
• Cycle lengths in randomly perturbed graphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• How many random edges make an almost-Dirac graph Hamiltonian?
• Minors, connectivity, and diameter in randomly perturbed sparse graphs

This page was built for publication: Hamiltonicity of graphs perturbed by a random regular graph

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