Contents Online

# 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: http://dx.doi.org/10.4310/JOC.2013.v4.n2.a1

#### Authors

#### 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