Hamiltonicity of graphs perturbed by a random regular graph

We study Hamiltonicity and pancyclicity in the graph obtained as the union of a deterministic \(n\)-vertex graph \(H\) with \(\delta(H)\geq\alpha n\) and a random \(d\)-regular graph \(G\), for \(d\in\{1,2\}\). When \(G\) is a random \(2\)-regular graph, we prove that a.a.s. \(H\cup G\) is pancyclic...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-09
Main Authors: Alberto Espuny Díaz, Girão, António
Format: Article
Language:English
Subjects:
Algorithms
Graphs
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study Hamiltonicity and pancyclicity in the graph obtained as the union of a deterministic \(n\)-vertex graph \(H\) with \(\delta(H)\geq\alpha n\) and a random \(d\)-regular graph \(G\), for \(d\in\{1,2\}\). When \(G\) is a random \(2\)-regular graph, we prove that a.a.s. \(H\cup G\) is pancyclic for all \(\alpha\in(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. \(H\cup G\) is pancyclic for all \(\alpha\in(\sqrt{2}-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.
ISSN:2331-8422