5-Cycle Systems with Holes

Designs, Codes and Cryptography, 8, 103–108 (1996)

c 1996 Kluwer Academic Publishers, Boston. Manufactured in The Netherlands. °

5-Cycle Systems with Holes DARRYN E. BRYANT Centre for Combinatorics, Department of Mathematics, The University of Queensland, Qld 4072, Australia D. G. HOFFMAN Auburn University, Department of Discrete and Statistical Sciences, 120 Math Annex, Auburn, Alabama 368495307 C. A. RODGER* Auburn University, Department of Discrete and Statistical Sciences, 120 Math Annex, Auburn, Alabama 368495307 Communicated by: D. Jungnickel Received October 5, 1994; Accepted January 1, 1995

Dedicated to Hanfried Lenz on the occasion of his 80th birthday Abstract. Recently the generalized Doyen-Wilson problem of embedding a 5-cycle system of order u in one of order v was completely solved. However it is often useful to solve the more general problem of the existence of a 5-cycle system of order v with a hole of size u. In this paper we completely solve this problem.

1.

Introduction

Let Zm = {0, 1, . . . , m − 1}. An m-cycle is a graph (v 0 , v1 , . . . , vm −1 ) with vertex set {vi | i ∈ Z m } and edge set {{vi , vi +1 } | i ∈ Zm } (reducing the subscript modulo m). An m-cycle system of a graph G is an ordered pair (V, C), where V is the vertex set of G and C is a set of m-cycles, the edges of which partition the edges of G. An m-cycle system of order v is an m-cycle system of K v . An m-cycle system of order v with a hole of size h is an m-cycle system of K v − K h (K v − K h is the subgraph of K v formed by removing all edges joining pairs of vertices in some subset of V (K v ) of size h). Doyen and Wilson [3] solved the problem of deciding when there exists a 3-cycle system (that is, a Steiner triple system) of order v that contains a subsystem of order u: such a system exists iff u, v ≡ 1 or 3 (mod 6) and v ≥ 2u + 1. If such a subsystem of order u is removed, then the result is a 3-cycle system of K v − K u . However, the Doyen-Wilson result does not completely solve the existence problem for 3-cycle systems of K v − K u , since the only reason that Doyen and Wilson required u ≡ 1 or 3 (mod 6) was that they needed a 3-cycle system of K u to exist. Removing this requirement allows the extra possibility that u ≡ v ≡ 5 (mod 6), and this additional case was settled by Mendelsohn and Rosa [6]. Recently, Bryant and Rodger [2] solved the problem of deciding when there exists a 5-cycle system of order v that contains a subsystem of order u: such a system exists iff *

Research supported by NSF grant DMS 9225046

104

BRYANT, HOFFMAN AND RODGER

u, v ≡ 1 or 5 (mod 10) and v ≥ 3u/2 + 1. (See [1] for a generalization to cycles of odd length.) However, again there remains the problem of finding 5-cycle systems of K v − K u . The point of this paper is to settle this problem. The additional cases to be considered can be seen from the following lemma. LEMMA 1.1 Let v > u. If there exists a 5-cycle system of K v − K u then v ≥ 3u /2 + 1, and (a) u, v ≡ 1 or 5 (mod 10), or (b) u, v ≡ 7 or 9 (mod 10), or (c) u ≡ v ≡ 3 (mod 10). Proof. Let (V , C) be a 5-cycle system of K v − K u . Let V = W ∪U, where U is the set of u vertices forming the hole, and W ∩U = ∅. If w ∈ W, then w has degreev − 1, and theedges incident with w are partitioned into pairs by the cycles. So v is odd. Similarly, considering a v u vertex in U shows that v − u is even, so u is odd. Since the total number of edges ( ) −( ) 2 2 is divisible by 5 (a), (b) and (c) follow, and the fact that v ≥ 3u/2 + 1 is shown in [5]. So in view of the Bryant-Rodger result, it remains to consider 5-cycle systems of K v − K u where u and v are as in case (b) or (c) of Lemma 1.1. Let G c denote thecomplement of G. If G and H are two graphs, then let G∪ H be thegraph with vertex set V (G) ∪ V( H) and edge set E(G) ∪ E(H ), and if V (G) ∩ V( H) = ∅ then let G ∨ H be the graph with vertex set V(G) ∪ V ( H) and edge set E(G) ∪ E(H) ∪ {{g, h } | g ∈ V (G), h ∈ V( H)}. If Di ⊆ {1, 2, . . . , bx/2c}, i ∈ Z2 , and if S ⊆ Z x , then let hD0 , S, D1 i x denote the graph with vertex set Zx × Z2 and edge set {{(i, 0), ( j, 0)} | |i − j |x ∈ D0 } ∪ {{(i, 0), ( j, 1)} | i − j (mod x ) ∈ S } ∪ {{(i, 1), ( j, 1)} | |i − j |x ∈ D1 }, where |i − j|x = min{|i − j|, x − |i − j |}. Then the following lemma is a particular case of a result of Stern and Lenz [7]. LEMMA 1.2 If D ⊆ {1, 2, . . . , bx/2c} and S ⊆ Z x , and if either |S | ≥ 1 or x/2 ∈ D then there exists a 1-factorization of h D, S, Dix . We also need the following result. A graph G is overfull if ²(G) > 1(G)bν(G)/2c, where ²(G) = | E(G)|, ν(G) = |V (G)| and 1(G) is the maximum degree of G. THEOREM 1.1 ([4]) The complete multipartite graph has chromatic index equal to the maximum degree if and only if it is not overfull. 2.

Preliminary Results

We begin by stating three results proved in [2]. A 2-factor of a graph is said to be even if each component of the 2-factor is a cycle of even length.

5-CYCLE SYSTEMS WITH HOLES

105

LEMMA 2.1 ([2]) For any even 2-factor T there exists a 5-cycle system of K 4c ∨ T . LEMMA 2.2 ([2]) If y ≤ (2x −2)/3 then there exist 3y-regular graphs G 1 , G 2 and G 3 , each with vertex set Z x × Z 2 , such that there exists a 5-cycle system of K yc ∨ G i for 1 ≤ i ≤ 3, and such that: (1) G c1 has a 1-factorization; (2) if y ≤ (2x − 4)/3 and 5|x then Gc2 − h{x /5}, ∅, {x/5}ix has a 1-factorization; and (3) if y ≤ (2 x−6)/3 and5|x then Gc3 −h{x/5, 2x/5}, ∅, {x /5, 2x/5}ix has a 1-factorization. LEMMA 2.3 ([2]) For any x ≥ 3, let T be a 2-factor defined on x vertices, and let K cx be defined on x further vertices. Then there exists a 5-cycle system of K c2 ∨ (T ∪ K cx ). We will need two more results. LEMMA 2.4 There exists a 3-regular graph G on 10 vertices such that (a) there exists a 5-cycle system of K 5c ∨ G, and (b) G c has a 1-factorization. Proof. Let G = h{1}, {0}, {1}i10 . Then ({∞1 , ∞2 , ∞3 , ∞4 , ∞ 5 } ∪ (Z5 × Z 2 ), {((0, 0), (0, 1), ∞4 , (1, 1),(1, 0)), ((0, 0), ∞2 , (2, 0), (1, 0), ∞5 ), ((0, 0), ∞3 , (1, 1),(2, 1), ∞4 ), ((0, 0), ∞ 1 , (2, 0), ∞4 , (4, 0)), ((1, 0), ∞1 , (2, 1),(2, 0), ∞3 ), ((1, 0), ∞2 , (3, 0), (3, 1), ∞4 ), ((2, 0), (3, 0),∞ 1 , (4, 0), ∞5 ), ((3, 0), (4, 0), ∞2 , (0, 1), ∞3 ), ((4, 0),(4, 1), ∞5 , (3, 1), ∞3 ), ((0, 1),(1, 1), ∞2 , (4, 1),∞ 1 ), ((0, 1), (4, 1),∞ 4 , (3, 0), ∞5 ), ((1, 1), ∞1 , (3, 1), (2, 1), ∞5 ), ((2, 1), ∞2 , (3, 1), (4, 1), ∞3 )}) is a 5-cycle system of K c5 ∨ h{1}, {0}, {1}i10 , and G c = h{2, 3, 4, 5}, Z 10\{0}, {2, 3, 4, 5}i 10 which has a 1-factorization by Lemma 1.2. LEMMA 2.5 There exists a 5-cycle system of K 13 − K 3 . Proof. ({∞1 , ∞2 , ∞3 }∪(Z 5 ×Z2 ), {(∞1 , (0, 0),(1, 0), (1,1), (0, 1))+(i, 0), (∞2 , (0, 0), (2, 0), (1, 1), (3, 1))+(i, 0), (∞3 , (0, 0), (3, 1), (1, 0), (2, 1))+ (i , 0) | i ∈ Z 5 } is a 5-cycle system of K 13 − K 3 . 3.

Constructing -cycle systems with holes

We begin by considering the cases where the size of the hole is comparatively large. PROPOSITION 3.1 Let u ≡ v ≡ 3 (mod 10) with 3u /2 + 1 ≤ v ≤ 4u . There exists a 5-cycle system of K v − K u .

106

BRYANT, HOFFMAN AND RODGER

Proof. If u = 20s + 13 + 10² with ² ∈ {0, 1} (so s ≥ 0, since v ≤ 4u implies u 6= 3) then v = 30s + 23 + 20² + 10t with 0 ≤ t ≤ 5s + 2 + 2² (by the restriction on v in the proposition). Let U be a set of size u, and V = Z 5s+5+5²+5t × Z 2 be a set of size v − u (disjoint from U). Partition the vertices in U into one set of size 4t +1 +2² and 5s −t +3+2² sets of size 4. We can apply Lemma 2.2 (1) to the set of size y = 4t + 1 + 2² and with x = 5s + 5 + 5t + 5² (so 3y ≤ 2 x − 2 since t ≤ 5s + 2 + 2²). Then since G c (with G as defined in Lemma 2.2) has a 1-factorization consisting of 2x − 1 − 3y = 10s − 2t + 6 + 4² 1-factors, these can be paired to form 5s − t + 3 + 2² even 2-factors which can be used together with the 5s − t + 3 + 2² sets of four vertices in U in applying Lemma 2.1.

As in the proof of Proposition 3.1, except where otherwise stated, let U be a set of size u and V = Z (v−u)/2 × Z 2 in the proofs of Propositions 3.2 to 3.5. PROPOSITION 3.2 Let u ≡ 7 (mod 10) and v ≡ 9 (mod 10) with 3u /2 + 1 ≤ v ≤ 4u. There exists a 5-cycle system of K v − K u . Proof. If u = 20s + 7+ 10² with ² ∈ {0, 1} (so s ≥ 0) then v = 30s + 19 + 10² + 10t with 0 ≤ t ≤ 5s + 3². Partition U into one setof size 4t + 3 −2² and 5s −t +1 + 3² sets of size 4. Apply Lemma 2.2 (1) to the set of size y = 4t + 3− 2² with x = 5s +6+ 5t (so 3 y ≤ 2x −2 since t ≤ 5s +3²). Then Gc hasa 1-factorizationconsisting of 2x −1−3y = 10s −2t +2+6² 1-factors. These can be paired to form 5s − t + 1 + 3² even 2-factors which can be used together with the 5s − t + 1 + 3² sets of four vertices in U in applying Lemma 2.1.

PROPOSITION 3.3 Let u ≡ 9 (mod 10) and v ≡ 7 (mod 10) with 3u /2 + 1 ≤ v ≤ 4u. There exists a 5-cycle system of K v − K u . Proof. If u = 20s + 9 + 10² with ² ∈ {0, 1} (so s ≥ 0) then v = 30s + 17 + 20² + 10t with 0 ≤ t ≤ 5s + 1 + 2². Partition U into one set of size 4t + 1 + 2² and 5s − t + 2 + 2² sets of size 4. Apply Lemma 2.2 (1) to the set of size y = 4t + 1 + 2² with x = 5s + 4 + 5t + 5² (so 3y ≤ 2x − 2 since t ≤ 5s + 1 + 2²). G c has a 2-factorization consisting of (2x − 1 − 3y)/2 = 5s − t + 2 + 2² even 2-factors, so the result follows from Lemma 2.1.

PROPOSITION 3.4 Let u ≡ v ≡ 9 (mod 10) with 3u/2 + 1 ≤ v ≤ 4u + 2. There exists a 5-cycle system of K v − K u . Proof. If u = 20s + 9+ 10² with ² ∈ {0, 1} (so s ≥ 0) then v = 30s + 19 + 20² + 10t with 0 ≤ t ≤ 5s + 2² + 1. Partition U into one set of size 4t + 1 + 2² and 5s − t + 2 + 2² sets of size 4. Apply Lemma 2.2 (2) to the set of size y = 4t + 1 + 2² with x = 5s + 5 + 5² + 5t (so 3y ≤ 2x − 4 since t ≤ 5s + 2² + 1). Next, G c − h{x/5}, ∅, {x/5}i x has a 2-factorization consisting of (2x − 3 − 3 y)/2 = 5s − t + 2 + 2² even 2-factors which can be used together

5-CYCLE SYSTEMS WITH HOLES

107

with the 5s − t + 2 + 2² sets of four vertices in U in applying Lemma 2.1. Finally, each component in each of the graphs h{x/5}, ∅, ∅ix and h∅, ∅, {x/5}ix is a 5-cycle.

PROPOSITION 3.5 Let u ≡ v ≡ 7 (mod 10) with 3u/2 + 1 ≤ v ≤ 4u − 2. There exists a 5-cycle system of K v − K u . Proof. In this case, the smallest embedding when u ≡ 17 (mod 20) must be done with a different set V, so we begin with it. Let u = 20s + 17 (so s ≥ 0) and v = 30s + 27. Partition U into one set of size 5 and 5s +3 sets of size 4. Define V = Z s+1 × Z 10 . For each i ∈ Z s+1 let G i be a graph with vertex set Zi × Z10 that is isomorphic to the graph G defined in Lemma 2.4, and apply Lemma 2.4 to the set of 5 vertices in U together with G i , thus defining a 5-cycle system of K 5c ∨ G i . From Lemma 2.4 (b) each G ci , i ∈ Z s+1 has a 1-factorization consisting of 6 1-factors, which together give 6 1-factors on the vertex set Z s+1 × Z 10. For 0 ≤ i < j ≤ s + 1, the edges joining vertices in Zi × Z 10 and Z j × Z 10 form a complete multipartite graph, which by Theorem 1.1 also has a 1-factorization. So altogether we have 10s + 6 1-factors which can be paired to form 5s + 3 even 2-factors which can be used together with the 5s + 3 sets of four vertices in U in applying Lemma 2.1. Now suppose u = 20s +7+10² with ² ∈ {0, 1} (so s ≥ 0). Then v = 30s +17 +20²+ 10t with 0 ≤ t ≤ 5s + 2². Partition U into one set of size 4t + 1 + 2², one set of size 2, and 5s − t + 1+ 2² sets of size 4. Apply Lemma 2.2 (3) to the set of size y = 4t + 1 + 2² with x = 5s+5+5²+5t (so3y ≤ 2x −6 since t ≤ 5s +2²). G c −h{x/5, 2x/5}, ∅, {x /5, 2x /5}i x has a 2-factorization consisting of (2x − 5 − 3 y)/2 = 5s − t + 1 + 2² even 2-factors, which can be used together with the 5s − t + 1 + 2² sets of four vertices in U in applying Lemma 2.1. Then, the set of size 2 can be used with the graph h{x /5}, ∅, ∅ix to apply Lemma 2.3, and finally each component in each of the graphs h{2 x/5}, ∅, ∅ix , h∅, ∅,{x /5}i x and h∅, ∅, {2x/5}i x is a 5-cycle. THEOREM 3.1 There exists a 5-cycle system of K v − K u if and only if (a) v ≥ 3u /2 + 1, and (b) u ≡ v ≡ 3 (mod 10), or u, v ≡ 1 or 5 (mod 10), or u , v ≡ 7 or 9 (mod 10). Proof. The proof is by induction on v. In [2] the theorem is proved for u , v ≡ 1 or 5 (mod 10). By Propositions 3.1 to 3.5, the theorem is proved if v ≤ 4u − 2, so we can assume that v ≥ 4u − 1. By Lemma 2.5 we can assume that if u = 3 then v ≥ 23. We begin by showing that there exists an integer s ≡ u or v (mod 10) such that 3u /2+ 1 ≤ s ≤ 2(v − 1)/3. Since 2(v − 1)/3 − (3u /2 + 1) ≥ (4(4u − 2) − 9u − 6)/6 ≥ 10 for u ≥ 13, clearly such an integer exists except possibly if u ∈ {3, 7, 9}. If u = 3 then v ≥ 23 so 13 is in the desired range, and if u ∈ {7, 9} then v ≥ 27 so 17 is in the desired range.

108

BRYANT, HOFFMAN AND RODGER

So in any case, let s be the largest integer with s ≡ u or v (mod 10) and 3u/2 + 1 ≤ s ≤ 2(v − 1)/3. Then by induction there exists a 5-cycle system of K s − K u , and by Propositions 3.1 to 3.5 there exists a 5-cycle system of K v − K s , so the result follows.

References 1. D. E. Bryant and C. A. Rodger, On the Doyen-Wilson Theorem for m-cycle systems, J. Combin. Designs, Vol. 2 (1994) pp. 253–271. 2. D. E. Bryant and C. A. Rodger, The Doyen-Wilson Theorem extended to 5-cycles, J. Combin. Theory Ser. A, Vol. 68 (1994) pp. 218–224. 3. J. Doyen and R.M. Wilson, Embeddings of Steiner triple systems, Discrete Math, Vol. 5 (1973) pp. 229–239. 4. D. G. Hoffman and C. A. Rodger, The chromatic index of complete multipartite graphs, J. Graph Theory, Vol. 16 (1992) pp. 159–163. 5. C. A. Rodger, Problems on cycle systems of odd length, Cong. Numer., Vol. 61 (1988) pp. 5–22. 6. E. Mendelsohn and A. Rosa, Embedding maximum packings of triples, Cong. Numer., Vol. 40 (1983) pp. 235–247. 7. G. Stern and A. Lenz, Steiner triple systems with given subspaces; another proof of the Doyen-Wilson theorem, Boll. Un. Mat. Ital. A (5), Vol. 17 (1980) pp. 109–114.