Journal of Combinatorics

Volume 4 (2013)

Number 2

On a sparse random graph with minimum degree three: Likely Pósa sets are large

Pages: 123 – 156

DOI: https://dx.doi.org/10.4310/JOC.2013.v4.n2.a1

Authors

Alan Frieze (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Penn., U.S.A.)

Boris Pittel (Department of Mathematics, Ohio State University, Columbus, Oh., U.S.A.)

Abstract

We consider the endpoint sets produced by Pósa rotations, when applied to a longest path in a random graph with $cn$ edges, conditioned on having minimum degree at least three. We prove that, for $c \geq 2.7$, the Pósa sets are likely to be almost linear in $n$, implying that the number of missing edges, each allowing either to get a longer path or to form a Hamilton cycle, is almost quadratic in $n$.

Keywords

random, sparse graphs, degrees, longest path, Pósa sets

2010 Mathematics Subject Classification

05C30, 05C80, 34E05, 60C05

Published 13 August 2013