Powers of Hamiltonian cycles in randomly augmented graphs

DOI10.1002/RSA.20870MaRDI QIDQ5113934zbMATH OpenOpenAlexFDO

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

Publication date 19 June 2020

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

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)

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.

Recommendations

• High powers of Hamiltonian cycles in randomly augmented graphs
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• Sprinkling a few random edges doubles the power
• How many random edges make a dense graph hamiltonian?
• Powers of Hamilton cycles in pseudorandom graphs

Cited in

(28)

• Hamiltonicity of graphs perturbed by a random geometric graph
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Smoothed analysis of the Komlós conjecture: Rademacher noise
• Factors in randomly perturbed hypergraphs
• Vertex Ramsey properties of randomly perturbed graphs
• 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
• How many random edges make a dense graph hamiltonian?
• Powers of Hamiltonian cycles in randomly augmented Dirac graphs—The complete collection
• On powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Cycle lengths in randomly perturbed graphs
• How many random edges make an almost-Dirac graph Hamiltonian?
• Rainbow subgraphs of uniformly coloured randomly perturbed graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Powers of Hamilton cycles in pseudorandom graphs
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Rainbow trees in uniformly edge‐colored graphs
• Triangles in randomly perturbed graphs
• Sprinkling a few random edges doubles the power
• Ramsey properties of randomly perturbed hypergraphs
• The effect of adding randomly weighted edges
• 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)