On Enomoto's problems in a bipartite graph  

作　　者：YAN Jin GAO YunShu 

机构地区：[1]School of Mathematics,Shandong University,Jinan 250100,China

出　　处：《Science China Mathematics》2009年第9期1947-1954,共8页中国科学：数学（英文版）

基　　金：supported by the Foundation for the Distinguished Young Scholars of Shandong Province (Grant No.2007BS01021);the Taishan Scholar Fund from Shandong Province,SRF for ROCS,SEM;National Natural Science Foundation of China (Grant No.60673047)

摘　　要：In this paper, we obtain the following result: Let k, n 1 and n 2 be three positive integers, and let G = (V 1,V 2;E) be a bipartite graph with |V1| = n 1 and |V 2| = n 2 such that n 1 ? 2k + 1, n 2 ? 2k + 1 and |n 1 ? n 2| ? 1. If d(x) + d(y) ? 2k + 2 for every x ∈ V 1 and y ∈ V 2 with xy $ \notin $ E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph.In this paper, we obtain the following result: Let k, n1 and n2 be three positive integers, and let G=(V1, V2; E) be a bipartite graph with |V1|=n1 and |V2|=n2 such that n1 2k + 1, n2 2k + 1 and |n1-n2| 1. If d(x) + d(y) 2k + 2 for every x∈V1 and y∈V2 with xy( ∈/)E(G), then G contains k independent cycles. This result is a response to Enomoto's problems on independent cycles in a bipartite graph.

关 键 词：bipartite graph balanced bipartite graph independent cycle 05C38 05C70 

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