Square of a Hamilton cycle in a random graph

Authors Patrick Bennett, Andrzej Dudek, Alan Frieze

Publication date 20 November 2016

Abstract: We show that the threshold for the random graph

G_{n, p}

to contain the square of a Hamilton cycle is

p = f r a c 1 s q r t n

. This improves the previous results of K"uhn and Osthus and also Nenadov and v{S}kori'c. In addition we consider how many random edges need to be added to a graph of order

n

with minimum degree

a l p h a n

in order that it contains the square of a Hamilton cycle w.h.p.

This page was built for publication: Square of a Hamilton cycle in a random graph

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