Long paths and Hamiltonicity in random graphs

MaRDI QIDQ5283764zbMATHFDO

Authors Michael Krivelevich

Publication date 24 July 2017

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: We discuss several classical results about long paths and Hamilton cycles in random graphs and present accessible versions of their proofs, relying on the Depth First Search (DFS) algorithm and the notion of boosters.

Cited in

(17)

• Crux and Long Cycles in Graphs
• Spanning Trees at the Connectivity Threshold
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Random perturbation of sparse graphs
• Color‐biased Hamilton cycles in random graphs
• Dirac's theorem for random regular graphs
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• Hamiltonian Berge cycles in random hypergraphs
• Asymptotics in percolation on high-girth expanders
• Ramsey goodness of clique versus paths in random graphs
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• The planted matching problem: sharp threshold and infinite-order phase transition
• Cycle lengths in expanding graphs
• Cycle lengths in randomly perturbed graphs
• Hamilton completion and the path cover number of sparse random graphs
• Oriented discrepancy of Hamilton cycles
• Random graph's Hamiltonicity is strongly tied to its minimum degree

This page was built for publication: Long paths and Hamiltonicity in random graphs

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