arXiv Analytics

Sign in

arXiv:1107.4947 [math.CO]AbstractReferencesReviewsResources

On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three

Alan Frieze

Published 2011-07-25, updated 2011-08-08Version 3

We describe and analyse a simple greedy algorithm \2G\ that finds a good 2-matching $M$ in the random graph $G=G_{n,cn}^{\d\geq 3}$ when $c\geq 15$. A 2-matching is a spanning subgraph of maximum degree two and $G$ is drawn uniformly from graphs with vertex set $[n]$, $cn$ edges and minimum degree at least three. By good we mean that $M$ has $O(\log n)$ components. We then use this 2-matching to build a Hamilton cycle in $O(n^{1.5+o(1)})$ time \whp.

Comments: Companion paper to "On a sparse random graph with minimum degree {three}: Likely Posa's sets are large"
Categories: math.CO
Related articles: Most relevant | Search more
arXiv:2010.08592 [math.CO] (Published 2020-10-16)
The threshold for the square of a Hamilton cycle
arXiv:1606.07833 [math.CO] (Published 2016-06-24)
Square of Hamilton cycle in a random graph
arXiv:1809.07534 [math.CO] (Published 2018-09-20)
Triangle resilience of the square of a Hamilton cycle in random graphs