Long paths and Hamiltonicity in random graphs

zbMATH Open1408.05075arXiv1507.00205MaRDI QIDQ5283764FDOQ5283764

Authors: Michael Krivelevich 

Publication date: 24 July 2017

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.

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)

Cited In (17)

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