Perfect hexagon triple systems

Abstract

The graph consisting of the three 3-cycles (a, b, c), (c, d, e), and (e, f, a), where a, b, C, d, e, and f are distinct is called a hexagon triple. The 3-cycle (a,c,e) is called an "inside" 3-cycle; and the 3-cycles (a,b,c), (c,d,e), and (e,f,a) are called "outside" 3-cycles. A 3k-fold hexagon triple system of order n is a pair (X, C), where C is an edge disjoint collection of hexagon triples which partitions the edge set of 3kK(n). Note that the outside 3-cycles form a 3k-fold triple system. If the hexagon triple system has the additional property that the collection of inside 3-cycles (a, c, e) is a k-fold triple system it is said to be perfect. A perfect maximum packing of 3kK(n) with hexagon triples is a triple (X, CL), where C is a collection of edge disjoint hexagon triples and L is a collection of 3-cycles such that the insides of the hexagon triples plus the inside of the triangles in L form a maximum packing of kK(n) with triangles. This paper gives a complete solution (modulo two possible exceptions) of the problem of constructing perfect maximum packings of 3kK(n) with hexagon triples. (C) 2003 Elsevier B.V. All rights reserved.