Packings and Coverings of Various Complete Graphs with the 4-Cycle with a Pendant Edge

We consider the packings and coverings of complete graphs with isomorphic copies of the 4-cycle with a pendant edge. Necessary and sufficient conditions are given for such structures for (1) complete graphs , (2) complete bipartite graphs , and (3) complete graphs with a hole . In the last two cases, we address both restricted and unrestricted coverings. 1. Introduction, Motivation, and History A -decomposition of graph is a set of subgraphs of , , where for , for , and . The are called blocks of the decomposition. The concept of a graph decomposition lies in the general area of the design theory. We can relate a graph decomposition to an experimental design by considering the following hypothetical situation: “suppose you have a collection of samples and you wish to compare a property of the samples. However, the only way to compare the samples is to run them three at a time in a machine which performs the comparison. The machine cannot be calibrated from run to run and so to compare two samples, we must run them together in the machine. When can all of the samples be optimally compared to each other by running the machine times?” The solution to this question is equivalent to finding a -decomposition of , where each vertex of represents a sample, an edge joining two vertices represents a comparison of the two corresponding samples, and a copy of represents a run of the machine. A -decomposition of exists if and only if or 3 (mod？6), and such a structure is called a Steiner triple system [1]. In the event that a -decomposition of does not exist, we can still consider a set of isomorphic copies of graphs which “approximate” a decomposition. There are two approaches to this. We describe the two approaches in terms of the sample comparison analogy. In the first approach, we can try comparing as many of the samples as possible, without repetition of comparisons (it might be that running the machine is expensive). In the setting mentioned above, we could seek a collection of runs of the machine (represented by copies of ) which do not repeat pairs of samples run together (i.e., the copies of are edge disjoint), and which minimizes the number of pairs of samples which are omitted (i.e., the cardinality of the set of edges in which are in none of the copies of is made minimal). Such an experimental design is related to a maximal graph packing. A maximal -packing of a graph with isomorphic copies of a graph is a set , where and for all , for , , and is minimal. In particular, the machine analogy corresponds to a -packing of . Such designs are explored in [2].