A Decomposition of a Complete Graph with a Hole
Published in Open Journal of Discrete Mathematics, 2021
Abstract: In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with ahole and G be a complete graph on four vertices minus one edge, also referred to as a K_4-e. A complete graph with a hole, K_d + v, consists of acomplete graph ond vertices,K_d, and a set of independent vertices of size v, V, where each vertex in V is adjacent to each vertex in K_d. Whend is even,we give two constructions for the decomposition of a complete graph with ahole into copies of K_4 -e: the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting d and v so that v = 2(d-1) - 5a, we are able to resolve both of these cases for a subset of K_d + v using difference methods and 1-factors.