Powers of Hamiltonian cycles in randomly augmented graphs

DOI10.1002/RSA.20870zbMATH Open1444.05080arXiv1805.10676OpenAlexW3101759291MaRDI QIDQ5113934FDOQ5113934

Andrzej Ruciński, Christian Reiher, M. Schacht, Andrzej Dudek

Publication date: 19 June 2020

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

Abstract: We study 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. It follows from the theorems of Dirac and of Koml'os, Sark"ozy, and Szemer'edi that for every $kgeq1$ and sufficiently large $n$ already the minimum degree $delta(G)gefrackk+1n$ for an $n$-vertex graph $G$ alone suffices to ensure the existence of a $k$-th power of a Hamiltonian cycle. Here we show that under essentially the same degree assumption the addition of just $O(n)$ random edges ensures the presence of the $(k+1)$-st power of a Hamiltonian cycle with probability close to one.

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

zbMATH Keywords

random graphspowers of Hamiltonian cyclesminimum degree conditions

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (23)

• Hamiltonicity of graphs perturbed by a random geometric graph
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Rainbow Hamilton Cycles in Randomly Colored Randomly Perturbed Dense Graphs
• Factors in randomly perturbed hypergraphs
• Sprinkling a Few Random Edges Doubles the Power
• Vertex Ramsey properties of randomly perturbed graphs
• The Effect of Adding Randomly Weighted Edges
• The square of a Hamilton cycle in randomly perturbed graphs
• High powers of Hamiltonian cycles in randomly augmented graphs
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• Powers of Hamiltonian cycles in randomly augmented Dirac graphs—The complete collection
• How many random edges make a dense graph hamiltonian?
• On powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Cycle lengths in randomly perturbed graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Rainbow trees in uniformly edge‐colored graphs
• Triangles in randomly perturbed graphs
• Small rainbow cliques in randomly perturbed dense graphs
• Large Rainbow Cliques in Randomly Perturbed Dense Graphs
• Random perturbation of sparse graphs
• Hamiltonicity of graphs perturbed by a random regular graph
• Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers
• Ramsey properties of randomly perturbed graphs: cliques and cycles

This page was built for publication: 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 Q5113934)