Directed Hamilton cycles in digraphs and matching alternating Hamilton cycles in bipartite graphs

DOI10.1137/110837188MaRDI QIDQ5300495zbMATH OpenOpenAlexFDO

Authors Zan-Bo Zhang, Xiaoyan Zhang, Xuelian Wen

Publication date 27 June 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

degree sumdirected Hamilton cyclematching alternating Hamilton cycleOre-type condition

Mathematics Subject Classification ID

Vertex degrees (05C07) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In 1972, Woodall raised the following Ore type condition for directed Hamilton cycles in digraphs: Let $D$ be a digraph. If for every vertex pair $u$ and $v$, where there is no arc from $u$ to $v$, we have $d^{+}u)+d^{-}(v)geq|D|$, then $D$ has a directed Hamilton cycle. By a correspondence between bipartite graphs and digraphs, the above result is equivalent to the following result of Las Vergnas: Let $G=(B,W)$ be a balanced bipartite graph. If for any $binB$ and $winW$, where $b$ and $w$ are nonadjacent, we have $d(w)+d(b)geq|G|/2+1$, then every perfect matching of $G$ is contained in a Hamilton cycle. The lower bounds in both results are tight. In this paper, we reduce both bounds by $1$, and prove that the conclusions still hold, with only a few exceptional cases that can be clearly characterized.

Recommendations

• Sufficient conditions for Hamiltonian cycles in bipartite digraphs
• scientific article; zbMATH DE number 4177106
• On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs
• Orientations of Hamiltonian cycles in bipartite digraphs
• A note on dominating pair degree condition for Hamiltonian cycles in balanced bipartite digraphs

Cited in

(15)

• M-alternating Hamilton paths and M-alternating Hamilton cycles
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems
• On degree sum conditions for directed path-factors with a specified number of paths
• Partitioning the vertices of a digraph into directed cycles and degenerated directed cycles
• On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs
• scientific article; zbMATH DE number 7641244 (Why is no real title available?)
• Disjoint Cycles in a Digraph with Partial Degree
• Degree sum condition on distance 2 vertices for Hamiltonian cycles in balanced bipartite graphs
• Hamiltonicity, pancyclicity, and full cycle extendability in multipartite tournaments
• Extremal digraphs on Woodall‐type condition for Hamiltonian cycles in balanced bipartite digraphs
• A new sufficient condition for a 2-strong digraph to be Hamiltonian
• The structure of (even) directed cycles
• Bipartite independent set reconfiguration: general and RNA-inspired parameterized algorithms
• Bipartite graphs with every matching in a cycle

This page was built for publication: Directed Hamilton cycles in digraphs and matching alternating Hamilton cycles in bipartite graphs

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