On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs
On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs
复制标题
关于有向图中的有向 2-因子和二分图中包含完美匹配的 2-因子
DOI：
10.1137/16m1108959
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yamashita Tomoki
中科院分区：
文献类型：
--
作者：
Chiba Shuya;Yamashita Tomoki
本文给出了以下结果：如果是一个有序的有向图，并且对于每两个不同的顶点和，则存在一个长度至少为3的有向环的有向因子，其中。这个结果等价于下面的结果：如果是一个2n阶的平衡二部图，有部分集和，并且对于每两个顶点和，那么对于每一个完美匹配，都有一个精确循环长度至少为6的2因子，包含的每条边，其中。这些结果是对Woodall过程中有关Hamilton环的定理的推广。数学。Soc。和Las Vergnas [problems of couges和problems hamiltoniens en the samorie des graphes，博士论文，巴黎大学，1972]。
In this paper, we give the following result: Ifis a digraph of order, and iffor every two distinct verticesandwith, thenhas a directed 2-factor with exactlydirected cycles of length at least 3, where. This result is equivalent to the following result: Ifis a balanced bipartite graph of order 2n with partite setsand, and iffor every two verticesandwith, then for every perfect matching,has a 2-factor with exactlycycles of length at least 6 containing every edge of, where. These results are generalizations of theorems concerning Hamilton cycles due to Woodall [Proc. Lond. Math. Soc., 24 (1972), pp. 739--755] and Las Vergnas [Problémes de couplages et problémes hamiltoniens en théorie des graphes, Ph.D. thesis, University of Paris, 1972], respectively.