Robust Hamiltonicity of Dirac graphs

Details Robust Hamiltonicity of Dirac graphs Robust Hamiltonicity of Dirac graphs

2012-01-10

arxiv.org/abs/1201.2202v1

Mathematics

Combinatorics

36 pages

Scientific paper

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 \ge 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.

Affiliated with

Also associated with

No associations

Rating

Robust Hamiltonicity of Dirac graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Robust Hamiltonicity of Dirac graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust Hamiltonicity of Dirac graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-602935