Dirac's theorem for random graphs

DOI10.1002/RSA.20419MaRDI QIDQ3168496zbMATH OpenOpenAlexWikidataFDO

Authors Choongbum Lee, Benny Sudakov

Publication date 31 October 2012

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

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

zbMATH Keywords

Dirac's theoremrandom graphresilience

Mathematics Subject Classification ID

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

Abstract: A classical theorem of Dirac from 1952 asserts that every graph on $n$ vertices with minimum degree at least $lceiln/2ceil$ is Hamiltonian. In this paper we extend this result to random graphs. Motivated by the study of resilience of random graph properties we prove that if $pgglogn/n$, then a.a.s. every subgraph of $G(n,p)$ with minimum degree at least $(1/2+o(1))np$ is Hamiltonian. Our result improves on previously known bounds, and answers an open problem of Sudakov and Vu. Both, the range of edge probability $p$ and the value of the constant 1/2 are asymptotically best possible.

Recommendations

• Dirac's theorem for random regular graphs
• Random directed graphs are robustly Hamiltonian
• Robust Hamiltonicity of Dirac graphs
• Robust Hamiltonicity of random directed graphs
• Random graph's Hamiltonicity is strongly tied to its minimum degree

Cites work

• Almost all regular graphs are Hamiltonian
• Bandwidth theorem for random graphs
• Hamiltonian circuits in random graphs
• Increasing the chromatic number of a random graph
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Local resilience of almost spanning trees in random graphs
• Local resilience of graphs
• Long cycles in subgraphs of (pseudo)random directed graphs
• On the asymmetry of random regular graphs and random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On the resilience of long cycles in random graphs
• On two Hamilton cycle problems in random graphs
• Resilient pancyclicity of random and pseudorandom graphs
• Some Theorems on Abstract Graphs
• Turán's extremal problem in random graphs: Forbidding even cycles
• Turán's extremal problem in random graphs: Forbidding odd cycles

Cited in

(50)

• Random induced graphs
• Dirac-type theorems in random hypergraphs
• A Dirac-type theorem for Berge cycles in random hypergraphs
• Random graph's Hamiltonicity is strongly tied to its minimum degree
• Rainbow factors in hypergraphs
• Hamiltonicity below Dirac's condition
• Spanning trees in random graphs
• Hamiltonicity in random graphs is born resilient
• Robust Hamiltonicity of random directed graphs
• Local resilience for squares of almost spanning cycles in sparse random graphs
• On resilience of connectivity in the evolution of random graphs
• Recent advances on the Hamiltonian problem: survey III
• On prisms, Möbius ladders and the cycle space of dense graphs
• On the Hamiltonicity of random bipartite graphs
• Triangle resilience of the square of a Hamilton cycle in random graphs
• Random directed graphs are robustly Hamiltonian
• Creating cycles in walker-breaker games
• Sharp thresholds for half-random games. I.
• Local resilience of spanning subgraphs in sparse random graphs
• Generating random graphs in biased maker-breaker games
• scientific article; zbMATH DE number 5375038 (Why is no real title available?)
• Algebraic statistics for a directed random graph model with reciprocation
• Independent sets in hypergraphs and Ramsey properties of graphs and the integers
• On the KŁR conjecture in random graphs
• How many random edges make a dense graph hamiltonian?
• Hamiltonicity in random directed graphs is born resilient
• Dirac's theorem for random regular graphs
• Crux and Long Cycles in Graphs
• Spanning Structures in Walker–Breaker Games
• A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• Tight Hamilton cycles in random hypergraphs
• Robust Hamiltonicity of random directed graphs: extended abstract
• Robust Hamiltonicity of Dirac graphs
• A spanning bandwidth theorem in random graphs
• The global resilience of Hamiltonicity in \(G(n, p)\)
• Color‐biased Hamilton cycles in random graphs
• Covering cycles in sparse graphs
• Dirac-type theorems for inhomogenous random graphs
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
• Resilience for tight Hamiltonicity
• Resilience with respect to Hamiltonicity in random graphs
• Doubly biased walker-breaker games
• Walker-breaker games on \(G_{n, p}\)
• Hamiltonicity of sparse pseudorandom graphs
• The Hamiltonicity of quasi-random k-graphs
• Ramsey numbers of cycles in random graphs
• Cyclic subsets of tournaments
• Vertex-separating path systems in random graphs

This page was built for publication: Dirac's theorem for random graphs

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