Long paths and Hamiltonicity in random graphs

MaRDI QIDQ5283764zbMATH OpenFDO

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)

• Hamiltonian Berge cycles in random hypergraphs
• Spanning Trees at the Connectivity Threshold
• Dirac's theorem for random regular graphs
• Asymptotics in percolation on high-girth expanders
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• 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
• Random graph's Hamiltonicity is strongly tied to its minimum degree
• Ramsey goodness of clique versus paths in random graphs
• Hamilton completion and the path cover number of sparse random graphs

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)