Maximum packing for perfect four-triple configurations

Abstract

The graph consisting of the four 3-cycles (triples) (x(1), x(2), x(8)), (x(2), x(3), x(4)), (x(4), x(5), x(6)), and (x(6), x(7), x(8)), where x(i)'s are distinct, is called a 4-cycle-triple block and the 4-cycle (x(2), x(4), x(6), x(8)) of the 4-cycle-triple block is called the interior (inside) 4-cycle. The graph consisting of the four 3-cycles (x(1), x(2), x(6)), (x(2), x(3), x(4)), (x(4), x(5), x(6)), and (x(6), x(7), x(8)), where x(i)'s are distinct, is called a kite-triple block and the kite (x(2), x(4), x(6))-x(8) (formed by a 3-cycle with a pendant edge) is called the interior kite. A decomposition of 3kK(n) into 4-cycle-triple blocks (or into kite-triple blocks) is said to be perfect if the interior 4-cycles (or kites) form a k-fold 4-cycle system (or kite system). A packing of 3kK(n) with 4-cycle-triples (or kite-triples) is a triple (X, B, L), where X is the vertex set of K, B is a collection of 4-cycle-triples (or kite-triples), and L is a collection of 3-cycles, such that B U L partitions the edge set of 3kK(n). If vertical bar L vertical bar is as small as possible, or equivalently vertical bar B vertical bar is as large as possible, then the packing (X, B, L) is called maximum. If the maximum packing (X, B, L) with 4-cycle-triples (or kite-triples) has the additional property that the interior 4-cycles (or kites) plus, a specified subgraph of the leave L form a maximum packing of kK(n) with 4-cycles (or kites), it is said to be perfect. This paper gives a complete solution to the problem of constructing perfect maximum packings of 3kK(n) with 4-cycle-triples and kite-triples, whenever n is the order of a 3k-fold triple system.