Some Covering and Packing Problems for Mixed Triples

A mixed graph has both edges and directed edges (or “arcs”). A complete mixed graph on v vertices, denoted Mv, has, for every pair of vertices u and v, an edge {u,v}, an arc (u,v), and an arc (v,u). A decomposition of the complete mixed graph on v vertices into a partial orientation of a three-cycle with one edge and two arcs (of which there are three types) is a mixed triple system of order v. Necessary and sufficient conditions for the existence of a mixed triple system of order v are well known. In this work packings and coverings of the complete mixed graph with mixed triples are considered. Necessary conditions are given for each of the three relevant mixed triples, and these conditions are shown to be sufficient for two of the relevant mixed triples. For the third mixed triple, a conjecture is given concerning the sufficient conditions. Applications of triple systems in general are discussed, as well as possible applications of mixed graphs, mixed triple systems, and packings and coverings with mixed triples.