How many random edges make a dense graph hamiltonian?

DOI10.1002/RSA.10070MaRDI QIDQ4798179zbMATH OpenOpenAlexWikidataFDO

Authors Tom Bohman, Ryan R. Martin, Alan Frieze

Publication date 19 March 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton cyclerandom digraphrandom graphrotation method

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding $Theta(n)$ random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs.

Recommendations

• Hamilton cycles in a class of random directed graphs
• Dirac's theorem for random graphs
• On the number of hamilton cycles in a random graph
• Random directed graphs are robustly Hamiltonian
• Powers of Hamiltonian cycles in randomly augmented graphs

Cited in

(75)

• Random induced graphs
• Hamilton -cycles in randomly perturbed hypergraphs
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Random perturbation of sparse graphs
• Small rainbow cliques in randomly perturbed dense graphs
• 2-universality in randomly perturbed graphs
• Isoperimetric numbers of randomly perturbed intersection graphs
• On prisms, Möbius ladders and the cycle space of dense graphs
• Hamiltonian completions of sparse random graphs
• On the Hamiltonicity of random bipartite graphs
• Getting a directed Hamilton cycle two times faster
• Smoothed Analysis on Connected Graphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Hamiltonicity thresholds in Achlioptas processes
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis
• Vertex Ramsey properties of randomly perturbed graphs
• On a sparse random graph with minimum degree three: likely Pósa sets are large
• Adding random edges to dense graphs
• Sprinkling a few random edges doubles the power
• The effect of adding randomly weighted edges
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• The genus of the Erdős-Rényi random graph and the fragile genus property
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Maker-Breaker games on randomly perturbed graphs
• Large Rainbow Cliques in Randomly Perturbed Dense Graphs
• Powers of Hamiltonian cycles in randomly augmented graphs
• Tree decompositions of graphs without large bipartite holes
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Hamilton cycles in random graphs with a fixed degree sequence
• Triangles in randomly perturbed graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Embedding clique-factors in graphs with low -independence number
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• High powers of Hamiltonian cycles in randomly augmented graphs
• Powers of Hamiltonian cycles in randomly augmented Dirac graphs—The complete collection
• Cycle lengths in randomly perturbed graphs
• Factors in randomly perturbed hypergraphs
• Rainbow trees in uniformly edge‐colored graphs
• Hamiltonicity of graphs perturbed by a random regular graph
• On powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• Hamilton completion and the path cover number of sparse random graphs
• Speeding up random walk mixing by starting from a uniform vertex
• Entropy bounds for perfect matchings and Hamiltonian cycles
• The square of a Hamilton cycle in randomly perturbed graphs
• A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
• Hamiltonicity of randomly perturbed graphs
• Rainbow cliques in randomly perturbed dense graphs
• Schur properties of randomly perturbed sets
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• Almost spanning universality in random graphs
• On oriented cycles in randomly perturbed digraphs
• Spanning trees in graphs without large bipartite holes
• Cycles and trees in randomly perturbed sparse digraphs
• How many random edges make an almost-Dirac graph Hamiltonian?
• Fragile minor-monotone parameters under a random edge perturbation
• Rainbow subgraphs of uniformly coloured randomly perturbed graphs
• Rainbow Hamiltonicity in uniformly coloured perturbed digraphs
• Average-case and smoothed analysis of graph isomorphism
• On product Schur triples in the integers
• Minors, connectivity, and diameter in randomly perturbed sparse graphs
• Tangled paths: a random graph model from Mallows permutations
• Smoothed analysis of the Komlós conjecture: Rademacher noise
• Rainbow connectivity of randomly perturbed graphs
• Rainbow spanning trees in uniformly coloured perturbed graphs (extended abstract)
• Cycles of every length and orientation in randomly perturbed digraphs (extended abstract)
• Hamiltonicity of random subgraphs of the hypercube
• Randomly perturbed digraphs also have bounded-degree spanning trees
• Hamiltonicity in randomly perturbed hypergraphs
• On two Hamilton cycle problems in random graphs

This page was built for publication: How many random edges make a dense graph hamiltonian?

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