Square of a Hamilton cycle in a random graph

2016/11/20 by Bennett, Patrick, Dudek, Andrzej, Frieze, Alan
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1611.06570

Abstract

We show that the threshold for the random graph G_n,p to contain the square of a Hamilton cycle is p=(1)/(√(n)). This improves the previous results of Kühn and Osthus and also Nenadov and Škorić. In addition we consider how many random edges need to be added to a graph of order n with minimum degree αn in order that it contains the square of a Hamilton cycle w.h.p.

Related

• Square of Hamilton cycle in a random graph
• The threshold for the square of a Hamilton cycle
• Adding random edges to create the square of a Hamilton cycle
• Sharp threshold for hamiltonicity of random geometric graphs
• The square of a Hamilton cycle in randomly perturbed graphs