Compatible Hamilton cycles in Dirac graphs

DOI10.1007/S00493-016-3328-7zbMATH Open1399.05143arXiv1410.1435OpenAlexW2293139534MaRDI QIDQ681601FDOQ681601

Authors: Michael Krivelevich, Choongbum Lee, Benny Sudakov

Publication date: 12 February 2018

Published in: Combinatorica (Search for Journal in Brave)

Abstract: A graph is Hamiltonian if it contains a cycle passing through every vertex exactly once. A celebrated theorem of Dirac from 1952 asserts that every graph on

n g e 3

vertices with minimum degree at least

n / 2

is Hamiltonian. We refer to such graphs as Dirac graphs. In this paper we obtain the following strengthening of this result. Given a graph

G = (V, E)

, an {em incompatibility system}

m a t h c a l F

over

G

is a family

m a t h c a l F = {F_{v}}_{v i n V}

such that for every

v i n V

, the set

F_{v}

is a set of unordered pairs

F_{v} s u b s e t e q e, e^{'} : e e e^{'} i n E, e c a p e^{'} = v

. An incompatibility system is {em

D e l t a

-bounded} if for every vertex

v

and an edge

e

incident to

v

, there are at most

D e l t a

pairs in

F_{v}

containing

e

. We say that a cycle

C

in

G

is {em compatible} with

m a t h c a l F

if every pair of incident edges

e, e^{'}

of

C

satisfies

e, e^{'} o t i n F_{v}

, where

v = e c a p e^{'}

. This notion is partly motivated by a concept of transition systems defined by Kotzig in 1968, and can be viewed as a quantitative measure of robustness of graph properties. We prove that there is a constant