Opuscula Mathematica • Vol. 29 • No. 4 • 2009 http://dx.doi.org/10.7494/OpMath.2009.29.4.345 Denise Amar, Evelyne Flandrin, Grzegorz Gancarzewicz CYCLABILITY IN BIPARTITE GRAPHS Abstract. Let G = (X,Y;E) be a balanced 2-connected bipartite graph and S ⊂ V(G). We will say that S is cyclable in G if all vertices of S belong to a common cycle in G. We givesufficient degree conditions in a balanced bipartite graph Gand a subset S ⊂V(G) for thecyclability of theset S. Keywords: graphs, cycles, bipartite graphs. Mathematics Subject Classification: 05C20, 05C35, 05C38, 05C45. 1. INTRODUCTION We shall consider only finite graphs without loops and multiple edges. Several authors have given results about cycles containing specific subsets of ver- tices, see for example [7] or [9]. The setS ofverticesiscalledcyclable inGifallverticesofS belongtoacommon cycle in G. We also speak about cyclability or noncyclability of the vertex set S. In a bipartite graphG=(X,Y;E) we will call the independent sets of vertices X and Y the partite sets. Let G=(X,Y;E) be a bipartite graph and let S ⊂V(G), then S =S∩X and X S =S∩Y. We will say that S is balanced iff |S |=|S |. Y X Y In 1992 Shi Ronghua [8] obtained the following result: Theorem 1.1. Let G be a 2-connected graph of order n and S a subset of V(G) with |S|≥3. If for every pair of nonadjacent vertices x and y in S we have d(x)+d(y)≥n, then S is cyclable in G. Note that the assumption of 2-connectivity may be omitted in Theorem 1.1. It is an easy corollary of a result of K. Ota [7]. Recently R. Čada, E. Flandrin and Z. Ryjáček [3] proved the following generali- zation of Theorem 1.1: 345 346 Denise Amar,EvelyneFlandrin, Grzegorz Gancarzewicz Theorem 1.2. Let G be a 2-connected graph of order n and S a subset of V(G). If for every pair of nonadjacent vertices x and y in S we have d(x)+d(y)≥n−1, then either S is cyclable in G, or n is odd and G contains an independent set S ⊆S 1 such that |S |= n and every vertex of S is adjacent to all vertices in G\S . 1 2 1 1 In2002E.Flandrin,H.Li,A.MarczykandM.Woźniak[4]obtainedthefollowing generalizationof Theorem 1.1: Theorem 1.3. Let G be a k-connected graph, k ≥ 2 of order n. Denote S ,...S 1 k subsets of the vertex set V(G) and let S = S ∪S ∪···∪S . If for any x, y ∈ S , 1 2 k i xy 6∈E we have d(x)+d(y)≥n, then S is cyclable in G. The notion of cyclability is a generalization of the term of hamiltonicity. If we consider S = V(G) then S is cyclable iff G is hamiltonian. In fact Theorem 1.1 is a generalizationof the following result of O. Ore [6]: Theorem 1.4. Let G be a graph on n ≥ 3 vertices. If for all nonadjacent vertices x,y ∈V(G) we have d(x)+d(y)≥n, then G is hamiltonian. A similar result for bipartite graphs was proved by J. Moon and M. Moser [5] in 1963: Theorem 1.5. Let G=(X,Y;E) be a balanced bipartite graph of order 2n. If for all nonadjacent vertices x∈X and y ∈Y we have d(x)+d(y)≥n+1, then G is hamiltonian. Givenabalancedbipartitegraphandaselectedsubsetofvertices,weareinterested in properties that imply cyclability. In 2000 D. Amar, M. El Kadi Abderrezzak, E. Flandrin [2] proved the following generalizationof Theorem 1.1 for bipartite graphs: Theorem 1.6. Let G=(X,Y;E) be a balanced 2-connected bipartite graph of order 2n, S ⊂X. If for every x∈S, y ∈Y, xy 6∈E we have d(x)+d(y)≥n+1, then S is cyclable in G. Note that in this case S = S and Theorem 1.6 is also a generalization of X Theorem 1.5. The main result of the present paper, given in Section 3, is Theorem 3.1, which improves upon Theorem 1.6. Cyclability in bipartite graphs 347 2. DEFINITIONS Let G be a graph and H a subgraph of G. Definition 2.1. NG(H) denotes the set of all vertices of the graph G which are adjacent to a vertex of the subgraph H, i.e. NG(H)={u∈V(G) : ∃v ∈V(H) such that uv ∈E(G)}. Consider an arbitrary vertex x ∈ V(G). N(x) denotes the set of all neighbors of the vertexxinG, i.e. N(x)={u∈V(G): xu∈E(G)}.NH(x) denotesthe setofall neighborsofthevertexxinthesubgraphH,i.e. NH(x)={u∈V(H): xu∈E(G)}. d (x) denotes the number of neighbors of x in the subgraph H i.e. H d (x)=|N (x)|, and d (x) denotes the degree of the vertex x in the subgraph H. H H H Intheproofwewillonlyusecyclesandpathswithagivenorientation. Foracycle C :c ...c or a path P :p ...p we will use implicit orientation. 1 k 1 l Thus it makes sense to speak of a successor ci+1 and a predecessor ci−1 of a vertex c (addition modulo l+1). Denote the successor of a vertex x by x+ and its i predecessor by x−. This notation can be extended to A+ = {x+ : x ∈ A}, and similarly, to A− when A⊆V(G). Let P be a path p ...p and u, v ∈V(G) such that up , vp ∈E(G), then: uPv 1 k 1 k is the path up ...p v and vPu is the path vp ...p u. 1 k k 1 Definition 2.2. We shall call a path P :p ...p a C-path of the cycle C iff V(P)∩ 1 l V(C)={p ,p }. Note that a C-path is a generalized chord of the cycle. 1 l Definition 2.3. Let C : c ...c be a cycle in G with the orientation, the indices 1 l 1,...,l are considered modulo l. For any pair of vertices c , c ∈ V(C) (i 6= j) we i j define four intervals: – ]ci,cj[ is the path ci+1...cj−1. – [ci,cj[ is the path ci...cj−1. – ]c ,c ] is the path c ...c . i j i+1 j – [c ,c ] is the path c ...c . i j i j Note that these four intervals are subsets of the cycle C. For notation and terminology not defined above a good reference is [1]. 3. THEOREM Theorem 3.1. If G = (X,Y;E) is a balanced 2-connected bipartite graph of order 2n and S ⊂V(G) satisfying conditions: For every x∈S , y ∈Y, xy 6∈E we have d(x)+d(y)≥n+1 (3.1) X For every x∈X, y ∈S , xy 6∈E we have d(x)+d(y)≥n+1 (3.2) Y then S is cyclable in G. 348 Denise Amar,EvelyneFlandrin, Grzegorz Gancarzewicz K 2,p K 2,2 K 2,p K 3p,6 K 2,p S vertices from X vertices from Y Fig. 1. Gp,3 Theorem 3.1 is obviously a generalizationof Theorem 1.6. We first tried to find a generalizationsatisfying two conditions: – The vertices of S are in both partite sets X and Y. – The degree sum condition holds only for vertices from S. However, even if we assume that S is balanced (i.e. |S |=|S |), such a result is X Y not true. Foreveryk ≥1wewillgiveanexampleofa2-connected,balancedbipartitegraph G=(X,Y;E) and a balanced set S ⊂V(G), satisfying the following condition: For every x∈S , y ∈S if xy 6∈E then d(x)+d(y)≥n+k, (3.3) X Y such that S is not cyclable in G. p−k Let k ≥1, p≥k+2 and 2≤r ≤1+ . 2 Cyclability in bipartite graphs 349 First consider bipartite graphs K , K and r copies of K . In K we have pr,2r 2,2 2,p 2,2 two partite sets say X and Y . The graph G = (X,Y;E) is obtained out of K , 2 2 pr,2r K and the r copies of K by joining every vertex of degree pr from K with 2,2 2,p pr,2r all vertices from X and every vertex of degree p from the r copies of K with all 2 2,p vertices from Y . 2 Let S be the set of all vertices from K of degree pr in K . 1 pr,2r pr,2r In each copy of K we take the two vertices of degree p in K . In this way we 2,p 2,p will get 2r vertices and we define the set S as the set containing these 2r vertices. 2 We can define now the set S. Let S =S ∪S ∪V(K ). 1 2 2,2 p−k For k ≥ 1, p ≥ k + 2 and 2 ≤ r ≤ 1+ we have obtained a balanced, 2 2-connected bipartite graph G =(X,Y;E) of order 2n with n=pr+2r+2 and a p,r balanced set S which is not cyclable, but satisfies (3.3). We can find an example of the graph G on the Figure 1. p,3 This example shows that it is not enough to assume that the degree sum con- dition holds only for the vertices from S in a bipartite graph. Even increasing the connectivity will not be sufficient, as we can see in the following example. For every k ≥ 1 and l ≥ 2 we will give an example of an l-connected, balanced bipartite graph G′ = (X,Y;E) and a balanced set S′ ⊂V(G′), satisfying (3.3), such that S′ is not cyclable in G′. p−k Let k ≥1, l≥2, p≥l2−l+k and l≤r <1+ . l First consider bipartite graphs K , K and r copies of K . In K we have pr,lr l,l l,p l,l two partite sets say X and Y . The graph G′ = (X,Y;E) is obtained out of K , l l pr,lr K and the r copies of K by joining every vertex of degree pr from K with l,l l,p pr,lr all vertices from X and every vertex of degree p from the r copies of K with all l l,p vertices from Y. l Let S′ be the set of all vertices from K of degree pr in K . 1 pr,lr pr,lr In eachcopy of K we take the l vertices of degree p in K . In this way we will l,p l,p get lr vertices and we define the set S′ as the set containing these lr vertices. 2 We can define now the set S′. Let S′ =S′ ∪S′ ∪V(K ). 1 2 l,l p−k Fork ≥1,l≥2,p≥l2−l+kandl≤r <1+ wehaveobtainedabalanced, l l-connected bipartite graph G′ =(X,Y;E) of order 2n with n=pr+lr+l and a p,r,l balanced set S′ which is not cyclable in G′, but satisfies (3.3). 4. PROOF OF THEOREM 3.1 4.1. PRELIMINARY NOTATIONS Let G=(X,Y;E) be a bipartite graph and let C be a cycle in G. InthischapterforagivencycleC andavertexx∈V(G\C),aC-pathQthrough xwillbedenotedQ:uQ xQ u′,whereQ andQ aretwovertexdisjointpaths. The 1 2 1 2 endverticesofthe C-pathQ:u andu′ andthe vertexx donotbelong to Q norQ . 1 2 350 Denise Amar,EvelyneFlandrin, Grzegorz Gancarzewicz Note that the path Q may be empty or in other words V(Q ) = ∅ and in this 1 1 case xu∈E. Similarly for Q . 2 AnexampleofaC-pathP :uP xP u′throughavertexxcanbefoundonFigure2. 1 2 x P P 1 2 u u 1 u′ u 2 C Fig. 2. An example of a cycle C and a C-path P with x,u′, u1 ∈X and u, u2 ∈Y Remark 4.1. Given a 2-connectedgraph G, a nonhamiltoniancycle C and a vertex x∈V(G\C), G contains necessarily a C-path through x. In the remainingpartofSection4 we willalwaysconsidera 2-connectedbipartite graph G and a subset S ⊂ V(G) not cyclable in G. Given a cycle C, a vertex x∈V(G\C)∩S suchthatC containsS\{x}butdoesnotcontainS,wewilldenote by P a C-paththroughx. We willalwaysassumethat the cycleC andthe C-pathP arechosensuchthatP isshortestpossibleamongallC-paths throughxforallcycles C containing S \{x}, i.e. for any cycle C′ containing S \{x}, and for any C′-path P′ containing the vertex x we have |V(P)| ≤ |V(P′)|. We will denote this C-path P :uP xP u′ (note that P and/or P may be empty). 1 2 1 2 Wewilldenotebyu thefirstvertexonthecycleC fromS afteru(u existssince 1 1 S is not cyclable). Similarly u is the first vertex on the cycle C from S after u′. 2 R is the subgraph induced in G by V(G)\V(C). Alltheintervalsoftype[a,b],[a,b[,]a,b]and]a,b[areintervalsonthecycleC and we sometimes identify the vertex set of an interval with the corresponding interval. Remark 4.2. The C-path P :uP xP u′ has the following properties: 1 2 – If V(P )6=∅ or V(P )6=∅ then d (x)≤1. (4.1) 1 2 C – If V(P )6=∅ and V(P )6=∅ then d (x)=0. (4.2) 1 2 C Remark 4.2 is an immediate consequence of the choice of the cycle C and the C-path P. Cyclability in bipartite graphs 351 4.2. FORMULATION AND PROOF OF LEMMA 4.3 In the proofof Theorem3.1 we shalluse the following lemma. Notations G, S, C, R, x and C-path P :uP xP u′, u and u are defined in Section 4.1 but we recall them 1 2 1 2 for completeness. We denote by C a cycle containing S \{x}. Let P be a C-path throughx. ThecycleC andthe C-pathP arechosensuchthatP is shortestpossible among all C-paths through x for all cycles C containing S\{x}. Let u be the first 1 vertexfromS after u onthe cycleC, andletu be the firstvertexfromS after u′ on 2 the cycle C. The subgraph of G induced by V(G)\V(C), will be denoted R. Lemma 4.3. Let G=(X,Y;E)be a 2-connectedbipartite graph and let C, P, R and S be as above. Then we have: ′ – For every C−path Q:aQ xQ a through x we have: 1 2 ′ ′ V(]a,a[)∩S 6=∅ and V(]a,a[)∩S 6=∅. (4.3) ′ – For any b∈V(]u,u ]) and c∈V(]u,u ]) we have: 1 2 NP xP (b)=NP xP (c)=∅. (4.4) 1 2 1 2 ′ – If z ∈V(P)\{u,u}, then NR(z)∩(N(]u,u1])∪N(]u,u2]))=∅. (4.5) ′ – NR(]u,u1])∩NR(]u,u2])=∅. (4.6) – For any y ∈NR(x) we have N]u,u ](y)=N]u′,u ](y)=∅. (4.7) 1 2 Proof of Lemma 4.3. Suppose that V(]a,a′[)∩S =∅, then the cycle: C′ : aQ xQ a′a′+... a, (4.8) 1 2 is a cycle containing S, a contradiction. If V(]a′,a[) ∩ S = ∅, then using similar arguments we get a contradiction and hence (4.3) is proved. In order to prove (4.4) suppose that there is a vertex b ∈ V(]u,u ]) such that 1 NP xP (b) 6= ∅. We have a vertex z ∈ NP xP (b) and we assume that the vertices 1 2 1 2 on the path P xP are labeled as follows: P xP : p1...plxpk...p1. 1 2 1 2 1 1 2 2 We shall consider three cases. 1. When z =x, then the following cycle: C′ : uP xbb+...u′...u ...u, (4.9) 1 2 contains S, a contradiction. 2. If z ∈V(P ), then the following cycle: 1 C′ : up1...pizbb+...u ...u′...u ...u, (4.10) 1 1 1 2 contains S\{x} and has a C′-path P′ : zpi+2...xP u′, (4.11) 1 2 shorter then P, a contradiction with the choice of C and P. 352 Denise Amar,EvelyneFlandrin, Grzegorz Gancarzewicz 3. If z ∈V(P ), then the following cycle: 2 C′ : uP xpk...pjzbb+...u′...u ...u, (4.12) 1 2 2 2 contains S, a contradiction. So we have NP xP (b) = ∅. Using similar arguments we can prove that for any 1 2 c∈V(]u′,u2]) NP xP (c)=∅, and hence (4.4) is true. 1 2 We will prove now (4.5). Suppose that NR(z)∩(N(]u,u1])∪N(]u′,u2]))6=∅. So we have a vertex w ∈ NR(z) ∩ (N(]u,u1]) ∪ N(]u′,u2])). Without loss of generality we can assume that w ∈NR(z)∩N(]u,u1]). Let a ∈V(]u,u1]), such that aw∈E. From (4.4) we know that w6∈V(P xP ). 1 2 x P P 1 z 2 w u u 1 u′ u 2 C Fig. 3. u2, w, x∈X and u, u1, u′, z∈Y As in the proof of (4.4), we shall consider three cases: 1. z ∈V(P ). 1 2. z ∈V(P ). 2 3. z =x. Using similar arguments we get contradiction. In any case we obtain a contradictionby replacing in (4.10), (4.12)and (4.9), the edge za by the path zwua. Hence (4.5) is true. For a = u , you can find the illustrations of Cases 1 and 2 on Figures 3 and 4 1 respectively. In order to prove (4.6), suppose that b ∈ V(]u,u ]), c ∈ V(]u′,u ]) and z ∈ 1 2 NR({b,c}). From (4.4) we know that N (b)=N (P xP )=∅, and so z 6∈V(P). In this P xP c 1 2 1 2 case the cycle: C′ : uP xP u′u′−...u ...bzc...u u+...u 1 2 1 2 2 contains S, a contradiction. Cyclability in bipartite graphs 353 x z P P 1 2 w u u 1 u′ u 2 C Fig. 4. u2, w, x∈X and u, u1, u′, z∈Y Hence (4.6) is true. In order to prove (4.7), suppose that there is a vertex y ∈ NR(x) such that N (y) 6= ∅. From (4.4) we know that y 6∈ V(P xP ). We have a vertex b ∈ ]u,u ] 1 2 1 V(]u,u ]) such that yb∈E and the following cycle: 1 C′ : uP xybb+...u ...u′...u ...u 1 1 2 contains S, a contradiction and so N (y)=∅. ]u,u ] 1 Using the same arguments we can prove N (y)= ∅. Hence (4.7) is true and ]u,u ] 2 the proof of Lemma 4.3 is finished. (cid:3) 4.3. PROOF OF THEOREM 3.1 We mayassumethatS 6=∅and|S |≥|S |. We willproceedbyinductionoverthe Y Y X number of vertices in S . X If |S |=0, then S =S and from Theorem1.6 we know that S is cyclable in G. X Y So the first step of the induction is finished. Suppose now that S satisfies the assumptions of Theorem 3.1 and |S |≥1. X From the induction hypothesis, we assume that for any x∈S the set S\{x} is X cyclable in G, while S itself is not cyclable. Let us choose a vertex x∈S . X WehaveacycleC containingS\{x}suchthatx6∈V(C). Werecallthatthecycle C and the C-path P are chosen such that P is shortest possible among all C-paths containing x for all cycles C containing S \{x}. As in Section 4.1, u is the first 1 vertex from S on the cycle C after u and u is the first vertex from S on the cycle C 2 after u′, R is the subgraph induced in G by V(G)\V(C). It is clear that in this case R is a balanced bipartite graph. c+r Note that if c=|V(C)|, r=|V(R)|, then c and r are even and n= . 2 From Remark 4.2 and Lemma 4.3 C and P satisfy (4.3) — (4.7). 354 Denise Amar,EvelyneFlandrin, Grzegorz Gancarzewicz We shall consider four cases: 1. NR(x)=∅. 2. NR(x)6=∅ and u1,u2 ∈SY. 3. NR(x)6=∅ and u1, u2 ∈SX. 4. NR(x)6=∅ and u1 and u2 are in different partite sets. Case 1. NR(x)=∅ In this case P and P are empty and xu, xu′ ∈E. 1 2 Since R is balanced there is an y ∈ Y ∩V(R). Since xy 6∈ E then from (3.1) we have: d(x)+d(y)≥n+1. (4.13) Since NR(x)=∅ we have: r d (x)=0 and d (y)≤ −1. (4.14) R R 2 x y a a+ b b+ C Fig. 5. a+,b+, x∈X and a,b, y∈Y Suppose that y has two neighbors a+, b+ in NC(x)+, then xa, xb ∈ E and the cycle C′ (see Fig. 5): C′ : xbb−...a+yb+b++...ax contains S, a contradiction with noncyclability of S. So y has at most one neighbor in N (x)+ and thus: C c d (x)+d (y)≤ +1. (4.15) C C 2 From (4.14) and (4.15) we have: r c d(x)+d(y)≤ −1+ +1≤n, 2 2 a contradiction with (3.1).