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

设G=(V₁,V₂;E)是一个二分图,其顶点数目满足|V₁|=|V₂|=n≥(k+1)s+1，s和k是满足s≥3并且k≥1的两个正整数. 定义σ_1,1为图G的属于不同分划中的不相邻顶点的最小度和，证明了如果σ_1,1(G)≥2(1-1/s)n]+2, 则G有一个2-因子包含至少k个圈,使得每个圈的长至少为2s.

On 2-factors with large cycles in biparitite graph

Let G=(V₁,V₂;E) be a bipartite graph with |V₁|=|V₂|=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 prove that if σ_1,1(G)≥2(1-1s)n]+2, then G contains a 2-factor with at least k cycles, such that the length of every cycle is at least 2s.