Graphs and Combinatorics (2001) 17:315±328

Graphs and Combinatorics Ó Springer-Verlag 2001

On the Volume of 5-Cycle Trades Barbara M. Maenhaut* Pure Mathematics Department, The Open University, Walton Hall, Milton Keynes, MK7 6AA, UK. e-mail: [email protected]

Abstract. A 5-cycle trade of volume t is a graph G whose edge set can be partitioned into t 5-cycles in at least two ways, such that the two collections of 5-cycles have no 5-cycles in common. The foundation of a trade is the number of vertices in the graph G. This paper determines for which values of t and v there exists a 5-cycle trade of volume t and foundation v.

1. Introduction A 5-cycle system of order n is a partition of the edge set of the complete graph on n vertices, Kn , into edge-disjoint 5-cycles. In 1966, Rosa [5] showed that 5-cycle systems exist precisely when n  1; 5 mod 10. A partial 5-cycle system is a pair …G; P†, where P is a collection of 5-cycles which form a partition of the edge set of the simple graph G. Here, isolated vertices will not be allowed in G, so the order of the partial 5-cycle system is the number of vertices in G. Also, throughout this paper, all graphs are simple. A 5-cycle trade of volume t is a graph G whose edge set can be partitioned into t 5-cycles in at least two ways, such that the two collections of 5-cycles have no 5-cycles in common. This is the de®nition which will be used throughout this paper, however the reader should be aware of equivalent de®nitions found in the literature. From [1], a 5-cycle trade of volume t is de®ned to be a pair fT1 ; T2 g where each Ti consists of t edge-disjoint 5-cycles, with the 5-cycles in T1 distinct from the 5-cycles in T2 , and the edge set of the 5-cycles in T1 being identical to the edge set of the 5-cycles in T2 . Also, following the notation from [2], a 5-cycle trade of volume t is a triple …G; T1 ; T2 † where jT1 j ˆ jT2 j ˆ t, T1 \ T2 ˆ ;, and …G; T1 † and …G; T2 † are partial 5-cycle systems. The foundation, v, of a trade is the number of distinct vertices occurring in the graph G. A 5-cycle trade of volume t with foundation v will be denoted T …t; v†. An

* Research supported by Natural Science and Engineering Research Council of Canada PGSB, University of Queensland OPRS and Australian Research Council grant A49532477

316

B.M. Maenhaut

example of a T …3; 10† is given in Figure 1. In all the examples provided in this paper, two copies of the graph will be given, showing the two partitionings of the edge set into 5-cycles. The trade spectrum for 5-cycles is the set of allowable volumes for a 5-cycle trade. From [1], the trade spectrum for 5-cycles is all non-negative integers except one. A trade of volume zero is simply an empty graph, so here we are only interested in positive trade volumes. For the remainder of this paper, a 5-cycle trade will simply be referred to as a trade. The study of trades within block designs and cycle systems arose from the need to avoid certain combinations of elements within a block or cycle of an experimental design, and so it is useful to know if trades of a given volume and foundation size exist. This problem was solved for 3-cycle trades by Bryant [2], and variations on his constructions are used here to solve the problem for 5-cycle trades. This paper will determine for which values of t there exists a trade of volume t on v vertices. Let E…v† ˆ ft j there exists a T …t; v†g. A maximum 5-cycle packing of order v is a partial 5-cycle system which has the maximum possible number of 5-cycles (for given v). A group divisible 5-cycle system on m groups of size n is a partial 5-cycle system …G; P† where G is the complete multi-partite graph with n vertices in each of its m parts. The intersection problem for a combinatorial structure involves determining how many objects (such as 5-cycles) a pair of combinatorial structures (such as 5-cycle systems), based on the same underlying set, can have in common. This paper will make direct use of two previously solved intersection problems: the intersection problems for maximum 5-cycle packings [3] and for group divisible 5-cycle systems [4].

2. Trades on a Small Number of Vertices The existence results presented in later sections will make use of many of the small trades given here. Obviously, a 5-cycle trade must have at least ®ve vertices, and must involve at least two 5-cycles. If v ˆ 5 or 6, E…v† ˆ f2g. A T …2; 5† and a T …2; 6† are given in Figure 2, and clearly no more than two 5-cycles can be placed on ®ve or six vertices. If v ˆ 7, E…v† ˆ f2; 3g. A T …2; 7† and a T …3; 7† are given in Figure 3, and clearly no more than three 5-cycles can be placed on seven vertices.

Fig. 1. A 5-cycle trade of volume three and foundation ten

On the Volume of 5-Cycle Trades

317

Fig. 2. Trades of volume two on ®ve and six vertices

Fig. 3. Trades of volumes two and three on seven vertices

If v ˆ 8, E…v† ˆ f2; 3; 4g. A T …2; 8† and T …3; 8† are given in Figure 4, and a T …4; 8† will be shown to exist in Section 5. Clearly no more than four 5-cycles may be placed on eight vertices. The ®nal small trades which will be required are a T …3; 9† and a T …3; 11†. These are given in Figure 5. 3. Necessary Conditions for the Existence of a T…t; v† Given v vertices, clearly the volume t of a trade can be no larger than the number of 5-cycles in a maximum 5-cycle packing of order v.

Fig. 4. Trades of volumes two and three on eight vertices

Fig. 5. Trades of volume three on nine and eleven vertices

318

B.M. Maenhaut

From [6], the maximum number of 5-cycles in a packing of Kv is: M

…5†

 …v† ˆ

be5v c be5v c

1

if v 6 7; 9 mod 10 if v  7; 9 mod 10

where ev ˆ v…v2 1† for v odd, and ev ˆ v…v2 2† for v even. Hence, we obtain the upper bounds on the volume of a T …t; v† shown in Table 1. Consider a graph G which is a T …t; v†. Every vertex of G must have even degree of at least two. Also, two or more vertices of each 5-cycle must have degree at least four. If v  0 mod 8, there exists a T …t; v† where exactly two vertices of each 5-cycle have degree four and any other vertices have degree two (see Figure 6). In this case, 1=4 of the vertices have degree four, the rest have degree two and hence there are v ‡ v=4 edges. Now since each 5-cycle uses ®ve edges, there must be v=4 cycles. Hence for this T …t; v†, t ˆ v=4. This is clearly the smallest trade volume which can be attained, so for any T …t; v†, t  v=4. 4. Tightening the Lower Bound If v  0 mod 8, then a T …v=4; v† consists of v=8 disjoint copies of a T …2; 8†, as in Figure 6. If v 6 0 mod 8, then the restriction t  v=4 is equivalent to t  dv=4e. Provided v 6 4 mod 8, such a trade is given by …bv=8c 1† T …2; 8†s and a trade of volume three or four on the remaining vertices. If v  4 mod 8, the sparsest trade possible consists of …v ‡ 4†=4 cycles. Such a trade is given by …bv=8c 1† T …2; 8†s and a trade of volume four on the remaining 12 vertices; a T …4; 12† will be shown to exist in Lemma 5.4. Hence, a tight lower bound on the volume of a trade on v vertices is given in Table 2. Table 1. Upper bounds on the volume of a trade on v vertices Foundation

Volume

v  0, 2 mod 10 v  1, 5 mod 10 v  3 mod 10

t  v…v10 2† t  v…v10 1† t  v…v 101† 6 t  v…v 102† 8 t  v…v 102† 4 1† 12 t  v…v 10

v  4, 8 mod 10 v  6 mod 10 v  7, 9 mod 10

Fig. 6. A sparse trade of volume v=4 and foundation v

On the Volume of 5-Cycle Trades

319

We are now left with a set, P …v†, of possible volumes for a trade on v vertices. P …v† ˆ

8 <;

v‡4 ; . . . ; M …5† …v† : 4v d4e; . . . ; M …5† …v†

if v  4 if v  4 mod 8; v  5 if v 6 4 mod 8; v  5

The rest of this paper is dedicated to showing that E…v† ˆ P …v†, for all v. 5. Existence Results To show that E…v† ˆ P …v† for all v, three constructions will be given; one for each of the large, middle and small trade volumes. Since the construction for the middle trade volumes builds on trades with smaller foundations, all trades with foundations less than or equal to 20 vertices will be explicitly listed. The ranges of trade volumes achieved by the three constructions will overlap to give the required results. The following lemma is a slight variation of [2, Lemma 3.1]. Lemma 5.1. Let …G; P1 † and …G; P2 † be a pair of partial 5-cycle systems on v vertices where: 1. jP1 j ˆ jP2 j ˆ b; 2. jP1 \ P2 j ˆ I; 3. the maximum degree of the complement G0 of G is d. If v

d

1 > 2I, then there exists a T …b

I; v†.

Proof. Since v d 1 > 2I, every vertex occurs in Gn…P1 \ P2 †. Hence Gn…P1 \ P2 † is a T …b I; v†. ( The solution to the intersection problem for maximum 5-cycle packings [3] is summarized in Table 3, along with the maximum degree d of the complement of each maximum 5-cycle packing. Using the solution to the intersection problem for maximum 5-cycle packings and Lemma 5.1, we obtain the T …t; v†s given in Table 4. Note that the small values of d have been used, as a maximum 5-cycle packing with the smaller value of d can always be constructed. Table 2. Lower bounds on the volume of a trade on v vertices Foundation

Volume

v  0 mod 8 v  1, 5 mod 8 v  2, 6 mod 8 v  3, 7 mod 8 v  4 mod 8

t  4v t  v‡3 4 t  v‡2 4 t  v‡1 4 t  v‡4 4

320

B.M. Maenhaut Table 3. Solution to the intersection problem for maximum 5-cycle packings of Kv Number of vertices

Possible Intersection Values 2

0; 1; . . . ; v 102v 2 0; 1; . . . ; v 10 v 2 0; 1; . . . ; v 10v 6 v2 2v 8 0; 1; . . . ; 10 2 2v 4 0; 1; . . . ; v 10 v2 v 12 0; 1; . . . ; 10

v  0, 2 mod 10 v  1, 5 mod 10 v  3 mod 10 v  4, 8 mod 10 v  6 mod 10 v  7, 9 mod 10

d

2

2; v 102v 2 2; v 10 v 2 2; v 10v 6 v2 2v 8 2; 10 2 2v 4 2; v 10 v2 v 12 2; 10

1 0 2 3 3 or 5 2 or 4

The following lemma appears in [2, Lemma 3.3]. Lemma 5.2. Suppose there exists a T …t1 ; v1 † having a set of m independent vertices. If there exists a T …t2 ; v2 †, then there exists a T …t1 ‡ t2 ; v1 ‡ v2 n† for n ˆ 0; 1; . . . ; min…m; v2 †. Proof. Let G1 be a T …t1 ; v1 † which contains a set of m independent vertices and let G2 be a T …t2 ; v2 †. Associate n vertices of G2 with n of the independent vertices of G1 . Then G1 [ G2 is the required trade, T …t1 ‡ t2 ; v1 ‡ v2 n†. ( Applying the ideas of [2, Lemma 3.8] to 5-cycle trades, we have the following lemma. Lemma 5.3. If v  13 and E…v 8† ˆ P …v t 2 P …v† with t  max…P …v 8†† ‡ 2.

8† then there exists a T …t; v† for all

Proof. We require that v  13 since there must exist a trade on v 8 vertices. Note that x 2 P …v† implies either x 2 fy ‡ 2 : y 2 P …v 8†g or x > max…P …v 8†† ‡ 2. Hence we need only observe that we can construct a T …t ‡ 2; v† by combining a T …2; 8† and a T …t; v 8†. ( If v is even, then max…P …v††  dv

2

2

2v 8 10 e, and hence 2 v 12 dv 10 e, and hence

max…P …v

8†† 

dv 18v‡72 e. If v is odd, then max…P …v††  max…P …v 8††  10 v2 17v‡60 d 10 e. Therefore, by Lemma 5.3, we obtain a T …t; v† for all values of t listed in Table 5. Table 4. Large trade volumes Foundation v  0; 2 mod 10 v  1; 5 mod 10 v  3 mod 10 v  4; 8 mod 10 v  6 mod 10 v  7; 9 mod 10

Volume 2 7v‡20 v2 7v‡30 ; 10 ; . . . ; v 102v 10 2 v2 6v‡15 v2 6v‡25 ; 10 ; . . . ; v 10 v 10 2 2 2 v 6v‡19 v 6v‡29 ; 10 ; . . . ; v 10v 6 10 2 v2 7v‡22 v2 7v‡32 2v 8 ; 10 ; . . . ; v 10 10 v2 7v‡26 v2 7v‡36 v2 2v 4 ; 10 ; . . . ; 10 10 2 v2 6v‡13 v2 6v‡23 v 12 ; 10 ; . . . ; v 10 10

v

2

On the Volume of 5-Cycle Trades

321

A new trade may be constructed simply by combining two smaller trades, since there is no condition that a trade must be a connected graph. Lemma 5.2 also shows that two smaller trades may combine to form a larger trade by overlapping on some independent vertices in one of the smaller trades. For the remainder of the paper this straightforward construction will be represented by the following notation. Let T …t1 ; v1 † ‡ T …t2 ; v2 † < x > represent a combination of the trades T …t1 ; v1 † and T …t2 ; v2 † overlapping on x independent vertices of the T …t1 ; v1 †. Lemma 5.4. E…v† ˆ P …v† for all v  20. Proof. Notice that the T …2; 7† given in Section 2 contains a set of four independent vertices and the T …3; 7† contains a set of three independent vertices. For v  4, E…v† ˆ P …v† ˆ ;. For v ˆ 5; 6; 7, it was shown in Section 2 that E…v† ˆ P …v†. For v ˆ 8, P …v† ˆ f2; 3; 4g. A T …2; 8† and T …3; 8† are given in Section 2, while a T …4; 8† exists by Table 4. For v ˆ 9, P …v† ˆ f3; 4; 5; 6g. A T …3; 9† is given in Section 2, a T …4; 9† ˆ T …2; 5† ‡ T …2; 5† < 1 >, and a T …5; 9† and T …6; 9† exist by Table 4. For v ˆ 10, P …v† ˆ f3; 4; 5; 6; 7; 8g. A T …3; 10† is given in Section 1, a T …4; 10† ˆ T …2; 5† ‡ T …2; 5† < 0 >, and T …t; 10†s exist for t ˆ 5; 6; 7; 8 by Table 4. For v ˆ 11, P …v† ˆ f3; 4; . . . ; 11g. A T …3; 11† is given in Section 2, a T …4; 11† ˆ T …2; 5† ‡ T …2; 6† < 0 >, a T …5; 11† ˆ T …2; 5† ‡ T …3; 7† < 1 >, and a T …6; 11† ˆ T …3; 7† ‡ T …3; 7† < 3 >. T …t; 11†s exist for t ˆ 7; 8; 9; 10; 11 by Table 4. For v ˆ 12, P …v† ˆ f4; 5; . . . ; 12g. A T …4; 12† ˆ T …2; 6† ‡ T …2; 6† < 0 >, a T …5; 12† ˆ T …2; 5† ‡ T …3; 7† < 0 >, a T …6; 12† ˆ T …2; 5† ‡ T …4; 8† < 1 >, and a T …7; 12† ˆ T …2; 7† ‡ T …5; 9† < 4 >. T …t; 12†s exist for t ˆ 8; 9; . . . ; 12 by Table 4. For v ˆ 13, P …v† ˆ f4; 5; . . . ; 15g. Lemma 5.3 gives a T …4; 13†. A T …5; 13† ˆ T …2; 5† ‡ T …3; 8† < 0 >, a T …6; 13† ˆ T …2; 5† ‡ T …4; 8† < 0 >, a T …7; 13† ˆ T …2; 5† ‡ T …5; 9† < 1 >, a T …8; 13† ˆ T …2; 5† ‡ T …6; 9† < 1 >, a T …9; 13† ˆ T …3; 7† ‡ T …6; 9† < 3 >, and a T …10; 13† ˆ T …2; 7† ‡ T …8; 10† < 4 >. T …t; 13†s exist for t ˆ 11; 12; . . . ; 15 by Table 4. For v ˆ 14, P …v† ˆ f4; 5; . . . ; 16g. Lemma 5.3 gives a T …4; 14†. A T …5; 14† ˆ T …2; 6† ‡ T …3; 8† < 0 >, a T …6; 14† ˆ T …2; 6† ‡ T …4; 8† < 0 >, a T …7; 14† ˆ T …2; 5† ‡ T …5; 9† < 0 >, a T …8; 14† ˆ T …2; 5† ‡ T …6; 9† < 0 >, a Table 5. Small trade volumes Foundation

Volume

v  0 mod 8, v  13 v  1, 5 mod 8, v  13 v  2, 6 mod 8, v  13 v  3, 7 mod 8, v  13 v  4 mod 8, v  13

v v‡4 v2 18v‡92 e 4 ; 4 ; . . . ; d 2 10 v‡3 v‡7 v 17v‡80 e 4 ; 4 ; . . . ; d 2 10 v‡2 v‡6 v 18v‡92 e 4 ; 4 ; . . . ; d 2 10 v‡1 v‡5 v 17v‡80 ; ; . . . ; d e 4 4 10 v‡4 v‡8 v2 18v‡92 ; ; . . . ; d e 4 4 10

322

B.M. Maenhaut

T …9; 14† ˆ T …2; 5† ‡ T …7; 10† < 1 >, a T …10; 14† ˆ T …2; 5† ‡ T …8; 10† < 1 >, and a T …11; 14† ˆ T …2; 7† ‡ T …9; 11† < 4 >. T …t; 14†s exist for t ˆ 12; 13; . . . ; 16 by Table 4. For v ˆ 15, P …v† ˆ f4; 5; . . . ; 21g. Lemma 5.3 gives a T …4; 15† and a T …5; 15†. A T …6; 15† ˆ T …2; 7† ‡ T …4; 8† < 0 >, a T …7; 15† ˆ T …2; 6† ‡ T …5; 9† < 0 >, a T …8; 15† ˆ T …2; 6† ‡ T …6; 9† < 0 >, a T …9; 15† ˆ T …2; 5† ‡ T …7; 10† < 0 >, a T …10; 15† ˆ T …2; 5† ‡ T …8; 10† < 0 >, a T …11; 15† ˆ T …2; 5† ‡ T …9; 11† < 1 >, a T …12; 15† ˆ T …2; 5† ‡ T …10; 11† < 1 >, a T …13; 15† ˆ T …2; 5† ‡ T …11; 11† < 1 >, and a T …14; 15† ˆ T …2; 7† ‡ T …12; 12† < 4 >. T …t; 15†s exist for t ˆ 15; 16; . . . ; 21 by Table 4. For v ˆ 16, P …v† ˆ f4; 5; . . . ; 22g. Lemma 5.3 gives a T …4; 16†, a T …5; 16† and a T …6; 16†. A T …7; 16† ˆ T …2; 7† ‡ T …5; 9† < 0 >, a T …8; 16† ˆ T …2; 7† ‡ T …6; 9† < 0 >, a T …9; 16† ˆ T …2; 6† ‡ T …7; 10† < 0 >, a T …10; 16† ˆ T …2; 6† ‡ T …8; 10† < 0 >, a T …11; 16† ˆ T …2; 5† ‡ T …9; 11† < 0 >, a T …12; 16† ˆ T …2; 5† ‡ T …10; 11† < 0 >, a T …13; 16† ˆ T …2; 5† ‡ T …11; 11† < 0 >, a T …14; 16† ˆ T …2; 5† ‡ T …12; 12† < 1 >, a T …15; 16† ˆ T …2; 7† ‡ T …13; 13† < 4 >, and a T …16; 16† ˆ T …2; 7† ‡ T …14; 13† < 4 >. T …t; 16†s exist for t ˆ 17; 18; . . . ; 22 by Table 4. For v ˆ 17, P …v† ˆ f5; 6; . . . ; 26g. Lemma 5.3 gives a T …t; 17† for t ˆ 5; 6; 7; 8. A T …9; 17† ˆ T …2; 7† ‡ T …7; 10† < 0 >, a T …10; 17† ˆ T …2; 7† ‡ T …8; 10† < 0 >, a T …11; 17† ˆ T …2; 6† ‡ T …9; 11† < 0 >, a T …12; 17† ˆ T …2; 6† ‡ T …10; 11† < 0 >, a T …13; 17† ˆ T …2; 6† ‡ T …11; 11† < 0 >, a T …14; 17† ˆ T …2; 5† ‡ T …12; 12† < 0 >, a T …15; 17† ˆ T …2; 5† ‡ T …13; 13† < 1 >, a T …16; 17† ˆ T …2; 5† ‡ T …14; 13† < 1 >, a T …17; 17† ˆ T …2; 5† ‡ T …15; 13† < 1 >, and a T …18; 17† ˆ T …2; 7† ‡ T …16; 14† < 4 >. A T …19; 17† can be constructed as follows: a pair of group divisible 5-cycle systems with three groups of size ®ve and intersection zero [4] will provide a T …15; 15† with three sets of ®ve independent vertices; place a T …2; 7† on one set plus two new vertices to give a T …17; 17†; place a T …2; 5† on one of the other sets of ®ve independent vertices to obtain a T …19; 17†. T …t; 17†s exist for t ˆ 20; 21; . . . ; 26 by Table 4. For v ˆ 18, P …v† ˆ f5; 6; . . . ; 28g. Lemma 5.3 gives a T …t; 18† for t ˆ 5; 6; . . . ; 10. A T …11; 18† ˆ T …2; 7† ‡ T …9; 11† < 0 >, a T …12; 18† ˆ T …2; 7†‡ T …10; 11† < 0 >, a T …13; 18† ˆ T …2; 7† ‡ T …11; 11† < 0 >, a T …14; 18† ˆ T …2; 6†‡ T …12; 12† < 0 >, a T …15; 18† ˆ T …2; 5† ‡ T …13; 13† < 0 >, a T …16; 18† ˆ T …2; 5† ‡ T …14; 13† < 0 >, a T …17; 18† ˆ T …2; 5† ‡ T …15; 13† < 0 >, a T …18; 18† ˆ T …2; 5† ‡ T …16; 14† < 1 >, a T …19; 18† ˆ T …2; 7† ‡ T …17; 15† < 4 >, a T …20; 18† ˆ T …2; 7† ‡ T …18; 15† < 4 >, and a T …21; 18† ˆ T …2; 7† ‡ T …19; 15† < 4 >. T …t; 18†s exist for t ˆ 22; . . . ; 28 by Table 4. For v ˆ 19, P …v† ˆ f5; 6; . . . ; 33g. Lemma 5.3 gives a T …t; 19† for t ˆ 5; 6; . . . ; 13. A T …14; 19† ˆ T …2; 7† ‡ T …12; 12† < 0 >, a T …15; 19† ˆ T …2; 6† ‡ T …13; 13† < 0 >, a T …16; 19† ˆ T …2; 6† ‡ T …14; 13† < 0 >, a T …17; 19† ˆ T …2; 6† ‡ T …15; 13† < 0 >, a T …18; 19† ˆ T …2; 5† ‡ T …16; 14† < 0 >, a T …19; 19† ˆ T …2; 5† ‡ T …17; 15† < 1 >, a T …20; 19† ˆ T …2; 5† ‡ T …18; 15† < 1 >, a T …21; 19† ˆ T …2; 5† ‡ T …19; 15† < 1 >, a T …22; 19† ˆ T …2; 5† ‡ T …20; 15† < 1 >, a T …23; 19† ˆ T …2; 5† ‡ T …21; 15† < 1 >, and a T …24; 19† ˆ T …2; 7† ‡ T …22; 16† < 4 >. A T …25; 19† may be constructed as follows: take a T …15; 15† with three sets of ®ve independent vertices (as in the case v ˆ 17); place a T …6; 9† on one set of ®ve vertices plus four new vertices

On the Volume of 5-Cycle Trades

323

to get a T …21; 19†; place a T …2; 5† on each of the remaining sets of ®ve independent vertices to get a T …25; 19†. T …t; 19†s exist for t ˆ 26; 27; . . . ; 33 by Table 4. For v ˆ 20, P …v† ˆ f6; 7; . . . ; 36g. Lemma 5.3 gives a T …t; 20† for t ˆ 6; 7; . . . ; 14. A T …15; 20† ˆ T …2; 7† ‡ T …13; 13† < 0 >, a T …16; 20† ˆ T …2; 7† ‡ T …14; 13† < 0 >, a T …17; 20† ˆ T …2; 7† ‡ T …15; 13† < 0 >, a T …18; 20† ˆ T …2; 6† ‡ T …16; 14† < 0 >, a T …19; 20† ˆ T …2; 5† ‡ T …17; 15† < 0 >, a T …20; 20† ˆ T …2; 5† ‡ T …18; 15† < 0 >, a T …21; 20† ˆ T …2; 5† ‡ T …19; 15† < 0 >, a T …22; 20† ˆ T …2; 5† ‡ T …20; 15† < 0 >, a T …23; 20† ˆ T …2; 5† ‡ T …21; 15† < 0 >, a T …24; 20† ˆ T …2; 5† ‡ T …22; 16† < 1 >, a T …25; 20† ˆ T …2; 7† ‡ T …23; 17† < 4 >, a T …26; 20† ˆ T …2; 7† ‡ T …24; 17† < 4 >, and a T …27; 20† ˆ T …2; 7† ‡ T …25; 17† < 4 >. T …t; 20†s exist for t ˆ 28; 29; . . . ; 36 by Table 4. ( The following lemma is an extension of [2, Lemma 3.5]. Lemma 5.5. Let …G; P1 † and …G; P2 † be a pair of group divisible 5-cycle systems with ®ve groups of size y, and hence jP1 j ˆ jP2 j ˆ 2y 2 . Suppose that jP1 \ P2 j ˆ I. 1. If there exist T …tj ; y†s for j ˆ 1; . . . ; 5, then there exists a T …t1 ‡ t2 ‡ t3 ‡ t4 ‡ t5 ‡ 2y 2 I; 5y†. 2. If there exists a T …t1 ; y ‡ 1† and T …tj ; zj †s for j ˆ 2; . . . ; 5 where zj ˆ y or y ‡ 1, then there exists a T …t1 ‡ t2 ‡ t3 ‡ t4 ‡ t5 ‡ 2y 2 I; 5y ‡ 1†. 3. If there exists a T …t1 ; y ‡ 2† and T …tj ; zj †s for j ˆ 2; . . . ; 5 where zj ˆ y or y ‡ 1 or y ‡ 2 and where at most one of the trades of order y ‡ 2 contains no pair of independent vertices, then there exists a T …t1 ‡ t2 ‡ t3 ‡ t4 ‡ t5 ‡ 2y 2 I; 5y ‡ 2†. 4. If there exists a T …t1 ; y ‡ 3† and T …tj ; zj †s for j ˆ 2; . . . ; 5 where zj ˆ y or y ‡ 1 or y ‡ 2 or y ‡ 3 and where at most one of the trades of orders y ‡ 2 and y ‡ 3 contain no pair or no triple of independent vertices respectively, then there exists a T …t1 ‡ t2 ‡ t3 ‡ t4 ‡ t5 ‡ 2y 2 I; 5y ‡ 3†. 5. If there exists a T …t1 ; y ‡ 4† and T …tj ; zj †s for j ˆ 2; . . . ; 5 where zj ˆ y or y ‡ 1 or y ‡ 2 or y ‡ 3 or y ‡ 4, and where at most one of the trades of orders y ‡ 2, y ‡ 3 and y ‡ 4 contain no pair, no triple, or no set of four independent vertices respectively, then there exists a T …t1 ‡ t2 ‡ t3 ‡ t4 ‡ t5 ‡ 2y 2 I; 5y ‡ 4†. Proof. We will proceed by applying Lemma 5.1. However here we can ignore the condition that v d 1 > 2I since that was included to ensure there were no isolated vertices; we will be adding extra 5-cycles from the trades of volume tj so that we will have no isolated vertices. From the two initial group divisible 5-cycle systems, Lemma 5.1 allows us to assume that we have a T …2y 2 I; 5y† which contains ®ve disjoint sets of y independent vertices. The results follow from Lemma 5.2 applied ®ve times. ( Lemma 5.6. For v > 20, if E…u† ˆ P …u† for all u  v then there exists a T …t; v† for all t and v given in Table 6. Proof. This proof makes use of the following three facts. By [4], there exists a pair of group divisible 5-cycle systems with ®ve groups of size y and with intersections f0; 1; . . . ; 2y 2 2; 2y 2 g. If u is odd and E…u† ˆ P …u†, then there exist T …t; u†s for at

324

B.M. Maenhaut 2

u 12 least all t in the range du4e; . . . ; du 10 e. If u is even and E…u† ˆ P …u†, then there 2 2u 8 exist T …t; u†s for at least all t in the range du4e ‡ 1; . . . ; du 10 e. Consider the cases v  0; 1; . . . ; 9 mod 10, one at a time. v ˆ 10x We need only consider x  3.

If x ˆ 3, there exists a T …t; 2x† with t ˆ 2 and we can combine this with the group divisible 5-cycle systems on ®ve groups of size 2x with intersections f0; 1; 2; . . . ; 70; 72g using Lemma 5.5 (1) to construct T …10; 30†, T …12; 30†, T …13; 30†; . . . ; T …82; 30†. If x  4, there exist T …t; 2x†s for at least all integers t where 4x2 4x 8 d2x e e. Hence there exist T …t; 2x†s for at least all integers t where 4 ‡ 1  t  2d 10 2x 2x 4 dx‡2 e  t  d e. When x  4, this range contains at least two values of t, so 2 5 these trades can be used together with the group divisible 5-cycle systems on ®ve groups of size 2x with intersections f0; 1; . . . ; 8x2 2; 8x2 g in Lemma 5.5 (1), to 2 obtain at least T …d5x‡15 2x 4 ‡ 8x2 ; 10x†. In terms of v, we 2 e; 10x†; . . . ; T …2x v‡30 v2 2v 40 obtain the trades T …d 4 e; v†; . . . ; T … 10 ; v†. v ˆ 10x ‡ 1 We need only consider x  2. If x ˆ 2, there exists a T …t; 2x ‡ 1† with t ˆ 2 and we can combine this trade with the group divisible 5-cycle systems on ®ve groups of size 2x with intersections f0; 1; . . . ; 30; 32g using Lemma 5.5 (2) to construct T …10; 21†, T …12; 21†, T …13; 21†; . . . ; T …42; 21†. If x  3, there exist T …t; 2x ‡ 1†s for at least all integers t where 4x2 ‡2x 12 d2x‡1 e. Hence there exist T …t; 2x ‡ 1†s for at least all integers t 4 e t  d 10 2x2 ‡x 6 where dx‡1 e  t  d e. When x  3, this range contains at least two values 2 5 Table 6. Middle trade volumes Foundation v ˆ 30 v  0 mod 10, v ˆ 21 v  1 mod 10, v ˆ 22 v  2 mod 10, v  3 mod 10, v ˆ 24 v  4 mod 10, v ˆ 25 v  5 mod 10, v ˆ 26 v  6 mod 10, v  7 mod 10, v  8 mod 10, v ˆ 29 v ˆ 39 v  9 mod 10,

v  40 v  31 v  32 v  23 v  34 v  35 v  36 v  27 v  28 v  49

Volume 10; 12; 13; . . . ; 282 v‡34 v 2v 40 dv‡30 4 e; d 4 e; . . . ; 10 10; 12; 13; . . . ; 42 v‡19 v‡23 v2 v 60 d 4 e; d 4 e; . . . ; 10 10; 12; 13; . . . ; 42 v‡42 v2 2v 40 dv‡38 4 e; d 4 e; . . . ; 2 10 v‡37 v 4v 27 dv‡33 4 e; d 4 e; . . . ; 10 10; 11; . . . ; 482 v‡40 v 6v 12 dv‡36 4 e; d 4 e; . . . ; 10 10; 12; 13; . . . ; 60 2 v‡19 v v 60 dv‡15 4 e; d 4 e; . . . ; 10 10; 12; 13; . . . ; 260 v‡38 v 2v 44 dv‡34 4 e; d 4 e; . . . ; 2 10 v‡27 v v 92 dv‡23 e; d e; . . . ; 4 4 10 v‡28 v2 3v 80 dv‡24 4 e; d 4 e; . . . ; 10 11; 12; . . . ; 68 15; 16; . . . ; 133 v‡25 v2 5v 36 dv‡21 4 e; d 4 e; . . . ; 10

On the Volume of 5-Cycle Trades

325

for t, so these trades can be used together with the group divisible 5-cycle systems on ®ve groups of size 2x with intersections f0; 1; . . . ; 8x2 2; 8x2 g in Lemma 5.5 2 (2), to obtain at least T …d5x‡10 6 ‡ 8x2 ; 10x ‡ 1†. In 2 e; 10x ‡ 1†; . . . ; T …2x2 ‡ x v‡19 v v 60 terms of v, we obtain the trades T …d 4 e; v†; . . . ; T … 10 ; v†. v ˆ 10x ‡ 2 We need only consider x  2. If x ˆ 2, there exists a T …t; 2x ‡ 2† with t ˆ 2 and a T …2; 6† contains a pair of independent vertices so we can combine this trade with the group divisible 5-cycle systems on ®ve groups of size 2x with intersections f0; 1; . . . ; 30; 32g using Lemma 5.5 (3) to construct T …10; 22†, T …12; 22†, T …13; 22†; . . . ; T …42; 22†. If x  3, there exist T …t; 2x ‡ 2†s for at least all integers t where 4x d2x‡2 4 e‡1 t d

dx‡3 2 e

2

‡4x 8 e. Hence there exist T …t; 2x ‡ 2†s for 10 2x2 ‡2x 4 d 5 e. Each T …t; 2x ‡ 2† will contain a

at least all integers t

where t pair of independent vertices since 2x ‡ 2 is even. When x  3, this range contains at least two values for t, so these trades can be used together with the group divisible 5-cycle systems on ®ve groups of size 2x with intersections f0; 1; . . . ; 8x2 2; 8x2 g in Lemma 5.5 2 (3), to obtain at least T …d5x‡20 4 ‡ 8x2 ; 10x ‡ 2†. In 2 e; 10x ‡ 2†; . . . ; T …2x 2 ‡ 2x v‡38 v 2v 40 terms of v, we obtain the trades T …d 4 e; v†; . . . ; T … 10 ; v†. v ˆ 10x ‡ 3 We need only consider x  2. If x  2, there exist T …t; 2x ‡ 3†s for at least all integers t where 4x2 ‡10x 6 d2x‡3 e. Hence there exist T …t; 2x ‡ 3†s for at least all integers t 4 e t  d 10 2 x‡2 3 where d 2 e  t  d2x ‡5x e. When x  2, this range contains at least two values 5 for t. However, we cannot guarantee that these trades will each contain three independent vertices so we will construct our trades using some T …t; 2x ‡ 2†s, which we know contain pairs of independent vertices since 2x ‡ 2 is even. Hence, by applying Lemma 5.5 (4) with one trade on 2x ‡ 3 vertices and four trades on 2x ‡ 2 vertices, together with the group divisible 5-cycle systems on ®ve groups of size 2x with intersections f0; 1; . . . ; 8x2 2; 8x2 g, the smallest trade volume we can x‡3 construct (with I ˆ 8x2 ) is dx‡2 2 e ‡ 4d 2 e, and the largest trade volume we can 2 2 3 4 construct (with I ˆ 0) is d2x ‡5x e ‡ 4d2x ‡2x e ‡ 8x2 . Simplifying these expres5 5 2 5x‡18 30 sions we obtain at least the trades T …d 2 e; 10x ‡ 3†; . . . ; T …100x ‡20x ; 10x ‡ 3†. 10 2 v‡33 v 4v 27 In terms of v, we obtain the trades T …d 4 e; v†; . . . ; T … 10 ; v†. v ˆ 10x ‡ 4 We need only consider x  2. If x ˆ 2, there exist T …t; 2x ‡ 4†s for t ˆ f2; 3; 4g. However, these trades do not each contain a set of four independent vertices. For x ˆ 2, there exist T …t; 2x ‡ 3†s for t ˆ f2; 3g each containing a set of three independent vertices. Hence, applying Lemma 5.5 (5) with one trade on 2x ‡ 4 vertices and four trades on 2x ‡ 3 vertices, together with the group divisible 5-cycle systems on ®ve groups of size 2x with intersections f0; 1; . . . ; 30; 32g, we obtain the trades T …10; 24†; . . . ; T …48; 24†. If x  3, there exist T …t; 2x ‡ 4†s for at least all integers t where 2

4x ‡12x d2x‡4 4 e ‡ 1  t  d 10 e. Hence there exist T …t; 2x ‡ 4†s for at least all integers t 2

2x ‡6x where dx‡4 2 e  t  d 5 e, and this range contains at least two values for t. However, we cannot guarantee that these trades will each contain four indepen-

326

B.M. Maenhaut

dent vertices so we will construct our trades using some T …t; 2x ‡ 2†s, which we know contain pairs of independent vertices since 2x ‡ 2 is even. Hence, by applying Lemma 5.5 (5) with one trade on 2x ‡ 4 vertices and four trades on 2x ‡ 2 vertices, together with the group divisible 5-cycle systems on ®ve groups of size 2x with intersections f0; 1; . . . ; 8x2 2; 8x2 g, the smallest trade volume we can conx‡3 struct (with I ˆ 8x2 ) is dx‡4 2 e ‡ 4d 2 e, and the largest trade volume we can con2

struct (with I ˆ 0) is d2x 5‡6xe ‡ 4d2x

2

‡2x 4 e 5

‡ 8x2 . Simplifying these expressions we

100x obtain at least the trades T …d5x‡20 2 e; 10x ‡ 4†; . . . ; T …

of v, we obtain the trades

v T …dv‡36 4 e; v†; . . . ; T …

2

2

‡20x 20 ; 10x 10

‡ 4†. In terms

6v 12 ; v†. 10

v ˆ 10x ‡ 5 We need only consider x  2. If x ˆ 2, there exists a T …t; 2x ‡ 1† with t ˆ 2 and we can combine this trade with the group divisible 5-cycle systems on ®ve groups of size 2x ‡ 1 with intersections f0; 1; . . . ; 48; 50g using Lemma 5.5 (1) to construct T …10; 21†, T …12; 21†, T …13; 21†; . . . ; T …60; 21†. If x  3, there exist T …t; 2x ‡ 1†s for at least all integers t where 4x2 ‡2x 12 d2x‡1 e. Hence there exist T …t; 2x ‡ 1†s for at least all integers t 4 e t  d 10 2 x‡1 6 where d 2 e  t  d2x ‡x e. When x  3, this range contains at least two values 5 for t, so these trades can be used together with the group divisible 5-cycle systems on ®ve groups of size 2x ‡ 1 with intersections f0; 1; . . . ; 8x2 ‡ 8x; 8x2 ‡ 8x ‡ 2g in 2 Lemma 5.5 (1), to obtain at least T …d5x‡10 6‡ 2 e; 10x ‡ 5†; . . . ; T …2x ‡ x v‡15 2 8x ‡ 8x ‡ 2; 10x ‡ 5†. In terms of v, we obtain the trades T …d 4 e; v†; . . . ; 2 v 60 T …v 10 ; v†. v ˆ 10x ‡ 6 We need only consider x  2. If x ˆ 2, there exists a T …t; 2x ‡ 2† with t ˆ 2 and we can combine this trade with the group divisible 5-cycle systems on ®ve groups of size 2x ‡ 1 with intersections f0; 1; 2; . . . ; 48; 50g using Lemma 5.5 (2) to construct T …10; 26†, T …12; 26†, T …13; 26†; . . . ; T …60; 26†. If x  3, there exist T …t; 2x ‡ 2†s for at least all integers t where 4x d2x‡2 4 e‡1 t d

2

‡4x 8 e. Hence there exist T …t; 2x ‡ 2†s for at least all integers t 10 2 4 d2x ‡2x e. When x  3, this range contains at least two values 5

where dx‡3 2 e  t  for t, so these trades can be used together with the group divisible 5-cycle systems on ®ve groups of size 2x ‡ 1 with intersections f0; 1; . . . ; 8x2 ‡ 8x; 8x2 ‡ 8x ‡ 2g in 2 2 Lemma 5.5 (2) to obtain at least T …d5x‡20 2 e; 10x ‡ 6†; . . . ; T …2x ‡ 2x 2 4 ‡ 8x ‡ v‡34 v 2v 44 8x ‡ 2; 10x ‡ 6†. In terms of v, we obtain the trades T …d 4 e; v†; . . . ; T … 10 ; v†. v ˆ 10x ‡ 7 We need only consider x  2. If x  2, there exist T …t; 2x ‡ 3†s for at least all integers t where 4x2 ‡10x 6 d2x‡3 e. Hence there exist T …t; 2x ‡ 3†s for at least all integers t 4 e t  d 10 2x2 ‡5x 3 where dx‡2 e  t  d e. When x  2, this range contains at least two values 2 5 for t. We cannot guarantee that these trades will each contain a pair of independent vertices, but a trade on 2x ‡ 3 vertices will contain a pair of independent vertices provided it is not of maximum volume. Hence, we can apply Lemma 5.5 (3) with one trade on 2x ‡ 3 vertices which is allowed to be any volume, and four

On the Volume of 5-Cycle Trades

327

trades on 2x ‡ 3 vertices which are allowed to be any volume except the maximum possible volume, together with the group divisible 5-cycle systems on ®ve groups of size 2x ‡ 1 with intersections f0; 1; . . . ; 8x2 ‡ 8x; 8x2 ‡ 8x ‡ 2g. Now, by applying Lemma 5.5 (3), the smallest trade volume we can construct (with I ˆ 8x2 ‡ 8x ‡ 2) is 5dx‡2 2 e and the largest trade volume we can construct (with 2 3 2x2 ‡5x 3 e ‡ 4…d e 1† ‡ 8x2 ‡ 8x ‡ 2. Simplifying these expresI ˆ 0) is d2x ‡5x 5 5 2 sions we obtain at least the trades T …d5x‡15 ‡ 13x 5; 2 e; 10x ‡ 7†; . . . ; T …10x v‡23 v2 v 92 10x ‡ 7†. In terms of v, we obtain the trades T …d 4 e; v†; . . . ; T … 10 ; v†. v ˆ 10x ‡ 8 We need only consider x  2. If x  2, there exist T …t; 2x ‡ 4†s for at least all integers t where 4x2 ‡12x d2x‡4 4 e ‡ 1  t  d 10 e. Hence there exist T …t; 2x ‡ 4†s for at least all integers t 2

2x ‡6x where dx‡4 2 e  t  d 5 e. When x  2, this range contains at least two values for t. We cannot guarantee that these trades will each contain a set of three independent vertices, but a trade on 2x ‡ 3 vertices will contain a pair of independent vertices provided it is not of maximum volume. Hence, we can apply Lemma 5.5 (4) with one trade on 2x ‡ 4 vertices which is allowed to be any volume, and four trades on 2x ‡ 3 vertices which are allowed to be any volume except the maximum possible volume, together with the group divisible 5-cycle systems on ®ve groups of size 2x ‡ 1 with intersections f0; 1; . . . ; 8xx ‡ 8x; 8x2 ‡ 8x ‡ 2g. Now, by applying Lemma 5.5 (4), the smallest trade volume we can construct (with x‡2 I ˆ 8x2 ‡ 8x ‡ 2) is dx‡4 2 e ‡ 4d 2 e and the largest trade volume we can construct 2

(with I ˆ 0) is d2x 5‡6xe ‡ 4…d2x

2

‡5x 3 e 5

1† ‡ 8x2 ‡ 8x ‡ 2. Simplifying these

100x expressions we obtain at least the trades T …d5x‡16 2 e; 10x ‡ 8†; . . . ; T …

v 10x ‡ 8†. In terms of v, we obtain the trades T …dv‡24 4 e; v†; . . . ; T …

2

2

‡130x 40 ; 10

3v 80 ; v†. 10

v ˆ 10x ‡ 9 We need only consider x  2. If x ˆ 2, there exist T …t; 2x ‡ 5†s for t ˆ f3; 4; 5; 6g. However, these trades do not each contain a set of four independent vertices. For x ˆ 2, there exist T …t; 2x ‡ 3†s for t ˆ f2; 3g each containing a pair of independent vertices. Hence, applying Lemma 5.5 (5) with one trade on 2x ‡ 5 vertices and four trades on 2x ‡ 3 vertices, together with the group divisible 5-cycle systems on ®ve groups of size 2x ‡ 1 with intersections f0; 1; . . . ; 48; 50g, we obtain the trades T …11; 29†; . . . ; T …68; 29†. If x ˆ 3, there exist T …t; 2x ‡ 5†s for t ˆ f3; 4; . . . ; 11g. However, these trades do not each contain a set of four independent vertices. For x ˆ 3, there exist T …t; 2x ‡ 3†s for t ˆ f3; 4; 5; 6g each containing a pair of independent vertices. Hence, applying Lemma 5.5 (5) with one trade on 2x ‡ 5 vertices and four trades on 2x ‡ 3 vertices, together with the group divisible 5-cycle systems on ®ve groups of size 2x ‡ 1 with intersections f0; 1; . . . ; 96; 98g, we obtain the trades T …15; 39†; . . . ; T …133; 39†. If x  4, there exist T …t; 2x ‡ 5†s for at least all integers t where 4x2 ‡18x‡8 d2x‡5 e. Hence there exist T …t; 2x ‡ 5†s for at least all integers t 4 e t  d 10 x‡3 2x2 ‡9x‡4 where d 2 e  t  d 5 e, and this range contains at least two values for t. We

328

B.M. Maenhaut

cannot guarantee that these trades will each contain a set of four independent vertices, but a trade on 2x ‡ 3 vertices will contain a pair of independent vertices provided it is not of maximum volume. Hence, we can apply Lemma 5.5 (5) with one trade on 2x ‡ 5 vertices which is allowed to be any volume, and four trades on 2x ‡ 3 vertices which are allowed to be any volume except the maximum possible volume, together with the group divisible 5-cycle systems on ®ve groups of size 2x ‡ 1 with intersections f0; 1; . . . ; 8x2 ‡ 8x; 8x2 ‡ 8x ‡ 2g. Now, by applying Lemma 5.5 (5), the smallest trade volume we can construct (with I ˆ 8x2 ‡ 8x ‡ 2) x‡2 is dx‡3 2 e ‡ 4d 2 e and the largest trade volume we can construct (with I ˆ 0) is 2 2x2 ‡9x‡4 3 e 1† ‡ 8x2 ‡ 8x ‡ 2. Simplifying these expressions we d 5 e ‡ 4…d2x ‡5x 5 2 . . . ; T …100x 10‡130x ; 10x ‡ 9†. In terms of obtain at least the trades T …d5x‡15 2 e; 10x ‡ 9†; 2 v 5v 36 v, we obtain the trades T …dv‡21 ; v†. ( 4 e; v†; . . . ; T … 10 Theorem 5.7. For all non-negative integers v, E…v† ˆ P …v†. Proof. By Lemma 5.4, if v  20, then the result holds. For v > 20, we proceed by considering each of the values of v modulo 10. We need to check that the trade volumes given in Tables 4, 5 and 6 overlap to cover all possible trade volumes. Consider v  1 mod 10. If v ˆ 21, P …v† ˆ f6; 7; . . . ; 42g. Table 4 gives volumes 33; 34; . . . ; 42, Table 6 gives volumes 10; 12; 13; . . . ; 42, and Table 5 gives volumes 6; 7; . . . ; 17. 2 2 2 If v  31, P …v† ˆ fd4ve; . . . ; v 10 vg. Table 4 gives volumes v 6v‡15  t  v 10 v, Table 10 2

v v 60 v 6 gives volumes dv‡19 4 e  t  10 , and Table 5 gives volumes d4e  t  v2 17v‡80 d 10 e. Tables 4 and 6 overlap for v  15 and Tables 6 and 5 overlap for v  18, so it is clear that for v > 20 and v  1 mod 10 all possible values of t are obtained. It is straightforward to check that the result holds for the other congruence classes as well. (

References 1. Billington, E.J., Ho€man, D.G.: Trades and Graphs. Graphs Comb. (to appear) 2. Bryant, D.E.: On the volume of trades in triple systems. Australas. J. Comb. 15, 161±176 (1997) 3. Maenhaut, B.M.: The intersection problem for maximum pentagon packings. J. Comb. Math. Comb. Comput. 32, 65±78 (2000) 4. Maenhaut, B.M.: The intersection problem for group divisible pentagon systems. Bull. Inst. Comb. Appl. 24, 73±78 (1998) 5. Rosa, A.: On cyclic decompositions of the complete graph into polygons with an odd number of edges. Cas. Pestovni Mat. 91, 53±63 (1966) (in Slovak) 6. Rosa, A., ZnaÂm, SÏ.: Packing pentagons into complete graphs: how clumsy can you get? Discrete Math. 128, 305±316 (1994) Received: April 27, 1998 Final version received: February 15, 1999