Minimum covering for hexagon triple systems

Abstract

A hexagon triple is a graph consisting of three triangles of the form (a, x, b), (b, y, c), and (c, z, a), where a, b,k c, x, y, z are distinct. The triangle (a, b, c) is called the inside triangle and the triangles (a, x, b), (b, y, c), and (c, z, a) are called outside triangles. A 3k-fold hexagon triple system of order n is a pair (X, H), where H is an edge-disjoint collection of hexagon triples which partitions the edge set of 3kK(n) with vertex set X. Note that the outside triangles form a 3k-fold triple system. If the 3k-fold hexagon triple system (X, H) has the additional property that the inside triangles form a k-fold triple system, then (X, H) is said to be perfect. A covering of 3kK(n) with hexagon triples is a triple (X, H, P) such that: 1. 3kK(n) has vertex set X. 2. P is a subset of E(lambdaK(n)) with vertex set X for some lambda, and 3. H is an edge disjoint partition of E(3kK(n)) boolean OR P with hexagon triples. If P is as small as possible (X, H, P) is called a minimum covering of 3kK(n) with hexagon triples. If the inside triangles of the hexagon triples in H form a minimum covering of kK(n) with triangles, the covering is said to be perfect. A complete solution for the problem of constructing perfect 3k-fold hexagon triple system and perfect maximum packing of 3kK(n) with hexagon triples was given recently by the authors [2]. In this work, we give a complete solution of the problem of constructing perfect minimum covering of 3kK(n) with hexagon triples.