ON DIRECTED 2-FACTORS IN DIGRAPHS AND 2-FACTORS CONTAINING PERFECT MATCHINGS IN BIPARTITE GRAPHS

摘要

In this paper, we give the following result: If D is a digraph of order n, and if d(D)(+)(u) + d(D)(-) (v) = n for every two distinct vertices u and v with (u, v) is not an element of A(D), then D has a directed 2-factor with exactly k directed cycles of length at least 3, where n = 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) = n + 2 for every two vertices x is an element of X and y is an element of Y with xy is not an element of 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 = 12k + 3. These results are generalizations of theorems concerning Hamilton cycles due to Woodall [Proc. Lond. Math. Soc., 24 (1972), pp. 739-755] and Las Vergnas [Problemes de couplages et problemes hamiltoniens en theorie des graphes, Ph.D. thesis, University of Paris, 1972], respectively.