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

DOI10.4310/JOC.2013.V4.N2.A1zbMath1275.05051arXiv1107.4944OpenAlexW1996769307MaRDI QIDQ376545

Alan M. Frieze, Boris G. Pittel

Publication date: 5 November 2013

Published in: Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1107.4944

zbMATH Keywords

degreeslongest pathsparse graphsPósa rotationsPósa sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Combinatorial probability (60C05) Asymptotic expansions of solutions to ordinary differential equations (34E05) Density (toughness, etc.) (05C42)

Related Items (3)

An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three ⋮ A scaling limit for the length of the longest cycle in a sparse random graph ⋮ Hamilton cycles in random graphs with minimum degree at least 3: An improved analysis

This page was built for publication: On a sparse random graph with minimum degree three: likely Pósa sets are large