二分图中含有大圈的2-因子  

On 2-factors with large cycles in a biparitite graph

作　　者：高云澍[1] 李国君[1] 

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

出　　处：《山东大学学报（理学版）》2007年第4期28-31,38,共5页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(60373025)

摘　　要：设G=(V1,V2;E)是一个二分图,其顶点数目满足|V1|=|V2|=n(k+1)s+1,s和k是满足s 3并且k 1的两个正整数.定义σ1,1为图G的属于不同分划中的不相邻顶点的最小度和,证明了如果σ1,1(G)2「(1-1s)n﹁+2,则G有一个2-因子包含至少k个圈,使得每个圈的长至少为2s.Let G = （ V1, V2 ; E） be a bipartite graph with ｜V1 ｜ = ｜ V2 ｜ = n 〉 （ k ＋ 1 ） s ＋ 1, s and k are two integers with s ≥ 3 and k≥ 1. Define σ1,1 , as the minimum degree of nonadjacent vertices of G. It is proved that if σ1,1 （G） ≥2[（1 - 1/s） n ] ＋ 2, then G contains a 2, factor with at least k cycles, such that the length of every cycle is at least 2s.

关 键 词：均衡二分图 圈 2-因子 

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