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

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

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

(22)

• Random perturbation of sparse graphs
• Cycle lengths in expanding graphs
• Random graph's Hamiltonicity is strongly tied to its minimum degree
• Dirac's theorem for random regular graphs
• Hamiltonian Berge cycles in random hypergraphs
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Crux and Long Cycles in Graphs
• Spanning Trees at the Connectivity Threshold
• Asymptotics in percolation on high-girth expanders
• Ramsey goodness of clique versus paths in random graphs
• Oriented discrepancy of Hamilton cycles
• Cycle lengths in randomly perturbed graphs
• Color‐biased Hamilton cycles in random graphs
• The planted matching problem: sharp threshold and infinite-order phase transition
• Hamilton completion and the path cover number of sparse random graphs
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• How many random edges make an almost-Dirac graph Hamiltonian?
• Fast construction on a restricted budget
• Rigid partitions: from high connectivity to random graphs
• Sparse pancyclic subgraphs of random graphs
• Vertex-separating path systems in 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)