Science in China Series A: Mathematics Sep., 2009, Vol. 52, No. 9, 1947–1954 www.scichina.com math.scichina.com www.springerlink.com

On Enomoto’s problems in a bipartite graph YAN Jin† & GAO YunShu School of Mathematics, Shandong University, Jinan 250100, China (email: [email protected])

Abstract 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. Keywords: MSC(2000):

1

bipartite graph, balanced bipartite graph, independent cycle 05C38, 05C70

Introduction

In this work, we only consider finite undirected simple graphs. Let G = (V, E) be a simple graph. A set of subgraphs of G is said to be vertex-disjoint or independent if no two of them have any common vertex in G. Let G1 and G2 be two vertex-disjoint subgraphs of G. We define E(G1 , G2 ) to be the set of edges of G between G1 and G2 , and let e(G1 , G2 ) = |E(G1 , G2 )|. For a subgraph H of G and a vertex x ∈ V (G), we denote by N (x, H) the set of neighbors of x contained in V (H), and let d(x, H) = |N (x, H)|. When H = G, d(x) is the degree of x in G. We use δ(G) to denote the minimum degree of G. Given a subset U ⊆ V (G), G[U ] is the subgraph of G induced by U . A graph is acyclic if it does not contain any cycle. For a bipartite graph G = (V1 , V2 ; E), two kinds of degree sum are defined as follows: δ1,1 (G) = min{d(x) + d(y)|x ∈ V1 , y ∈ V2 }, σ1,1 (G) = min{d(x) + d(y)|x ∈ V1 , y ∈ V2 , xy ∈ E(G)}. If |V1 | = |V2 |, then we call G a balanced bipartite graph. Unexplained terminologies and notations can be found in [1]. Corr´ adi and Hajnal[2] proved that if G is a graph of order n  3k with the minimum degree δ(G)  2k, then G contains k disjoint cycles. For bipartite graphs, Wang[3] proved the following result. Theorem 1.1[3] . If G = (V1 , V2 ; E) is a bipartite graph with |V1 | = |V2 | = n  2k + 1 and δ(G)  k + 1, then G contains k independent cycles. Enomoto[4] put forward the following problems about Theorem 1.1. Problem 1.2[4] .

Is it possible to replace the assumption on δ with δ1,1 or σ1,1 in Theorem 1.1?

Received June 17, 2008; accepted September 16, 2008 DOI: 10.1007/s11425-009-0012-z † Corresponding author This work was 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 and National Natural Science Foundation of China (Grant No. 60673047) Citation: Yan J, Gao Y S. On Enomoto’s problems in a bipartite graph. Sci China Ser A, 2009, 52(9): 1947–1954, DOI: 10.1007/s11425-009-0012-z

1948

Yan J & Gao Y S

Problem 1.3[4] . What happens if we do not assume |V1 | = |V2 | in Theorem 1.1? Motivated by the above problems, in this paper, we obtain the following result. Theorem 1.4. 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 and n2  2k + 1. If σ1,1 (G)  2k + 2 and |n1 − n2 |  1, then G contains k independent cycles. This paper also gives a message that it is possible that in [5, 6] the condition “balanced” is not necessary for a bipartite graph to contain specified cycles. Other results on independent cycles in a graph can be found in [9,10]. The following example shows that the degree condition σ1,1 (G)  2k + 2 in Theorem 1.4 is sharp. Let G1 = (X1 , Y1 ; E1 ) and G2 = (X2 , Y2 ; E2 ) be two independent complete bipartite graphs such that |X1 | = k, |Y1 | = |X2 | = m  k + 2 and |Y2 | = k − 1. The bipartite graph G = (X, Y ; E) = (X1 ∪X2 , Y1 ∪Y2 ; E) consists of G1 , G2 and a set of independent edges between Y1 and X2 . Then σ1,1 (G) = 2k + 1. It is easy to see that each cycle in G contains at least two vertices in X1 ∪ Y2 . Since |X1 ∪ Y2 | = 2k − 1, G does not contain k independent cycles. 2 Lemmas Throughout this section, G = (V1 , V2 ; E) is a given bipartite graph. We use l(C) and l(P ) to denote the length of a cycle C and a path P , respectively. That is, l(C) = |V (C)| and l(P ) = |V (P )| − 1. A cycle of length four is called a quadrilateral. We list several lemmas to prove Theorem 1.4. Lemma 2.1[7] . Let C be a cycle of G and x a vertex of G not on C. If d(x, C)  2, then either C is a quadrilateral or C + x contains a cycle C  such that l(C  ) < l(C). Lemma 2.2[3]. Let s and t be two integers such that t  s  2 and t  3. Let C1 and C2 be two independent cycles of G with lengths 2s and 2t, respectively. If e(C2 , C1 )  2t + 1, then G[V (C1 ∪ C2 )] contains two independent cycles C1∗ and C2∗ such that l(C1∗ ) + l(C2∗ ) < 2s + 2t. Lemma 2.3[7] . Suppose that C is a quadrilateral of G. Let x ∈ V1 and y ∈ V2 be two vertices not on C. If d(x, C) + d(y, C)  3, then there exists z ∈ V (C) such that either C − z + x is a quadrilateral and yz ∈ E, or C − z + y is a quadrilateral and xz ∈ E. Lemma 2.4[3]. Let T be a tree of order at least 2 with a bipartition (X, Y ) such that |Y |  |X|. Let p = |Y | − |X|. Then Y contains at least p + 1 endvertices of T . Lemma 2.5[8] . Let P = x1 x2 · · · xp be a path which is independent of edge e = y1 y2 , where p  3 is odd and {x1 , y1 } ⊆ Va for some a ∈ {1, 2}. Suppose that there exists a quadrilaterals C, which is independent of both P and e, such that e({x1 , x2 , xp , y1 }, C) + 2d(y2 , C)  7. Then G[V (P ∪ C) ∪ {y1 , y2 }] contains a quadrilateral C  and a path P  such that P  is independent of C  and l(P  ) > l(P ). Lemma 2.6[3] . Suppose that P = x1 x2 x3 and Q = y1 y2 y3 are two independent path of G with x1 ∈ V1 and y1 ∈ V2 . Let C be a quadrilateral of G such that C is independent of both P and Q. If e({x1 , x3 , y1 , y3 }, C)  5, then G[V (C ∪ P ∪ Q)] contains a quadrilateral C  and a path P ∗ of order 6 such that P ∗ is independent of C  . Lemma 2.7[3] . Let C be a quadrilateral of G. Let uv and xy be two independent edges of G such that they are independent of C. If e({u, v, x, y}, C)  5, then G[V (C) ∪ {u, v, x, y}] contains a quadrilateral C  and a path P ∗ of order 4 such that P ∗ is independent of C  .

On Enomoto’s problems in a bipartite graph

1949

Lemma 2.8[3]. Let C be a quadrilateral of G and P a path of order s  6 in G such that C is independent of P . If e(P, C)  s + 1, then G[V (C ∪ P )] contains two independent cycles. 3

Proof of Theorem 1.4

Let k, n1 , n2 be three positive integers and G = (V1 , V2 ; E) be a bipartite graph with |V1 | = n1 and |V2 | = n2 satisfying the condition of Theorem 1.4. Without loss of generality, we may assume n1  n2 . We claim that G contains at least one cycle. If δ(G)  2, then we are done. Hence, we may assume that δ(G)  1 and let v ∈ Va be the vertex with degree at most one. Since σ1,1 (G)  2k + 2, each vertex x ∈ Vb that is not adjacent to v has degree at least 2k + 1, where {a, b} = {1, 2}. So we have that e(G)  (2k + 1)(n − 1) > 2n − 1. It follows that G is not a forest and hence G contains at least one cycle. Let m be the greatest integer such that G contains m independent cycles. If m  k, then we have nothing to prove. So we assume m  k − 1. To prove the theorem, we choose m independent cycles C1 , . . . , Cm in G such that m  l(Ci ) is minimum. (1) i=1

Subject to (1), we choose C1 , . . . , Cm such that The length of the longest path in

G−V

 m

 Ci

is maximum.

(2)

i=1 (∪m i=1 Ci ).

Let P = x1 x2 · · · xp be one of the longest path of G − V Subject to (1) and (2), if p  2, we choose C1 , . . . , Cm in G such that    m is minimum. (3) d xp−1 , G − V Ci i=1

Subject to (1), (2) and (3), we choose C1 , . . . , Cm and P in G such that   m The length of the longest path in G − V (P ) ∪ V is maximum. Ci

(4)

i=1

Let Q = y1 y2 · · · yq be one of the longest path of G − V (P ) ∪ V (∪m i=1 Ci ). Finally, subject to (1)–(4), if q  2, we choose C1 , . . . , Cm , P and Q in G such that       m m d y2 , G − V (P ) ∪ V + d yq−1 , G − V (P ) ∪ V is minimum. (5) Ci Ci i=1

i=1

Let H = ∪m i=1 Ci , D = G − V (H), D0 = D − V (P ) and |V (D)| = d. Our aim is to show that D has a path of order at least d − 2 and further show that there exists Ci ∈ H such that G[V (D ∪ Ci )] contains induces two independent cycles which contradicts the maximality of m. To do this, we first give several claims and in the proofs we always use Va , Vb , where {a, b} = {1, 2}, to denote the two partitions of the bipartite graph G. Claim 1.

d  6.

Proof. On the contrary, suppose that d  5. We assume that l(C1 )  · · ·  l(Cm ) for convenience. Since n1  2k + 1, n2  2k + 1, we have l(Cm )  6. By Lemma 2.1 and (1), Cm has no any chord and d(y, Cm )  1 for each y ∈ V (D). By Lemma 2.2 and (1), we have that  x∈V (Cm ) d(x, Ci )  l(Cm ) for each i ∈ {1, . . . , m − 1}. It follows by σ1,1 (G)  2k + 2 that  (k + 1)l(Cm )  d(x)  (m + 1)l(Cm ) + d  (k + 1)l(Cm ) − 1. x∈V (Cm )

Yan J & Gao Y S

1950

This contradiction shows Claim 1. Claim 2.

d(y2 , D0 ) + d(yq−1 , D0 )  5.

Proof. Suppose d(y2 , D0 ) + d(yq−1 , D0 )  6. Then either d(yi , D0 )  3 for each i ∈ {2, q − 1} or d(yi , D0 )  4 for some i ∈ {2, q − 1}. In the latter case, without loss of generality, say d(y2 , D0 )  4. Let u1 and u2 be two endvertices of D0 such that ui y2 ∈ E(ui yq−1 ∈ E) and ui = y1 , yq . Clearly, d(u1 , P ) + d(y1 , P )  1 since D is acyclic. We may assume d(u1 , P ) = 0. The following two cases occur. Case 1.

q is even.

Since D is acyclic, d(yq , P )  1. Then we have d(u1 , H) + d(yq , H)  2(k + 1) − 3 = 2(k − 1) + 1. By pigeonhole principle, there exists Ci ∈ H such that d(u1 , Ci ) + d(yq , Ci )  3. By Lemma 2.1 and (1), l(Ci ) = 4. By Lemma 2.3, G[V (Ci ) ∪ {u1 , yq }] contains a quadrilateral Ci and an edge e independent of C  such that exactly one of u1 and yq is an endvertex of e . Replace Ci with Ci , then D0 contains a path of order q + 1, contradicting (4) while (1), (2) and (3) are maintained. Case 2.

q is odd.

Suppose y1 ∈ Va and let D1 = D0 −V (Q)∪{u1 , u2 } with the bipartition (A, B) such that A ⊆ Va and B ⊆ Vb , where {a, b} = {1, 2}. Then |(V (Q) ∪ {u1 , u2 }) ∩ Va | − |(V (Q) ∪ {u1 , u2 }) ∩ Vb | = 3. Since |V (P ) ∩ Va | − |V (P ) ∩ Vb |  −1 and n1 − n2  1, we obtain |B|  |A| + 1. Recalling that D is acyclic, we have d(v, P )  1 and d(v, Q ∪ {u1 , u2 })  1 for each v ∈ B. We are to show that we may choose a vertex in B such that d(v, D)  2. If there exists a vertex v ∈ B such that d(v, D1 ) = 0, then we are done. So D1 is a tree. By Lemma 2.4, B contains at least two endvertices v1 , v2 . Again since D is acyclic, e({v1 , v2 }, Q ∪ {u1 , u2 })  1, we can choose an endvertex v1 ∈ B such that d(v1 , Q ∪ {u1 , u2 }) = 0 and so d(v1 , D)  2. It follows by the hypothesis d(u1 , P ) = 0 that d(v, D) + d(u1 , D)  3. Therefore, d(u1 , H) + d(v, H)  2(k − 1) + 1. This implies that there exists Ci ∈ H such that d(u1 , Ci ) + d(v, Ci )  3. By Lemmas 2.1, 2.3, (1) and (4), G[V (Ci ) ∪ {u1 , v}] contains a quadrilateral Ci and an edge e independent of Ci such that exactly one of u1 and v is an endvertex of e , u1 ∈ V (Ci ) and v is an endvertex of e , say e = vz for z ∈ V (Ci ). Let H  = H − V (Ci ) ∪ V (Ci ) and D0 = D0 − u1 + z. If zy2 ∈ E, then D0 contains a path Q = vzy2 · · · yq of order q + 1, contradicting (4). Therefore, zy2 ∈ E. Similarly, zyq−1 ∈ E. We see that d(y2 , D0 ) = d(y2 , D0 ) − 1 and d(yq−1 , D0 )  d(yq−1 , D0 ), contradicting (5) while (1)–(4) are maintained. So Claim 2 holds. The following Claim 3 may be proved by the similar way as the proof of Case 2 in Claim 2. Claim 3.

If p is odd with 3  p  d − 2, then d(xp−1 , D) = 2.

Proof. Suppose that d(xp−1 , D)  3. Let u be an endvertex of D not on P such that uxp−1 ∈ E and (A, B) be the bipartition of D − V (P )∪{u} with A∪{xp } ⊆ Va and B ⊆ Vb . By the similar argument as done in the proof of Case 2 in Claim 2, we may show that |B|  |A| + 1 and there exists v ∈ B such that d(u, Ci ) + d(v, Ci )  3. Furthermore, G[V (Ci ) ∪ {u, v}] contains a quadrilateral Ci and an edge e independent of Ci satisfying u ∈ V (Ci ) and e = vz for z ∈ V (Ci ). Let H  = (H − V (Ci ) ∪ V (Ci ) and D = D − u + z. It also may be showed that d(xp−1 , D ) = d(xp−1 , D) − 1. This contradiction with (3) proves the claim. Claim 4.

If there exist two vertices v1 ∈ V1 ∩ D0 and v2 ∈ V2 ∩ D0 , then q  2.

On Enomoto’s problems in a bipartite graph

1951

Proof. Otherwise, q = 1. Since D is acyclic, d(v1 , P ) + d(v2 , P )  2. Subsequently, d(v1 , H) + d(v2 , H)  2(k − 1) + 2 and hence there exists Ci ∈ H such that d(v1 , Ci ) + d(v2 , Ci )  3. By Lemma 2.1 and (1), l(Ci ) = 4. By Lemma 2.3, G[V (Ci ) ∪ {v1 , v2 }] contains a quadrilateral Ci and an edge e such that they are independent. Replacing Ci with Ci in H yields an edge of D0 but P is still a longest path. This contradiction confirms Claim 4. Claim 5.

p  d − 2 and if the equality holds, then q = 1.

Proof. To the contrary, p  d − 2 and if the equality holds, then q = 2. The following two cases are considered. Case 1. p is even. Since p  d − 2 and p is even, there exist two vertices v1 ∈ V1 ∩ D0 and v2 ∈ V2 ∩ D0 .  By Claim 4, we have q  2. Let R = {x1 , xp , y1 , y2 }. Then z∈R d(z, D)  7. By Claim 2 and (2), we have d(y1 , D0 ) + d(y2 , D0 )  4 and d(x1 , D) + d(xp , D) = 2, and since D is  acyclic, we have e(P, Q)  1. It follows that z∈R d(z, H)  4(k − 1) + 1. This implies that  there exists Ci ∈ H such that z∈R d(z, Ci )  5. By Lemma 2.1 and (1), l(Ci ) = 4. Let Ci = u1 u2 u3 u4 u1 . Without loss of generality, we assume {u1 , x1 , y1 } ⊆ Va for some a ∈ {1, 2} and d(x1 , Ci ) + d(y2 , Ci )  3. By Lemma 2.3 and (2), d(x1 , Ci ) = 2 and d(y2 , Ci ) = 1, say e = y2 u1 and Ci = Ci − u1 + x1 . Therefore, d(xp , Ci ) + d(y1 , Ci )  2. We may assume that d(y1 , Ci )  1 for otherwise d(xp , Ci ) = 2 and so we have a path P  = x2 · · · xp u1 y2 y1 of order p + 2 such that P  is independent of Ci , contradicting (2). Assume that y1 u2 ∈ E. Then replacing Ci with Ci = u1 u2 y1 y2 u1 results in a path P  = u3 u4 x1 · · · xp of order p + 2, contradicting (2) once again. Case 2. p is odd. Case 2.1. q = 2. Let Q = y1 y2 with y1 ∈ Va . By the argument of Claim 3, we have d(xp−1 , D) = 2. As D is acyclic and q = 2, it is easy to check d(y1 , D) + 2d(y2 , D)  5. So we obtain e({x1 , xp , xp−1 , y1 }, H)+2d(y2 , H)  6(k+1)−9 = 6(k−1)+3. Thus there exists Ci ∈ H such that e({x1 , xp , xp−1 , y1 }, Ci ) + 2d(y2 , Ci )  7. By Lemma 2.1 and (1), l(Ci ) = 4. By Lemma 2.5, G[V (P ∪ Q ∪ Ci )] contains a quadrilateral Ci and a path P  such that P  is independent of Ci and l(P  ) > l(P ). Replacing Ci with Ci results in a contradiction with (2). Case 2.2. q  3. First we show that if q = 3, we may choose Q such that y1 and x1 are in different partitions of G. Suppose {x1 , y1 } ⊆ Va for some a ∈ {1, 2}. Let D1 = D0 − V (Q) with the bipartition (A, B) such that A ⊆ Va and B ⊆ Vb with {a, b} = {1, 2}. Then |B|  |A| + 1 since p and q are odd and n1 − n2  1. We claim that D0 contains two independent edges. To the contrary, let v ∈ B be the only vertex in D1 . Then d(v, D + d(y3 , D)  3 and so d(v, H) + d(y3 , H)  2(k − 1) + 1, which implies that there exists Ci ∈ H such that d(v, Ci ) + d(y3 , Ci )  3. By Lemmas 2.1, 2.3, (1) and (4), l(Ci ) = 4, d(v, Ci ) = 1 and d(y3 , Ci ) = 2. Let z ∈ V (C) be such that zv ∈ E. Replacing Ci with Ci = Ci − z + y3 results in two independent edges y1 y2 , vz in D0 . By the maximality of Q, e(y1 y2 , vz) = 0. So e({y1 y2 , zv}, H)  4(k − 1) + 2 and hence there exists Cj ∈ H such that e({y1 y2 , zv}, Cj )  5. By Lemmas 2.1 and 2.7, G[V (Cj ∪ D0 )] contains a quadrilateral Cj and a path of order four such that they are disjoint, contradicting (4). Hence if q = 3 we may choose Q such that {x1 , y1 } ⊆ Va for some a ∈ {1, 2}.

Yan J & Gao Y S

1952

For convenience, we suppose that x1 ∈ Va . Let T = {x1 , xp−1 , xp , z1 , z2 , z3 }, where z1 , z2 , z3 are to be chosen from D0 as follows: z1 ∈ Va and {z2 , z3 } ⊆ Vb such that {z1 , z2 } = {y1 , y2 }  and z3 ∈ {yq−1 , yq }. By Claim 2, Claim 3, (2) and (4), we have u∈T d(u, D)  11. Clearly, x1 z1 ∈ E, xp z3 ∈ E and xp−1 z2 ∈ E by Claim 3. Then by the assumption on the degrees of G,  we obtain u∈T d(u, H)  6(k + 1) − 11 = 6(k − 1) + 1 and hence d(u, Ci )  7 for some Ci ∈ H. (6) u∈T

By Lemma 2.1 and (1), l(Ci ) = 4. Let Ci = u1 u2 u3 u4 u1 with u1 ∈ Va . If d(z2 , Ci ) = 2 or d(z3 , Ci ) = 2, it is easy to see that either d(x1 , Ci ) + d(xp , Ci )  1 or d(x1 , Ci ) + d(xp , Ci ) = 0 (then d(xp−1 , Ci ) + d(z1 , Ci ) + d(z3 , Ci )  5), then G[V (Ci ∪ P ) ∪ {z1 , z2 , z3 }] contains a quadrilateral C  and a path P  independent of C  but longer than P , which contradicts (2). Thus d(z2 , Ci )  1 and d(z3 , Ci )  1. First consider the case d(z1 , Ci ) = 0. It follows by (6) that d(x1 , Ci )+d(xp , Ci )  3. So there exists a vertex in V (Ci )∩Vb , say u, such that {x1 u, xp u} ⊆ E. We obtain a cycle C  = uP u, and then G[V (Ci ∪ Q) − u] ia acyclic. Therefore, d(x1 , Ci ) = d(xp−1 , Ci ) = d(xp , Ci ) = 2, and there exists j ∈ {2, 3}, such that d(zj , Ci ) = 1, say zj u1 ∈ E. Then we obtain a quadrilateral C  = xp−1 xp u4 u3 xp−1 and a path P  = zj u1 u2 x1 · · · xp−2 of order p + 1 of G[V (Ci ∪ P ∪ Q)] such that P  and C  are independent, contradicting (1). Now consider d(z1 , Ci )  1. We may assume that d(z2 , Ci ) = 0. Otherwise, d(z2 , Ci ) = 1. Assume {u1 z2 , u2 z1 } ⊆ E. Then we have a quadrilateral C  = u1 u2 z1 z2 u1 . By the maximality of P , e({x1 , xp−1 , xp }, {u3 , u4 }) = 0. It follows by (6) that d(u, Ci ) = 1 for all u ∈ T − {z1 } and d(z1 , Ci ) = 2. Consequently, G[V (Ci ∪ P ∪ Q)] contains two disjoint cycles C  and u2 P u2 independent of C  , contradicting (1). Suppose d(z3 , Ci ) = 0. That is, there is only one vertex in {x1 , xp−1 , xp , z1 }, say u∗ , such that d(u∗ , Ci )  1 and d(u, Ci ) = 2 for all u ∈ {x1 , xp−1 , xp , z1 } − {u∗ }. This implies that {ui z1 , ui x1 , uj xp } ⊆ E for some {i, j} = {2, 4} and xp−1 uh ∈ E for some h ∈ {1, 3}. So G[V (Ci ∪ P ∪ Q)] contains a quadrilateral C  = xp−1 xp uj uh xp−1 and a path P  = z2 z1 ui x1 · · · xp−2 of order p + 1 such that P  is independent of C  , which contradicts (2). Thus d(z3 , Ci ) = 1. Without loss of generality, we assume that {u1 z3 , u2 z1 } ⊆ E. Therefore, G[V (Q ∪ {u1 , u2 }] contains a cycle and then G[V (P ) ∪ {u3 , u4 }] is acyclic. Hence e({x1 , xp−1 , xp }, {u3, u4 })  1. On the other hand, d(z1 , Ci ) + d(z3 , Ci )  3. We have d(x1 , Ci ) + d(xp−1 , Ci ) + d(xp , Ci ) = 4. Thus d(z1 , Ci ) = 2 and xp−1 u1 ∈ E. Then the quadrilateral z1 u2 u3 u4 z1 is independent of the path x1 · · · xp−1 u1 z3 of order p + 1, contradicting (2). The proof of Claim 5 is completed. In the following, we will use the above claims to finish the proof. First, the case p = d− 2 and q = 1 is considered. By the assumption, in this case, p = d − 2, n1 − n2 = 1 and by Claim 4, D0 has two isolated vertices {y1 , v} ⊆ Vb . Without lass of generality, assume x1 ∈ V1 . As y1 xp ∈ / E(G) and d(y1 , P )  1, then d(y1 , H) + d(xp , H)  2(k + 1) − 2 = 2(k − 1) + 2. This implies that there exists Ci ∈ H, say C1 , such that d(y1 , C1 ) + d(xp , C1 )  3. By Lemma 2.1 and (1), l(C1 ) = 4. By Lemma 2.3 and (2), d(y1 , C1 ) = 1 and d(xp , C1 ) = 2. Let y ∈ V (C1 ) be the vertex such that C1∗ = C1 − y + xp is a quadrilateral and y1 y ∈ E. Set H1 = H − V (C1 ), By the maximality of P , we see that d(v, C1 ∪ D) + d(x1 , C1 ∪ D)  5 and so d(v, H1 ) + d(x1 , H1 )  2(k − 2) + 1. Thus there exists Cj ∈ H1 , say C2 , such that d(v, C2 ) + d(x1 , C2 )  3. By Lemmas 2.1, 2.3, (1) and (2), l(C2 ) = 4, d(v, C2 ) = 1 and d(x1 , C2 ) = 2. Let v  ∈ V (C2 ) be the vertex such that C2∗ = C2 − v  + x1 is a quadrilateral and

On Enomoto’s problems in a bipartite graph

1953

vv  ∈ E(G). We discuss the following two cases d = 7 and d  9. If d = 7, then p = 5. Denote H  = (H −C1 ∪C2 )∪C1∗ ∪C2∗ , D = G−V (H  ), P  = P −x1 −xp and D0 = {v  v, yy1 }. We may assume that D0 induces a path of order 4. Otherwise, since D  is acyclic, z∈D d(z, , D )  6. Hence e(D0 , H  )  4(k − 1) + 2. This implies that there exists 0 Ct ∈ H  such that e(D0 , Ct )  5. By Lemmas 2.1 and 2.7 and (1), Ct is a quadrilateral and G[V (Ct ∪ D0 )] contains a quadrilateral Ct and a path of order 4 such that they are disjoint. Without lass of generality, say Q = yy1 v  v. Let S = {x2 , x4 , y, v  } and by the similar argument, we may show that e(S, Ct )  5 for some Ct ∈ H. By Lemmas 2.1, 2.6 and (1), G[V (Ct ∪P  ∪Q )] contains a quadrilateral C ∗ and a path P ∗ of order 6 such that P ∗ is independent of C ∗ . Replace Ct with C ∗ , this contradicts the maximality of P . Otherwise d  9 and p  7, since D is acyclic and p is odd, there are (p − 1)/2 pairs of  nonadjacent vertices in P − xp . We are to show z∈V (P −xp ) d(z, D) = 2p − 1. If there exists some Ci ∈ H such that e(P − xp , Ci )  p. As p − 1  6, by Lemma 2.1 and (1), l(Ci ) = 4 and so it follows from Lemma 2.8 that G[V (P − xp ) ∪ V (Ci )] contains two disjoint cycles, which contradicts the maximality of m. So e(P − xp , Ci )  p − 1 for each Ci ∈ H. Thus  (p − 1)(k + 1) − d(z, D)  e(P − xp , H)  (p − 1)(k − 1), 

z∈V (P −xp )

which implies that z∈V (P −xp ) d(z, D)  2p − 2 and if the equality holds, then e(P − xp , Ci ) = p − 1 for each Ci ∈ H. Recalling that d(xp , C1 ) = 2, we have e(P, Ci ) = p + 1. By the similar argument above, G[V (P ∪ Ci )] contains two disjoint cycles, again a contradiction. Therefore,  z∈V (P −xp ) d(z, D)  2p − 1. Since D is acyclic and p = d − 2, we have that  d(z, D) = 2p − 1. z∈V (P −xp )

In this case, there exist xs , xt ∈ V (P −xp )∩V1 (possibly xs = xt ) such that e({xs , xt }, {y1 , v}) = 2. Since D is acyclic, P + v has (p + 1)/2 pairs of nonadjacent vertices and so e(P + v, H)  (p + 1)(k + 1) − (2p + 1) = (p + 1)(k − 1) + 1. Hence there exists some Ci ∈ H such that e(P + v, Ci )  p + 2. By Lemma 2.8 and the maximality of P , we may assume that e(P, Ci ) = p, d(v, Ci ) = 2 and d(x1 , Ci ) = d(xp , Ci ) = 0. Let P1 = x1 · · · xs and P2 = xs · · · xp . By symmetry suppose s − 1  p − s, thus, P1 is no shorter than P2 . Keeping in mind that e(P, Ci ) = p and d(v, Ci ) = 2, by Lemma 2.8, we may assume that e(P1 , Ci )  |P1 | − 1, e(P2 , Ci )  |P2 | + 1 and |P2 |  4, xs = xt . For otherwise G[V (Pj + v) ∪ V (Ci )] contains two independent cycles, where j ∈ {1, 2}. Since xs ∈ V1 , we have |P2 | = 3, say P2 = xs xs+1 xp . It follows by d(xp , Ci ) = 0 that d(xs , Ci ) = d(xs+1 , Ci ) = 2 and e(P1 , Ci ) = |P1 | − 1. Since G[{xs , xs+1 , v, z}] contains a quadrilateral for each z ∈ V (Ci ), we may assume that d(z, P1 − xs )  1. Let Ci = a1 b1 a2 b2 a1 , then we see thate(Ci , P1 − xs )  2 since G[{xs , v, ai , bi }] contains a quadrilateral for each i = 1, 2. It follows by e(P1 , Ci ) = |P1 |− 1 and p  7 that |P1 | = 5. Let P  = x1 · · · x5 y1 . Then e(P  , H)  6(k + 1) − 12 = 6(k − 1). By Lemmas 2.1, 2,8 and (1), we may assume that e(P  , Ci ) = 6 for each Ci ∈ H. In particular, e(P  + v, C2 ) = 7 and d(x1 , C2 ) = 2. Let C2 = u1 u2 u3 u4 u1 and let vu3 ∈ E. Since C2 − ui + x1 contains a quadrilateral for each i = 1, 3, we assume that e({u1 , u3 }, P  )  1 and so e({u2 , u4 }, {x3 , x5 }) 

Yan J & Gao Y S

1954

3, say d(u4 , {x3 , x5 }) = 2. It follows that G[V (P  ∪ C2 ) ∪ {v}] contains two independent cycles u4 x3 x4 x5 u4 and x1 u2 u3 x2 x1 , contradicts the maximality of m. Now we consider the case p  d − 1. By Claims 1 and 5, we have p  5. First consider the case p  6. Define  p, if p is even, t= p − 1, otherwise. t Clearly, there are t pairs of non-adjacent vertices and i=1 d(xi , D)  2t. Therefore, t  d(xi , H)  t(k + 1) − 2t = t(k − 1). i=1 t By the similar argument as in the case p = d − 2, we may assume that i=1 d(xi , Cj ) = p t for each Cj ∈ H and i=1 d(xi , D) = 2t. In this case p = d − 1, p is odd and there exists exactly one vertex xs ∈ V (P ) ∩ V1 such that d(xs , D − P ) = 1. Let v ∈ D − P . Without lass of generality, assume that x1 · · · xs is a subpath of P that is not shorter than xs · · · xp . Then we see that P  = x1 · · · xs v is a path of order at least 6 and |P  | is even such that   z∈V (P  ) d(z, D)  2|V (P )| − 1. Then  d(z, H)  |V (P  )|(k − 1) + 1, z∈V (P  )

we can continue the process as above and complete the proof for the case p  6. So p  5 and by Claims 1 and 5, we see that p = 5 and d = 6. Let v ∈ V (D) − V (P ). As before, we may show that there exists a quadrilateral Ci ∈ H such that d(x1 , Ci ) = 2 and d(v, Ci ) = 1. Let u ∈ V (Ci ) be the vertex such that Ci = Ci − u + x1 is a quadrilateral and uv ∈ E. Set H1 = H − V (Ci ). We may also show that there exists anther quadrilateral Cj ∈ H1 with d(v, Cj ) = 1 and d(x5 , Cj ) = 2. Similarly, let w ∈ V (Cj ) be the vertex such that Cj = Cj − w + x5 is a quadrilateral and wv ∈ E. Set H  = H − V (Ci ∪ Cj ) ∪ V (Ci ∪ Cj ),  D = G − V (H  ) and T = {x2 , x4 , u, w}. Hence z∈T d(z, H  )  4(k − 1) + 4. By the similar argument as the proof of the case p = d − 2, we see that there exists a quadrilateral C ∗ ∈ H  such that G[V (C ∗ ∪ D )] contains a quadrilateral C ∗∗ and a path P ∗ of order 6 such that they are independent. This contradicts the maximality of P and so the proof of the theorem is complete. Acknowledgements ments.

The authors are indebted to anonymous referees for their valuable com-

References 1 Bondy J A, Murty U S R. Graph Theory with Applications. The second edition. New York: Springer, 2008 2 Corr´ adi K, Hajnal A. On the maximal number of independent circuits in a graph. Acta Math Acad Sci Hungar, 14: 423–439 (1963) 3 Wang H. On the maximum number of independent cycles in a bipartite graph. J Combin Theory Ser B, 67: 152–164 (1996) 4 Enomoto H. Graph partition problems into cycles and paths. Discrete Math, 233: 93–101 (2001) 5 Wang H. Large vertex-disjoint cycles in a bipartite graph. Graph Combin, 16: 359–366 (2000) 6 Wang H. Proof of a conjecture on cycles in a bipartite graph. J Graph Theory, 31: 333–343 (1999) 7 Wang H. On 2-factors of a bipartite graph. J Graph Theory, 31: 101–106 (1999) 8 Li X, Wei B, Yang F. Independent cycles in a bipartite graph. Ars Combin, 73: 173–186 (2004) 9 Yan J. Disjoint triangles and quadrilaterals in a graph. Discrete Math, 308: 3930–3937 (2008) 10 Yan J, Liu G. On 2-factors with prescribed properties in a bipartite graph. Acta Math Sinica, English Ser, 15: 1–11 (2006)