10.1184/R1/6478643.v1
Alan Frieze
Alan
Frieze
Boris Pittel
Boris
Pittel
On a sparse random graph with minimum degree three: Likely Pósa sets are large
Carnegie Mellon University
2013
random
sparse graphs
degrees
longest path
Posa sets
2013-01-13 00:00:00
Journal contribution
https://kilthub.cmu.edu/articles/journal_contribution/On_a_sparse_random_graph_with_minimum_degree_three_Likely_P_sa_sets_are_large/6478643
<p>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≥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.</p>