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

We study the powers of Hamiltonian cycles in randomly augmented Dirac graphs, that is, n $n$‐vertex graphs G $G$ with minimum degree at least (1∕2+ε)n $(1\unicode{x02215}2+\varepsilon )n$ to which some random edges are added. For any Dirac graph and every integer m≥2 $m\ge 2$, we accurately estimate...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2023-12, Vol.104 (4), p.811-835
Main Authors: Antoniuk, Sylwia, Dudek, Andrzej, Ruciński, Andrzej
Format: Article
Language:English
Subjects:
Dirac graphs
Graph theory
Graphs
powers of Hamiltonian cycles
random graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the powers of Hamiltonian cycles in randomly augmented Dirac graphs, that is, n $n$‐vertex graphs G $G$ with minimum degree at least (1∕2+ε)n $(1\unicode{x02215}2+\varepsilon )n$ to which some random edges are added. For any Dirac graph and every integer m≥2 $m\ge 2$, we accurately estimate the threshold probability p=p(n) $p=p(n)$ for the event that the random augmentation G∪G(n,p) $G\cup G(n,p)$ contains the m $m$‐th power of a Hamiltonian cycle.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.23001