2016/12/28 by Shuya Chiba, Tomoki Yamashita, Chiba, Shuya +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1612.08904
openalex publication_date 2016/12/28 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
In this paper, we give the following result: If D is a digraph of order n, and if dD+(u) + dD-(v) ≥ n for every two distinct vertices u and v with (u, v) ∉ 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 dG(x)+dG(y) ≥ n + 2 for every two vertices x ∈ X and y ∈ Y with xy ∉ 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 (1972) and Las Vergnas (1972), respectively.