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

random graphHamilton cyclerotation methodrandom digraph

Mathematics Subject Classification ID

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

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)

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