Compatible Hamilton cycles in Dirac graphs

DOI10.1007/S00493-016-3328-7MaRDI QIDQ681601zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich, Choongbum Lee, Benny Sudakov

Publication date 12 February 2018

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

compatible Hamilton cyclesrobustness of graph propertiestheorem of Dirac

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

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 $nge3$ 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} $mathcalF$ over $G$ is a family $mathcalF={F_v}_{vinV}$ such that for every $vinV$, the set $F_v$ is a set of unordered pairs $F_{v}subseteqe,e^{\prime }:ee{e}^{\prime }inE,ecap{e}^{\prime }=v$. An incompatibility system is {em $Delta$-bounded} if for every vertex $v$ and an edge $e$ incident to $v$, there are at most $Delta$ pairs in $F_v$ containing $e$. We say that a cycle $C$ in $G$ is {em compatible} with $mathcalF$ if every pair of incident edges $e,e^{\prime }$ of $C$ satisfies $e,e^{\prime }otin{F}_v$, where $v=ecap{e}^{\prime }$. 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 $mu>0$ such that for every $mun$-bounded incompatibility system $mathcalF$ over a Dirac graph $G$, there exists a Hamilton cycle compatible with $mathcalF$. This settles in a very strong form, a conjecture of H"{a}ggkvist from 1988.

Recommendations

• Hamiltonian cycles in Dirac graphs
• Hamiltonian cycles of certain kinds of graphs satisfying Dirac condition
• On the number of Hamiltonian cycles in Dirac graphs
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
• Counting Hamilton cycles in Dirac hypergraphs
• Compatible Hamilton cycles in random graphs
• scientific article; zbMATH DE number 568821
• Hamilton cycles in hypergraphs below the Dirac threshold
• Hamiltonian cycles in directed Toeplitz graphs
• scientific article; zbMATH DE number 7641244

Cites work

• scientific article; zbMATH DE number 1286511 (Why is no real title available?)
• scientific article; zbMATH DE number 1067836 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• A property of the colored complete graph
• A sufficient condition for Hamiltonian circuits
• Alternating Hamiltonian cycles
• Compatible Hamilton cycles in random graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Edge-disjoint Hamilton cycles in graphs
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Graphs with cycles having adjacent lines different colors
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamiltonian circuits in random graphs
• Hamiltonian cycles in Dirac graphs
• Local resilience of graphs
• On prisms, Möbius ladders and the cycle space of dense graphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Robust Hamiltonicity of Dirac graphs

Cited in

(10)

• Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems
• Counting oriented trees in digraphs with large minimum semidegree
• A rainbow Dirac's theorem
• Properly colored Hamilton cycles in Dirac-type hypergraphs
• Compatible powers of Hamilton cycles in dense graphs
• Some Hamiltonian properties of one-conflict graphs
• Hamiltonian cycles in Dirac graphs
• Connectivity preserving Hamiltonian cycles in \(k\)-connected Dirac graphs
• scientific article; zbMATH DE number 3922699 (Why is no real title available?)
• Graph Tilings in Incompatibility Systems

This page was built for publication: Compatible Hamilton cycles in Dirac graphs

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