Perfect hexagon triple systems Original Research Article

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 3kKn. 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 3kKn with hexagon triples is a triple (X,C,L), 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 kKn with triangles. This paper gives a complete solution (modulo two possible exceptions) of the problem of constructing perfect maximum packings of 3kKn with hexagon triples.