TITLE:
A Decomposition of a Complete Graph with a Hole
AUTHORS:
Roxanne Back, Alejandra Brewer Castano, Rachel Galindo, Jessica Finocchiaro
KEYWORDS:
Graph Decomposition, Combinatorial Design, Complete Graph with a Hole
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.11 No.1,
December
31,
2020
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 a hole and G be a complete graph on four vertices minus one edge, also referred to as a . A complete graph with a hole, , consists of a complete graph on d vertices, , and a set of independent vertices of size v, V, where each vertex in V is adjacent to each vertex in. When d is even, we give two constructions for the decomposition of a complete graph with a hole into copies of : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting d and v so that , we are able to resolve both of these cases for a subset ofusing difference methods and 1-factors.