pith. sign in

arxiv: 1612.08904 · v2 · pith:OTOHHJTNnew · submitted 2016-12-28 · 🧮 math.CO

On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs

classification 🧮 math.CO
keywords everycyclesdirectedresultbipartitecontainingexactlyfactor
0
0 comments X
read the original abstract

In this paper, we give the following result: If $D$ is a digraph of order $n$, and if $d_{D}^{+}(u) + d_{D}^{-}(v) \ge n$ for every two distinct vertices $u$ and $v$ with $(u, v) \notin A(D)$, then $D$ has a directed $2$-factor with exactly $k$ directed cycles of length at least $3$, where $n \ge 12k+3$. This result is equivalent to the following result: If $G$ is a balanced bipartite graph of order $2n$ with partite sets $X$ and $Y$, and if $d_{G}(x)+d_{G}(y) \ge n + 2$ for every two vertices $x \in X$ and $y \in Y$ with $xy \notin E(G)$, then for every perfect matching $M$, $G$ has a $2$-factor with exactly $k$ cycles of length at least $6$ containing every edge of $M$, where $n \ge 12k+3$. These results are generalizations of theorems concerning Hamilton cycles due to Woodall (1972) and Las Vergnas (1972), respectively.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.