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

DOI10.4310/JOC.2013.V4.N2.A1zbMATH Open1275.05051arXiv1107.4944OpenAlexW1996769307MaRDI QIDQ376545FDOQ376545

Authors: Alan Frieze, Boris Pittel 

Publication date: 5 November 2013

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

Abstract: We consider the likely size of the endpoint sets produced by Posa rotations, when applied to a longest path in a random graph with $cn,,cgeq2.7$ edges that is conditioned to have minimum degree at least three.

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

Recommendations

• Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis
• On Pósa's conjecture for random graphs
• Local resilience of an almost spanning k‐cycle in random graphs
• How many random edges make a dense graph hamiltonian?
• On the Number of Hamilton Cycles in Sparse Random Graphs

zbMATH Keywords

sparse graphsdegreeslongest pathPósa rotationsPósa sets

Mathematics Subject Classification ID

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

Cited In (3)

• Hamilton cycles in random graphs with minimum degree at least 3: An improved analysis
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q376545)