二分图中含有完美对集的2-因子  

On 2-factors Containing Perfect Matching in Bipartite Graphs

作　　者：王骁力[1] 

机构地区：[1]山东大学数学与系统科学学院

出　　处：《数学物理学报（A辑）》2004年第4期475-479,共5页Acta Mathematica Scientia

基　　金：国家自然科学基金(60172003)资助

摘　　要：该文证明若G是2n阶均衡二分图,δ(G)≥(2n-1)／3,则对任何正整数k,n≥4k时,任给G的一个完美对集M,G中存在一个包含M的所有边的恰含k个分支的2-因子(k=1,n=5且δ(G)=3除外).特别k=2时,在条件n≥5且δ(G)≥(n+2)／2下,结论也成立.这里所给的δ(G)的下界是最好的可能.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 conclusion under the condition 4δ≥(n+1)/2 , and this bound about minimum degree is the best possible.

关 键 词：均衡二分图 完美对集 2-因子 M-2-因子 

分 类 号：O157.5[理学—数学]