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

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) g e n

for every two distinct vertices

u

and

v

with

(u, v) o t i n A (D)

, then

D

has a directed

2

-factor with exactly

k

directed cycles of length at least

3

, where

n g e 12 k + 3

. This result is equivalent to the following result: If

G

is a balanced bipartite graph of order

2 n

with partite sets

X

and

Y

, and if

d_{G} (x) + d_{G} (y) g e n + 2

for every two vertices

x i n X

and

y i n Y

with

x y o t i n 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 g e 12 k + 3

. These results are generalizations of theorems concerning Hamilton cycles due to Woodall (1972) and Las Vergnas (1972), respectively.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs