Powers of Hamiltonian cycles in randomly augmented Dirac graphs—The complete collection

DOI10.1002/JGT.23001MaRDI QIDQ6062872zbMATH OpenFDO

Authors Sylwia Antoniuk, Andrzej Dudek, Andrzej Ruciński

Publication date 6 November 2023

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

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

zbMATH Keywords

Dirac graphspowers of Hamiltonian cyclesrandom graphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the powers of Hamiltonian cycles in randomly augmented Dirac graphs, that is, $n$-vertex graphs $G$ with minimum degree at least $(1/2+varepsilon)n$ to which some random edges are added. For any Dirac graph and every integer $mge2$, we accurately estimate the threshold probability $p=p(n)$ for the event that the random augmentation $GcupG(n,p)$ contains the $m$-th power of a Hamiltonian cycle.

Recommendations

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

Cites work

• High powers of Hamiltonian cycles in randomly augmented graphs
• How many random edges make a dense graph hamiltonian?
• On the square of a Hamiltonian cycle in dense graphs
• Powers of Hamiltonian cycles in randomly augmented graphs
• Proof of the Seymour conjecture for large graphs
• Some Theorems on Abstract Graphs
• Sprinkling a few random edges doubles the power

Cited in

(4)

• 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 an almost-Dirac graph Hamiltonian?
• Rainbow subgraphs of uniformly coloured randomly perturbed graphs

This page was built for publication: Powers of Hamiltonian cycles in randomly augmented Dirac graphs—The complete collection

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