High powers of Hamiltonian cycles in randomly augmented graphs

DOI10.1002/JGT.22691MaRDI QIDQ6056783zbMATH OpenOpenAlexWikidataFDO

Authors Sylwia Antoniuk, Andrzej Dudek, Christian Reiher, Andrzej Ruciński, M. Schacht

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

augmented graphspowers of Hamilton cycles

Mathematics Subject Classification ID

Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45)

Abstract: We investigate the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. For all integers $kgeq1$, $rgeq0$, and $ellgeq(r+1)r$, and for any $alpha>frackk+1$ we show that adding $O(n^{2-2/ell})$ random edges to an $n$-vertex graph $G$ with minimum degree at least $alphan$ yields, with probability close to one, the existence of the $(kell+r)$-th power of a Hamiltonian cycle. In particular, for $r=1$ and $ell=2$ this implies that adding $O(n)$ random edges to such a graph $G$ already ensures the $(2k+1)$-st power of a Hamiltonian cycle (proved independently by Nenadov and Truji'c). In this instance and for several other choices of $k$, $ell$, and $r$ we can show that our result is asymptotically optimal.

Recommendations

• Powers of Hamiltonian cycles in randomly augmented graphs
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• On powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Powers of Hamiltonian cycles in randomly augmented Dirac graphs—The complete collection
• Powers of Hamilton cycles in pseudorandom graphs
• Powers of Hamilton cycles in pseudorandom graphs
• Hamilton -cycles in randomly perturbed hypergraphs
• On the number of hamilton cycles in a random graph
• Hamiltonian cycles in random regular graphs

Cites work

• \(H\)-factors in dense graphs
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• How many random edges make a dense graph hamiltonian?
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1286511 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• On extremal problems of graphs and generalized graphs
• Powers of Hamiltonian cycles in randomly augmented graphs
• Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
• Some Theorems on Abstract Graphs
• Sprinkling a few random edges doubles the power
• Supersaturated graphs and hypergraphs

Cited in

(13)

• Sprinkling a few random edges doubles the power
• Powers of Hamiltonian cycles in randomly augmented graphs
• Triangles in randomly perturbed graphs
• Powers of Hamiltonian cycles in randomly augmented Dirac graphs—The complete collection
• Rainbow trees in uniformly edge‐colored graphs
• Hamiltonicity of graphs perturbed by a random regular graph
• On powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• The square of a Hamilton cycle in randomly perturbed graphs
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• How many random edges make an almost-Dirac graph Hamiltonian?
• Rainbow subgraphs of uniformly coloured randomly perturbed graphs
• Minors, connectivity, and diameter in randomly perturbed sparse graphs

This page was built for publication: High powers of Hamiltonian cycles in randomly augmented graphs

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