Sprinkling a Few Random Edges Doubles the Power

DOI10.1137/19M125412XzbMath1465.05090arXiv1811.09209MaRDI QIDQ4990400

Rajko Nenadov, Miloš Trujić

Publication date: 28 May 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random graphsHamiltonicityextremal graph theory

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45)

Related Items (9)

Triangles in randomly perturbed graphs ⋮ 2-universality in randomly perturbed graphs ⋮ Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu ⋮ High powers of Hamiltonian cycles in randomly augmented graphs ⋮ Powers of Hamiltonian cycles in randomly augmented Dirac graphs—The complete collection ⋮ Factors in randomly perturbed hypergraphs ⋮ 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

Cites Work

• Vertex coverings by monochromatic cycles and trees
• Proof of the Seymour conjecture for large graphs
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Triangle Factors in Random Graphs
• Powers of Hamiltonian cycles in randomly augmented graphs
• Some Theorems on Abstract Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sprinkling a Few Random Edges Doubles the Power