关键词: 均衡二分图, 完美对集, 2因子, M2因子

Abstract:

A bipartite graph G=(X,Y; E) is called  balanced if |X|=|Y|. Let  G=(X,Y; E) be a balanced bipartite  graph of order 2n, suppose  that the minimum degree of G is at least   (2n-1)/3, the author shows that if n≥4k, then for each perfect  matching M, G contains a 2factor with exactly k components  (vertex disjoint cycles) including every edge of M (with one  exception that k=1, n=5 and δ(G)=3). When k=2,  n≥5,  the author has  the same conclusionunder  the condition  4δ≥(n+1)/2,  and  this bound about minimum degree  is the best possible.

Key words: Balanced bipartite graph, Perfect matching, 2 factor, M 2 factor.