有圈二部图覆盖的一个结果

H.Wang猜想,对于任意整数k≥2,存在N(k)使得二部图G=(V1,V2,E)中,V1=V2=n≥N(k),且对于G中任意一对不相邻的顶点x∈V1,y∈V2,有d(x)+d(y)≥n+k,那么,对于G中任意k个独立边e1,e2,e3,…,ek,存在顶点不重的k个圈C1,C2,…,Ck,使得ei∈E(Ci),i∈{1,2,…,k}和V(C1∪C2∪…∪Ck)=V(G).H.Wang及J.A.Bondy对k=2,3时证明了猜想成立,本文对k=4证明了猜想的正确性.

A Result of Covering a Bipartite Graph with Cycles

H. Wang conjectured that for each integer k &le 2 there exists N(k) such that if G = (V1, V21, E) is a bipartite graph in which |V1| = |V2| = n &le N(k) and d(x) + d(y) &le n + k for any pair of nonadjacentvertices x∈V1 and y∈V2, then for any k independent edges e1, e2, e3, &mellip;ek in G there exist k vertex-disjoint cycles C1, C2, &mellip;, Ck such that ei∈E(Ci), i∈{l, 2, &mellip;, k} and V(C1UC2U&mellip;UCk) = V(G). This conjecture has been verified if k = 2, 3 by H. Wang and J.A.Bondy, but we prove it if k = 4.