Journal of Combinatorics
Volume 4 (2013)
On a sparse random graph with minimum degree three: Likely Pósa sets are large
Pages: 123 – 156
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$.
random, sparse graphs, degrees, longest path, Pósa sets
2010 Mathematics Subject Classification
05C30, 05C80, 34E05, 60C05