A Decomposition of a Complete Graph with a Hole

DOI: 10.4236/ojdm.2021.111001, PP. 1-12

Keywords: Graph Decomposition, Combinatorial Design, Complete Graph with a Hole

Full-Text   Cite this paper   Add to My Lib

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 of？using difference methods and 1-factors.

References

[1]	Bermond, J.C. and Schonheim, J. (1977) G-Decomposition of , Where G Has Four Vertices or Less. Discrete Mathematics, 54, 113-126.
[2]	Hoffman, D.G., Lindner, C.C., Sharry, M.J. and Street, A.P. (1996) Maximum Packing of with Copies of . Aequationes Mathematicae, 51, 247-269.
[3]	Stern, G. and Lenz, H. (1980) Steiner Triple Systems with Given Subspaces: Another Proof of the Doyen-Wilson Theorem. Bolletino dell Unione Matematica Italiana, 17, 109-114.

Full-Text