Maximum Packing of <i>λ</i>-Fold Complete 3-Uniform Hypergraph with a Special Tetrahedron

Abstract

Let Kv(3)=(V,E) be the complete 3-uniform hypergraph, where the vertex set is V={x1,x2,⋯,xv}, in which the edge set E is of all triples. Let ST denote the special tetrahedron with four edges, where each edge contains three vertices of degree 2. In this paper, we consider the decomposition and packing of a complete 3-uniform hypergraph of an λ-fold special tetrahedron. Firstly, the necessary conditions for the existence of the λ-fold ST-decomposition are discussed in four distinct cases. Secondly, according to the recursive constructions, the required designs of small orders are found. For hypergraphs with large orders, they can be recursively generated using some designs of small orders. Then, it is proven that the above necessary conditions are sufficient. Finally, we prove that a maximum ST-packing of a complete 3-uniform hypergraph Kv(3) exists for all v≥6 and λ≥1.

Keywords

• complete 3-uniform hypergraph
• hypergraph decomposition
• packing design
• maximum packing
• special tetrahedron
• leave