Thumbnail
Access Restriction
Open

Author Krivelevich, Michael ♦ Lee, Choongbum ♦ Sudakov, Benny
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Dirac Graph ♦ Robust Hamiltonicity ♦ Random Subgraph ♦ General Framework ♦ Cn Log ♦ Maker-breaker Game ♦ Hamiltonian Subgraph ♦ Absolute Constant ♦ Minimum Degree ♦ Classical Theorem ♦ Strong Sense ♦ Dirac Theorem ♦ Constant Factor
Abstract A graph is Hamiltonian if it contains a cycle which passes through every vertex of the graph exactly once. A classical theorem of Dirac from 1952 asserts that every graph on n vertices with minimum degree at least n/2 is Hamiltonian. We refer to such graphs as Dirac graphs. In this paper we extend Dirac’s theorem in two directions and show that Dirac graphs are robustly Hamiltonian in a very strong sense. First, we consider a random subgraph of a Dirac graph obtained by taking each edge independently with probability p, and prove that there exists a constant C such that if p ≥ C log n/n, then a.a.s. the resulting random subgraph is still Hamiltonian. Second, we prove that if a (1: b) Maker-Breaker game is played on a Dirac graph, then Maker can construct a Hamiltonian subgraph as long as the bias b is at most cn / log n for some absolute constant c> 0. Both of these results are tight up to a constant factor, and are proved under one general framework. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article