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

Authors: Brandon Coker; Gary D. Coker; Robert Gardner; Yan Xia
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

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 graphsKv, (2) complete bipartite graphs Km,n, and (3) complete graphs with a hole K(v,w). In the last two cases, we address both restricted and unrestricted coverings.


---

## Body

## 1. Introduction, Motivation, and History

Ag-decomposition of graphG is a set of subgraphs of G, γ={g1,g2,…,gn}, where gi≅g for i∈{1,2,…,n}, E(gi)∩E(gj)=⌀ for i≠j, and ∪i=1nE(gi)=E(G). The gi 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 v 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 v samples be optimally compared to each other by running the machine (v2)/3 times?” The solution to this question is equivalent to finding a K3-decomposition of Kv, where each vertex of Kv represents a sample, an edge joining two vertices represents a comparison of the two corresponding samples, and a copy of K3 represents a run of the machine. A K3-decomposition of Kv exists if and only if v≡1 or 3 (mod 6), and such a structure is called a Steiner triple system [1].In the event that ag-decomposition of G does not exist, we can still consider a set of isomorphic copies of graphs g 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 K3) which do not repeat pairs of samples run together (i.e., the copies of K3 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 Kv which are in none of the copies of K3 is made minimal). Such an experimental design is related to a maximal graph packing. A maximalg-packing of a graph G with isomorphic copies of a graph g is a set {g1,g2,…,gn}, where gi≅g and V(gi)⊂V(G) for all i, E(gi)∩E(gj)=⌀ for i≠j, ∪i=1ngi⊂G, and |E(G)∖∪i=1nE(gi)| is minimal. In particular, the machine analogy corresponds to a K3-packing of Kv. Such designs are explored in [2]. Other packings of the complete graphs have also been studied, for example, 4-cycle-packings [3], K4-packings [4], and 6-cycle-packings [5, 6]. A second approach involves comparing all of the samples to each other, but with minimal repetitions of the compared samples (we might postulate that the machine must have three samples in it during each run to keep it balanced). This experimental design is related to a minimal graph covering. A minimalg-covering of a graph G with isomorphic copies of a graph g is a set {g1,g2,…,gn}, where gi≅g, V(gi)⊂V(G), E(gi)⊂E(G) for all i, G⊂∪i=1ngi, and |∪i=1nE(gi)∖E(G)| is minimal (when considering coverings, the graph ∪i=1ngi may not be simple and ∪i=1nE(gi) may be a multiset). The machine analogy in this case corresponds to a K3-covering of Kv. Such designs are explored in [7]. Coverings of Kv have also been explored, for example, for 4-cycles [2] and 6-cycles [8].In terms of graph decompositions, several studies have concentrated on theg-decompositions of complete graphs into copies of a given graph g with a small number of vertices [9–12]. In this paper, we go in a different direction and consider a single graph g, the 4-cycle with a pendant edge, and explore packings and coverings of several graphs related to the complete graph. We denote the 4-cycle with a pendant edge as H=[a,b,c,d;e], where V(H)={a,b,c,d,e} and E(H)={(a,b),(b,c),(c,d),(a,d),(a,e)}. See Figure 1. An H-decomposition of Kv exists if and only if v≡0 or 1 (mod 5), v≥10 [9]. An H-decomposition of the complete bipartite graph, Km,n, exists if and only if mn≡0 (mod 5), m≥5, and n≥2 [13]. Another graph related to the complete graph is the complete graph with a hole K(v,w). The complete graph on v vertices with a hole of size w is the graph with a vertex set V(K(v,w))=Vv-w∪Vw, where |Vv-w|=v-w and |Vw|=w, and edge set E(K(v,w))={(a,b)∣a,b∈V(K(v,w)),{a,b}⊄Vw}. Necessary and sufficient conditions for the decomposition of K(v,w) into m-cycles are known for m∈{3,4,5,6,7,8,10,12,14} [14–16]. There is an H-decomposition of K(v,w) if and only if |E(K(v,w))|≡0 (mod 5), v-w≥4, and (v,w)∉{(5,1),(6,1)} [13].Figure 1
We denote byH=[a,b,c,d;e] this graph.The graphK(v,w) relates to the experimental design story as follows. Suppose you have performed comparisons on a collection of w samples and then received an additional collection of samples (say, v-w new samples). You now wish to compare the v-w new samples to each other and to the original w samples. In the case of the machine described above, this would correspond to a K3 decomposition of K(v,w). In the event that a decomposition does not exist, we can explore the packings and coverings of K(v,w). With a maximal g-packing of G, we require that each copy of g is a subgraph of G. The definition given above for a maximal g-covering also involves the condition that each copy of g is a subgraph of G. Most studies of coverings have involved G=Kv, so the condition that the copies of g are subgraphs of G is trivially satisfied. But when G is not a complete graph, there is no obvious reason to impose the subgraph condition. Returning to the testing-of-samples story, we see no reason to disallow, for example, the testing (or retesting) of two samples in the hole of K(v,w). Therefore, we are motivated to refine the definition of a graph covering into two cases—one case in which the edges that are not in G are forbidden from use in the copies of g and a second case in which these edges are not forbidden. A minimal unrestrictedg-covering of a graph G with isomorphic copies of a graph g is a set {g1,g2,…,gn} where gi≅g, V(gi)⊂V(G), G⊂∪i=1ngi, and |∪i=1nE(gi)∖G| is minimal (the graph ∪i=1ngi may not be simple and ∪i=1nE(gi) may be a multiset). A minimal restrictedg-covering of a graph G with isomorphic copies of a graph g is a set {g1,g2,…,gn}, where gi≅g, V(gi)⊂V(G), E(gi)⊂E(G) for all i, G⊂∪i=1ngi, and |∪i=1nE(gi)∖G| is minimal. The distinction between restricted and unrestricted coverings was introduced in [17]. Notice that in the event that G is a complete graph, there is no distinction between a minimal restricted and minimal unrestricted covering.The purpose of this paper is to giveH-packings of Kv, Km,n, and K(v,w), as well as H-coverings of Kv, and restricted and unrestricted H-coverings of Km,n and K(v,w).


## 2. Packing and CoveringKv

In this section, when necessary, we assume that the vertex set ofKv is V(Kv)={0,1,2,…,v-1}. Since H has 5 vertices, we only consider v≥5.Theorem 1.
A maximalH-packing of Kv, v≥5, has leave L, where |E(L)|=|E(Kv)|(mod5), except when v∈{5,6} in which case |E(L)|=5.Proof.
Since|E(H)|=5, then it is necessary that in any H-packing of Kv with leave L, |E(L)|≡|E(Kv)| (mod 5). Therefore, such a packing with |E(L)|=|E(Kv)| (mod 5) would be maximal. If v∈{5,6}, then |E(Kv)|≡0 (mod 5), but there is not an H-decomposition of Kv [9]. So for v∈{5,6}, an H-packing of Kv with leave L, where |E(L)|=5 would be maximal.
Case
1. Suppose v=5. The set {[0,1,2,3;4]} is a maximal packing of K5 with leave L, where E(L)={(0,2),(1,3),(1,4),(2,4),(3,4)}, so |E(L)|=5.
Case
2. Suppose v=6. The set {[0,1,2,3;4],[1,3,4,5;4]} is a maximal packing of K6 with leave L, where E(L)={(0,2),(0,5),(2,5),(2,4),(3,5)}, so |E(L)|=5.
Case
3. Suppose v≡2 or 4 (mod 5), v≥9. Since |E(Kv)|≡1 (mod 5), |E(L)|=1 would be optimal. Now K(v,2) can be decomposed [13], so |E(L)|=1.
Case
4. Suppose v≡3 (mod 5), v≥8. Since |E(Kv)|≡3 (mod 5), |E(L)|=3 would be optimal. Now K(v,3) can be decomposed [13], so |E(L)|=3.In the following result (and throughout this paper), we refer to an equality of the forma=b (mod c). By this, we mean that a∈{0,1,2,…,c-1} and a≡b (mod c).Theorem 2.
A minimalH-covering of Kv, v≥5, has padding P, where |E(P)|=-|E(Kv)|(mod5), except when v∈{5,6} in which case |E(P)|=5.Proof.
Since|E(H)|=5, then it is necessary that in any H-covering of Kv with padding P, we have |E(Kn)|+|E(P)|≡0 (mod 5) or that |E(P)|≡-|E(Kv)| (mod 5). So if |E(P)|=-|E(Kv)| (mod 5), then the covering is minimal. If v∈{5,6}, then -|E(Kv)|≡0 (mod 5), but there is no H-decomposition of Kv [9]. So for v∈{5,6}, an H-covering of Kv with padding P, where |E(P)|=5 would be minimal.
Case
1. Suppose v=5. The set {[0,1,2,3;4],[1,2,0,4;3],[4,1,0,2;3]} is a minimal covering of K5 with padding P, where (P)={(0,1),(0,2),(0,4),(1,2),(1,4)}, so |E(P)|=5.
Case
2. Suppose v=6. The set {[0,1,2,3;4],[5,0,2,4;1],[5,3,4,1;2],[3,4,5,2;1]} is a minimal covering of K6 with padding P, where E(P)={(1,5),(2,3),(2,5),(3,4),(4,5)}, so |E(P)|=5.
Case
3. Suppose v≡2 or 4 (mod 5), v≥7. There is an H-decomposition of K(v,2) [13]. Take such a decomposition, along with another copy of H which includes the edge of the hole of K(v,2). This gives a covering of Kv with padding P, where |E(P)|=4=-|E(Kv)| (mod 5).
Case
4. Suppose v≡3 (mod 5), v≥8. An H-covering of K8 is given by {[0,1,2,7;3],[1,3,5,7;6], [4,5,6,3;7],[2,4,6,0;5],[1,4,0,5;2],[7,3,2,6;0]} with padding P, where E(P)={(0,7),(1,2)} and the covering is optimal. For v≥13, Kv=K(v,8)∪K8, K(v,8) can be decomposed [13], and K8 can be covered with padding P, where |E(P)|=2. Therefore, there is an optimal H-covering of Kv with padding P, where |E(P)|=2=-|E(Kv)| (mod 5).


## 3. Packing and Covering the Complete Bipartite Graph

In this section, we consider theH-packings and H-coverings of the complete bipartite graph Km,n. We assume the partite sets of Km,n are {00,10,…,(m-1)0} and {01,11,…,(n-1)1}.Theorem 3.
A maximalH-packing of Km,n has leave L, where(1)
|E(L)|=mn   if m=1 or n=1, or if m=n=2, or(2)
|E(L)|=|E(Km,n)|(mod5), otherwise.Proof.
First, ifm or n equals 1, then H is not a subgraph of Km,n, and the leave must have mn edges. Similarly, the leave of a packing of K2,2 has mn=4 edges. For m≥2 and n≥3, as in the proof of Theorem 1, an H-packing of Km,n with leave L, where |E(L)|=|E(Km,n)| (mod 5) would be maximal. Next, for m≥2 and n≥3 we observe that if there is a packing of Km,n with leave L, then there is a packing of Km+5i,n+5j with leave L for all i,j∈ℕ. This is because Km+5i,n+5j=Km,n∪Km,5j∪K5i,n∪K5i,5j, where the partite sets of Km+5i,n+5j are {00,10,…,(m-1+5i)0} and {01,11,…,(n-1+5j)1}, the partite sets of Km,n are {00,10,…,(m-1)0} and {01,11,…,(n-1)1}, the partite sets of Km,5j are {00,10,…,(m-1)0} and {n1,(n+1)1,…,(n-1+5j)1}, the partite sets of K5i,n are {m0,(m+1)0,…,(m-1+5i)0} and {01,11,…,(n-1)1}, and the partite sets of K5i,5j are {m0,(m+1)0,…,(m-1+5i)0} and {n1,(n+1)1,…,(n-1+5j)1}. There is an H-decomposition of Km,5j, K5i,n, and K5i,5j [13].
In Table1, the packings, combined with the decompositions of complete bipartite graphs mentioned above, yield the result.Table 1
(
m
,
n
) (mod 5)
K
m
,
n
Packing
Leave
(
1,1
)
K
6,6
{
[
0
0
,
0
1
,
1
0
,
1
1
;
2
1
]
,
[
0
0
,
5
1
,
1
0
,
4
1
;
3
1
]
,
[
2
0
,
0
1
,
3
0
,
1
1
;
2
1
]
,
{
(
5
0
,
3
1
)
}
[
2
0
,
4
1
,
3
0
,
5
1
;
3
1
]
,
[
4
0
,
0
1
,
5
0
,
1
1
;
2
1
]
,
[
4
0
,
4
1
,
5
0
,
5
1
;
3
1
],
[
2
1
,
1
0
,
3
1
,
3
0
;
5
0
]
}
(
1,2
)
K
6,2
{
[
0
1
,
0
0
,
1
1
,
1
0
;
2
0
]
,
[
1
1
,
5
0
,
0
1
,
4
0
;
3
0
]
}
{
(
2
0
,
1
1
)
,
(
3
0
,
0
1
)
}
(
1,3
)
K
6,3
{
[
3
0
,
0
1
,
2
0
,
1
1
;
2
1
]
,
[
1
0
,
0
1
,
0
0
,
1
1
;
2
1
]
,
[
5
0
,
0
1
,
4
0
,
1
1
;
2
1
]
}
{
(
0
0
,
2
1
)
,
(
2
0
,
2
1
)
,
(
4
0
,
2
1
)
}
(
1,4
)
K
6,4
{
[
0
0
,
0
1
,
1
0
,
1
1
;
2
1
]
,
[
3
1
,
2
0
,
2
1
,
3
0
;
1
0
]
,
{
(
2
0
,
0
1
)
,
(
2
0
,
1
1
)
,
[
2
1
,
4
0
,
1
1
,
5
0
;
1
0
]
,
[
3
1
,
4
0
,
0
1
,
5
0
;
0
0
]
}
(
3
0
,
0
1
)
,
(
3
0
,
1
1
)
}
(
2,2
)
K
2,2
⌀
{
(
0
0
,
0
1
)
,
(
0
0
,
1
1
)
,
(
1
0
,
0
1
)
,
(
1
0
,
1
1
)
}
(
2,3
)
K
3,2
{
[
1
1
,
1
0
,
0
1
,
0
0
;
2
0
]
}
{
(
2
0
,
0
1
)
}
(
2,4
)
K
4,2
{
[
1
1
,
1
0
,
0
1
,
0
0
;
2
0
]
}
{
(
2
0
,
0
1
)
,
(
3
0
,
0
1
)
,
(
3
0
,
1
1
)
}
(
3,3
)
K
3,3
{
[
1
1
,
1
0
,
0
1
,
0
0
;
2
0
]
}
{
(
0
0
,
2
1
)
,
(
1
0
,
2
1
)
,
(
2
0
,
0
1
)
,
(
2
0
,
2
1
)
}
(
3,4
)
K
4,3
{
[
0
0
,
0
1
,
1
0
,
1
1
;
2
1
]
,
[
2
0
,
3
1
,
1
0
,
2
1
;
1
1
]
}
{
(
0
0
,
3
1
)
,
(
2
0
,
0
1
)
}
(
4,4
)
K
4,4
{
[
1
0
,
1
1
,
0
0
,
0
1
;
2
1
]
,
[
3
0
,
1
1
,
2
0
,
0
1
;
2
1
]
,
[
3
1
,
2
0
,
2
1
,
0
0
;
3
0
]
}
{
(
1
0
,
3
1
)
}Theorem 4.
A minimal restrictedH-covering of Km,n, where neither m nor n equals 1 and m+n≥5, has padding P, where |E(P)|=-|E(Km,n)|(mod5).Proof.
ForK1,n, H is not a subgraph and so a restricted H-covering does not exist. Similar to the argument in Theorem 2, a H-covering of Km,n with padding P where |E(P)|=-|E(Km,n)| (mod 5) would be minimal. As in Theorem 3, for m≥2 and m≥3, if there is a restricted covering of Km,n with padding P, then there is a restricted covering of Km+5i,n+5j with padding P for all i,j∈ℕ.
In Table2, the coverings, combined with the decompositions of complete graphs mentioned in Theorem 3, yield the result.Table 2
(
m
,
n
) (mod 5)
K
m
,
n
Covering
Padding
(
1,1
)
K
6,6
{
[
3
1
,
0
0
,
0
1
,
1
0
;
5
0
]
}
{
(
0
0
,
3
1
)
,
(
0
0
,
0
1
)
,
(
1
0
,
0
1
)
,
(
1
0
,
3
1
)
}
(
1,2
)
K
6,2
{
[
0
1
,
2
0
,
1
1
,
1
0
;
3
0
]
}
{
(
1
0
,
0
1
)
,
(
1
0
,
1
1
)
,
(
2
0
,
0
1
)
}
(
1,3
)
K
6,3
{
[
2
1
,
0
0
,
1
1
,
2
0
;
4
0
]
}
{
(
0
0
,
1
1
)
,
(
2
0
,
1
1
)
}
(
1,4
)
K
6,4
{
[
2
0
,
0
1
,
3
0
,
1
1
;
2
1
]
}
{
(
2
0
,
2
1
)
}
(
2,2
)
K
7,2
{
[
0
1
,
0
0
,
1
1
,
1
0
;
6
0
]
,
[
1
1
,
2
0
,
0
1
,
3
0
;
6
0
]
,
[
1
1
,
5
0
,
0
1
,
4
0
;
0
0
]
}
{
(
0
0
,
1
1
)
}
(
2,3
)
K
3,2
{
[
0
1
,
1
0
,
1
1
,
0
0
;
2
0
]
}
{
(
0
0
,
0
1
)
,
(
0
0
,
1
1
)
,
(
1
0
,
0
1
)
,
(
1
0
,
1
1
)
}
(
2,4
)
K
4,2
{
[
0
1
,
3
0
,
1
1
,
0
0
;
2
0
]
}
{
(
0
0
,
0
1
)
,
(
0
0
,
1
1
)
}
(
3,3
)
K
3,3
{
[
2
1
,
2
0
,
0
1
,
1
0
;
0
0
]
}
{
(
1
0
,
0
1
)
}
(
3,4
)
K
4,3
{
[
0
1
,
0
0
,
3
1
,
2
0
;
1
0
]
}
{
(
0
0
,
0
1
)
,
(
1
0
,
0
1
)
,
(
2
0
,
3
1
)
}
(
4,4
)
K
4,4
{
[
3
1
,
0
0
,
0
1
,
3
0
;
1
0
]
}
{
(
0
0
,
3
1
)
,
(
0
0
,
0
1
)
,
(
3
0
,
0
1
)
,
(
3
0
,
3
1
)
}Theorem 5.
A minimal unrestrictedH-covering of Km,n has padding P where  (1)
whenm>1 and n>1, |E(P)|=-|E(Km,n)|(mod5),(2)
whenm=1, |E(P)|=(2/3)n for n≡0(mod3), |E(P)|=2(n+5)/3 for n≡1(mod3), |E(P)|=(2n+5)/3 for n≡2(mod3).Proof.
Form>1 and n>1, the necessary condition follows as in the proof of Theorem 4. In this case, sufficiency also follows from Theorem 4.
Whenm=1, a copy of H where V(H)⊂V(K1,n) has at most 3 edges in E(K1,n) and at least 2 edges in the padding. So in an H-covering of K1,n, there are at least ⌈n/3⌉ copies of H. Now ⌊n/3⌋ copies of H can have at most 3⌊n/3⌋ edges in E(K1,n) and at least 2⌊n/3⌋ edges in the padding. If n≡1 (mod 3), then to completely cover K1,n we must add one more copy of H which has at most 1 edge in E(K1,n) and at least 4 edges in the padding. If n≡2 (mod 3), then to completely cover K1,n we must add one more copy of H which has at most 2 edges in E(K1,n) and at least 3 edges in the padding. This yields the necessary conditions for m=1. We now establish sufficiency for m=1.
Case
1. Suppose m=1 and n≡0 (mod 3); n≥6. Consider the blocks {[00,01,31,11;21]}∪{[00,(3k)1,21,(3k+1)1;(3k+2)1]∣k=1,2,…,(n/3)-1}. This is a covering of Km,n with padding P={(01,31),(11,31)}∪{(21,(3k)1),(21,(3k+1)1)∣k=1,2,…,(n/3)-1}, where |E(P)|=(2/3)n.
Case
2. Suppose m=1 and n≡1 (mod 3); n≥4. From Case 1, there is a covering of K1,n-1, where the partite sets of K1,n-1 are {00}, and Vn∖{(n-1)1} with padding P1, where |E(P1)|=2(n-1)/3. This covering along with {[00,01,21,11;31]}, is an unrestricted covering of Km,n with padding P2=P1∪{(00,01),(01,21),(21,11),(00,11)} and so |E(P2)|=2(n+5)/3.
Case  3. Suppose m=1 and n≡2 (mod 3); n≥5. From Case 1, there is a covering of K1,n-2, where the partite sets of K1,n-2 are {00} and Vn∖{(n-2)1} with padding P1, where |E(P1)|=2(n-2)/3. This covering along with {[00,(n-1)1,01,(n-2)1;11]} is an unrestricted covering of Km,n with padding P2=P1∪{(01,(n-1)1),(01,(n-2)1),(00,11)}, and so |E(P2)|=(2n+5)/3.


## 4. Packing the Complete Graph with a Hole

In this section, we assume the vertex set ofK(v,w) is V(K(v,w))=Vv-w∪Vw as described in Section 1, where Vv-w={00,10,…,(v-w-1)0} and Vw={01,11,…,(w-1)1}.Theorem 6.
A maximalH-packing of K(v,w) has leave L, where |E(L)|=|E(K(v,w))|(mod5) and v-w≥2 is necessary.Proof.
Whenv=w+1, H is not a subgraph of K(v,w), and so, there is no packing. Therefore, v-w≥2 is necessary for the existence of a packing.
Case  1. If v-w=6, then K(v,w)=K6∪K6,w, where the vertex set of K6 is Vv-w and the partite sets of K6,w are Vv-w and Vw. There exists a packing K6,w with leave L2 such that |E(L2)|∈{1,2,3,4}. Without loss of generality, (00,01)∈E(L2). Take such a packing along with {[40,50,20,30;10],[00,30,10,50;20],[00,10,20,40;01]}. This yields a packing of K(v,w) with leave L={(30,50)}∪E(L2)∖{(00,01)}, so |E(L)|=|E(L2)|.
Case
2. Suppose v≡0 (mod 5) and w≡2 (mod 5). Then K(v,w)=Kv-w∪Kv-w,w, where V(Kv-w)=Vv-w and the partite sets of Kv-w,w are Vv-w and Vw. We have v-w≡3 (mod 5) and w≡2 (mod 5). There is a maximal packing of Kv-w, where v-w≡3 (mod 5) with |E(L1)|=3 by Theorem 1 and a maximal packing of Kv-w,w with |E(L2)|=1 by Theorem 3. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=4=|E(K(v,w))| (mod 5).
Case
3. Suppose v≡0 (mod 5) and w≡3 (mod 5) or v≡3 (mod 5) and w≡4 (mod 5). Then K(v,w)=Kv-w∪Kv-w,w as in Case 2, where v-w≡2 (mod 5) and w≡3 (mod 5) or v-w≡4 (mod 5) and w≡4 (mod 5). There is a maximal packing of Kv-w, where v-w≡2 (mod 5) or v-w≡4 (mod 5) with |E(L1)|=1 by Theorem 1, and there is a maximal packing of Kv-w,w with |E(L2)|=1 by Theorem 3. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=2=|E(K(v,w))| (mod 5).
Case
4. Suppose v≡0 (mod 5) and w≡4 (mod 5). When v-w≥11, K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡1 (mod 5) and w≡4 (mod 5). There is a maximal packing of Kv-w,w with |E(L2)|=4 by Theorem 3 and Kv-w, where v-w≡1 (mod 5) is decomposable [9]. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=4=|E(K(v,w))| (mod 5).
Case
5. Suppose v≡1 (mod 5) and w≡2 (mod 5) or v≡1 (mod 5) and w≡4 (mod 5). Then K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡4 (mod 5) and w≡2 (mod 5), or v-w≡2 (mod 5) and w≡4 (mod 5). There is a maximal packing of Kv-w, where v-w≡4 (mod 5) or v-w≡2 (mod 5) with |E(L1)|=1 by Theorem 1, and there is a maximal packing of Kv-w,w with |E(L2)|=3 by Theorem 3. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=4=|E(K(v,w))|(mod5).
Case
6. Suppose v≡1 (mod 5) and w≡3 (mod 5). Then K(v,w)=Kv-w+1∪Kv-w,w-1, where V(Kv-w+1)=Vv-w∪{w1} and the partite sets of Kv-w,w-1 are Vv-w∪{w1} and Vw∖{w1}. Then there is a maximal packing of Kv-w+1 with leave L1, where |E(L1)|=1 by Theorem 1, and there is a maximal packing of Kv-w,w-1 with leave L2, where |E(L2)|=1 by Theorem 3. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=2=|E(K(v,w))| (mod 5).
Case
7. Suppose v≡2 (mod 5) and w≡0 (mod 5) or v≡4 (mod 5), and w≡0 (mod 5). Then K(v,w)=Kv-w∪Kv-w,w where v-w≡2 (mod 5) and w≡0 (mod 5) or v-w≡4 (mod 5), and w≡0 (mod 5). There is a maximal packing of Kv-w, where v-w≡2 (mod 5) or v-w≡4 (mod 5) with |E(L1)|=1 by Theorem 1 and Kv-w,w is decomposable [13]. Therefore, there is a maximal packing of K(v,w) with leave L where |E(L)|=1=|E(K(v,w))| (mod 5).
Case
8. Suppose v≡2 (mod 5) and w≡1 (mod 5). Similar to Case 3, when v-w≥11, K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡1 (mod 5) and w≡1 (mod 5). There is a maximal packing of Kv-w,w with |E(L2)|=1 by Theorem 3 and Kv-w, where v-w≡1 (mod 5) is decomposable [9]. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=1=|E(K(v,w))| (mod 5).
Case
9. Suppose v≡2 (mod 5) and w≡3 (mod 5), or v≡3 (mod 5) and w≡1 (mod 5). Then K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡4 (mod 5), w≡3 (mod 5) or v-w≡2 (mod 5) and w≡1 (mod 5). There is a maximal packing of Kv-w, where v-w≡4 (mod 5) or v-w≡2 (mod 5) with |E(L1)|=1 by Theorem 1, and there is a maximal packing of Kv-w,w with |E(L2)|=2 by Theorem 3. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=3=|E(K(v,w))| (mod 5).
Case
10. Suppose v≡3 (mod 5) and w≡0 (mod 5). Then K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡3 (mod 5) and w≡0 (mod 5). There is a maximal packing of Kv-w, where v-w≡3 (mod 5) with |E(L1)|=3 by Theorem 1 and Kv-w,w is decomposable [13]. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=3=|E(K(v,w))| (mod 5).
Case
11. Suppose v≡3 (mod 5) and w≡2 (mod 5). Similar to Case 4, when v-w≥11, K(v,w)=Kv-w∪Kv-w,w, where v-w≡1 (mod 5) and w≡2 (mod 5). There is a maximal packing of Kv-w,w with |E(L2)|=2 by Theorem 3 and Kv-w where v-w≡1 (mod 5) is decomposable [9]. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=2=|E(K(v,w))| (mod 5).
Case
12. Suppose v≡4 (mod 5) and w≡1 (mod 5). As in Case 6, we have K(v,w)=Kv-w+1∪Kv-w,w-1. Then there is a maximal packing of Kv-w+1 with leave L1, where |E(L1)|=1 by Theorem 1 and Kv-w,w-1 is decomposable [13]. There is a maximal packing of K(v,w) with leave L, where |E(L)|=1=|E(K(v,w))| (mod 5).
Case
13. Suppose v≡4 (mod 5) and w≡3 (mod 5). Similar to Case 4, when v-w≥11, consider K(v,w)=Kv-w∪Kv-w,w, where v-w≡1 (mod 5) and w≡3 (mod 5). There is a maximal packing of Kv-w,w with |E(L2)|=3 by Theorem 3 and Kv-w, where v-w≡1 (mod 5) is decomposable [9]. Therefore, there is a maximal packing of K(v,w) with leave L, where |E(L)|=3=|E(K(v,w))| (mod 5).


## 5. Covering the Complete Graph with a Hole

As in the previous section, we assume the vertex set ofK(v,w) is V(K(v,w))=Vv-w∪Vw, where Vv-w={00,10,…,(v-w-1)0} and Vw={01,11,…,(w-1)1}.Theorem 7.
A minimal restrictedH-covering of K(v,w) has padding P, where |E(P)|=-|E(K(v,w))|(mod5), when v-w>2. No restricted H-covering of K(v,w) exists for v-w=2.Proof.
First, supposev-w=2. Consider the edge (00,10). If (00,10) is the pendant edge of an H, say H=[00,a,b,c;10], then 00,10, and b must be distinct vertices in Vv-w. But |Vv-w|=2, so this cannot happen. If (00,10) is an edge in the 4-cycle of some H, then there must be an edge in the 4-cycle of the form (a1,b1), a contradiction to the restricted covering. So, v-w>2 is necessary.
Similar to the argument in Theorem2, an H-covering of K(v,w) with padding P where |E(P)|=-|E(K(v,w)| (mod 5) would be minimal.
Case
1. Suppose v≡0 (mod 5) and w≡2 (mod 5). First, K(5,2) can be covered with {[00,01,20,10;11],[20,01,10,11;00]}, and this has a padding P with E(P)={(20,01)} and so |E(P)|=1. For general v and w, K(v,w)=K(5,2)∪Kv-w-3,3∪Kv-w,w-2, where the vertex set of K(5,2) is {00,10,20,01,11} and the hole is on vertex set {01,11}, the partite sets of Kv-w-3,3 are {30,40,…,(v-w-1)0} and {00,10,20}, and the partite sets of Kv-w,w-2 are Vv-w and {21,31,…,(w-1)1}. Now, Kv-w-3,3 and Kv-w,w-2 can be decomposed [13]. Taking these decompositions along with the above covering of K(5,2) yields a covering of K(v,w) with padding P, where E(P)={(20,01)}, and so |E(P)|=1=-|E(K(v,w))| (mod 5).
Case
2. Suppose v≡0 (mod 5) and w≡3 (mod 5) or v≡3 (mod 5), and w≡4 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, where V(Kv-w)=Vv-w and the partite sets of Kv-w,w are Vv-w and Vw and v-w≡2 (mod 5) and w≡3 (mod 5) or v-w≡4 (mod 5), and w≡4 (mod 5). There is a maximal packing of Kv-w where v-w≡2 (mod 5) or v-w≡4 (mod 5) with |E(L1)|=1 by Theorem 1. There is a maximal packing of Kv-w,w with |E(L2)|=1 by Theorem 3. Therefore, there is a minimal covering of K(v,w) with padding P, where |E(P)|=3=-|E(K(v,w))| (mod 5).
Case
3. Suppose v≡0 (mod 5), and w≡4 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡1 (mod 5), and w≡4 (mod 5). There is a minimal covering of Kv-w,w with padding P, where |E(P)|=1 by Theorem 4 and Kv-w, where v-w≡1 (mod 5) is decomposable [9]. Therefore, there is a minimal covering of K(v,w) with padding P, where |E(P)|=1=-|E(K(v,w))| (mod 5).
Case  4. Suppose v≡1 (mod 5) and w≡2 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡4 (mod 5) and w≡2 (mod 5). There is a maximal packing of Kv-w with leave L1, where |E(L1)|=1 by Theorem 1 and, without loss of generality, E(L1)={(00,20)}. There is a maximal packing of Kv-w,w with leave L2, where |E(L2)|=3 and E(L2)={(20,01),(01,30),(30,11)} by Theorem 3. These two packings combined with {[20,01,30,11;00]} yield a covering of K(v,w) with padding P, where E(P)={(20,11)}, so |E(P)|=1=-|E(K(v,w))| (mod 5).
Case
5. Suppose v≡1 (mod 5) and w≡4 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡2 (mod 5) and w≡4 (mod 5). There is a maximal packing of Kv-w with leave L1, where |E(L1)|=1 by Theorem 1 and, without loss of generality, E(L1)= {(01,21)}. There is a maximal packing of Kv-w,w with leave L2, where |E(L2)|=3 and E(L2)={(20,01),(01,30),(30,11)} by Theorem 3. These two packings combined with {[01,30,11,20;21]} yield a covering of K(v,w) with padding P, where E(P)={(20,11)}, so |E(P)|=1=-|E(K(v,w))| (mod 5).
Case
6. Suppose v≡1 (mod 5) and w≡3 (mod 5). Consider K(v,w)=Kv-w+1∪Kv-w,w-1, where V(Kv-w+1)=Vv-w∪{w1}, and the partite sets of Kv-w,w-1 are Vv-w∪{w1} and Vw∖{w1}. Then there is a maximal packing of Kv-w+1 with leave L1, where |E(L1)|=1 by Theorem 1, and there is a maximal packing of Kv-w,w-1 with leave L2, where |E(L2)|=1 by Theorem 3. Therefore, we can add an additional copy of H which includes the edges in L1 and L2. So, there is a minimal covering of K(v,w) with padding P, where |E(P)|=3=-|E(K(v,w))| (mod 5).
Case
7. Suppose v≡2 (mod 5) and w≡0 (mod 5), or v≡4 (mod 5) and w≡0 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡2 (mod 5), and w≡0 (mod 5) or v-w≡4 (mod 5), and w≡0 (mod 5). There is a minimal covering of Kv-w with padding P, where |E(P)|=4 by Theorem 2, and Kv-w,w is decomposable [13]. Therefore, there is a minimal covering of K(v,w) with padding P where |E(P)|=4=-|E(K(v,w))| (mod 5).
Case
8. Suppose v≡2 (mod 5) and w≡1 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡1 (mod 5) and w≡1 (mod 5). There is a minimal covering of Kv-w,w with padding P, where |E(P)|=4 by Theorem 4 and Kv-w, where v-w≡1 (mod 5) is decomposable [9]. Therefore, there is a minimal covering of K(v,w) with padding P, where |E(P)|=4=-|E(K(v,w))| (mod 5).
Case
9. Suppose v≡2 (mod 5) and w≡3 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡4 (mod 5) and w≡3 (mod 5). There is a maximal packing of Kv-w with leave L1, where |E(L1)|=1 by Theorem 1 and, without loss of generality, E(L1)= {(00,10)}. There is a maximal packing of Kv-w,w with leave L2, where |E(L2)|=2 and E(L2)={(00,31),(20,01)} by Theorem 3. These two packings combined with {[00,01,20,31;10]} yield a covering of K(v,w) with padding P, where E(P)={(00,01),(20,31)}, so |E(P)|=2=-|E(K(v,w))| (mod 5).
Case
10. Suppose v≡3 (mod 5) and w≡1 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡2 (mod 5) and w≡1 (mod 5). There is a maximal packing of Kv-w with leave L1, where |E(L1)|=1 by Theorem 1 and, without loss of generality, E(L1)= {(10,20)}. These is a maximal packing of Kv-w,w with leave L2, where |E(L2)|=2 and E(L2)={(20,11),(30,01)} by Theorem 3. There two packings combined with {[20,01,30,11;10]} yield a covering of K(v,w) with padding P, where E(P)={(20,01),(30,11)}, so |E(P)|=2=-|E(K(v,w))| (mod 5).
Case
11. Suppose v≡3 (mod 5) and w≡0 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡3 (mod 5) and w≡0 (mod 5). There is a minimal covering of Kv-w with padding P, where |E(P)|=2 by Theorem 2, and Kv-w,w is decomposable [13]. Therefore, there is a minimal covering of K(v,w) with padding P, where |E(P)|=2=-|E(K(v,w))| (mod 5).
Case
12. Suppose v≡3 (mod 5) and w≡2 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡1 (mod 5) and w≡2 (mod 5). There is a minimal covering of Kv-w,w with padding P, where |E(P)|=3 by Theorem 4 and Kv-w, where v-w≡1 (mod 5) is decomposable [9]. Therefore, there is a minimal covering of K(v,w) with padding P, where |E(P)|=3=-|E(K(v,w))| (mod 5).
Case
13. Suppose v≡4 (mod 5) and w≡1 (mod 5). As in Case 6, we have K(v,w)=Kv-w+1∪Kv-w,w-1. Then there is a minimal covering of Kv-w+1 with padding P, where |E(P)|=4 by Theorem 2 and Kv-w,w-1 is decomposable [13]. Therefore, there is a minimal covering of K(v,w) with padding P, where |E(P)|=4=-|E(K(v,w))| (mod 5).
Case
14. Suppose v≡4 (mod 5) and w≡3 (mod 5). Consider K(v,w)=Kv-w∪Kv-w,w, as in Case 2, where v-w≡1 (mod 5) and w≡3 (mod 5). There is a minimal covering of Kv-w,w with padding P, where |E(P)|=2 by Theorem 4 and Kv-w, where v-w≡1 (mod 5) is decomposable [9]. Therefore, there is a minimal covering of K(v,w) with padding P, where |E(P)|=2=-|E(K(v,w))| (mod 5).Theorem 8.
A minimal unrestrictedH-covering of K(v,w) has padding P where (1)
whenv-w>2, |E(P)|=-|E(K(v,w))|(mod5),(2)
whenv-w=1, |E(P)|=(2/3)w for w≡0(mod3), |E(P)|=2(w+5)/3 for w≡1(mod3), |E(P)|=(2w+5)/3 for w≡2(mod3),(3)
whenv-w=2, |E(P)|=5-ℓ, where ℓ=|E(K(v,w)|(mod5) for v≠6 and |E(P)|=6 for v=6.Proof.
Whenv-w>2, the necessary and sufficient conditions follow from Theorem 7. When v-w=1, K(v,w)≅K1,w and the necessary and sufficient conditions follow from Theorem 5.
Whenv-w=2, similar to the argument in Theorem 2, an H-covering of K(v,w) with padding P must satisfy |E(P)|≡-|E(K(v,w)| (mod 5). Since an H-decomposition of K(v,w) does not exist for w≡2 (mod 5) [13], the necessary conditions follow for v-w=2 and v≠6. For v=6, since |E(K(6,4))|=9, then an unrestricted H-covering of K(6,4) with padding P where |E(P)|=1 would be minimal. However, in such a covering, there are only two copies of H. Edge (00,10) cannot be the pendant edge of a copy of H in such a covering since this copy would have 2 edges in the padding. If edge (00,10) is in a copy of H and is not the pendant edge, then this copy of H must be of the form [00,10,a1,b1;c1] for some distinct a1,b1,c1∈{01,11,21,31}. However, the complement of this graph in K(6,4) is not a copy of H. Therefore, no such H-covering of K(6,4) exists, and a minimal unrestricted H-covering of K(6,4) with padding P, where |E(P)|=6 would be minimal. The set {[10,11,01,00;21],[00,21,10,31;11],[10,31,00,21;01]} is an unrestricted H-covering of K(6,4) with padding P where E(P)={(01,11),(10,21),(00,21),(10,21),(10,31),(00,31)}. So |E(P)|=6, and the covering is minimal.
Case  1. Suppose v-w=2 and w≡0 (mod 5); w≥5. Then K(v,w)=K(7,5)∪K2,w-5 where the vertex set of K(7,5) is {00,10,01,11,21,31,41} and the hole is on vertex set {01,11,21,31,41}, and the partite sets of K2,w-5 are {00,10} and {51,61,…,(w-1)1}. There is an H-decomposition of K2,w-5 [13], and the set {[10,11,01,00;21],[00,31,10,41;21],[11,01,10,21;00]} is an unrestricted H-covering of K(7,5) with padding P, where E(P)={(01,11),(01,11),(11,21),(10,21)} and |E(P)|=4. So, there is an unrestricted covering of K(v,w) with padding P, where |E(P)|=4=-|E(K(v,w))| (mod 5).
Case  2. Suppose v-w=2, w≡1 (mod 5); w≥6. Then, as in Case 1, K(v,w)=K(8,2)∪K2,w-6. There is an H-decomposition of K2,w-6 [13], and the set {[10,11,01,00;21],[10,31,00,41;01],[01,21,10,51;11]} is an unrestricted H-covering of K(8,6) with padding P, where E(P)={(01,11),(10,21)} and |E(P)|=2. So, there is an unrestricted covering of K(v,w) with padding P, where |E(P)|=2=-|E(K(v,w))| (mod 5).
Case
3. Suppose v-w=2 and w≡2 (mod 5); w≥7. Then, as in Case 1, K(v,w)=K(9,7)∪K2,w-7. There is an H-decomposition of K2,w-7 [13], and the set {[10,11,01,00;21],[10,31,00,41;01], [01,21,10,51;11],[00,51,10,61;01]} is an unrestricted H-covering of K(9,7) with padding P, where E(P)={(01,11),(10,21),(00,01),(00,51),(10,51)} and |E(P)|=5. So, there is an unrestricted covering of K(v,w) with padding P, where |E(P)|=5=5-ℓ, where ℓ=0=-|E(K(v,w))| (mod 5).
Case
4. Suppose v-w=2 and w≡3 (mod 5). Then, as in Case 1, K(v,w)=K(5,3)∪K2,w-3. There is an H-decomposition of K2,w-3 [13], and the set {[10,00,01,11;21],[01,21,00,11;10]} is an unrestricted H-covering of K(5,3) with padding P, where E(P)={(01,11),(01,11),(01,21)} and |E(P)|=3. So, there is an unrestricted covering of K(v,w) with padding Pn where |E(P)|=3=-|E(K(v,w))| (mod 5).
Case
5. Suppose v-w=2 and w≡4 (mod 5); w≥9. Then, as in Case 1, K(v,w)=K(11,9)∪K2,w-9. There is an H-decomposition of K2,w-9 [13], and the set {[10,11,01,00;21],[00,71,10,81;11], [00,51,10,61;21],[00,31,10,41;01]} is an unrestricted covering of K(11,9) with padding P, where E(P)={(01,11)} and |E(P)|=1. So, there is an unrestricted covering of K(v,w) with padding P, where |E(P)|=1=-|E(K(v,w))| (mod 5).


## 6. Conclusion

Motivated by experimental designs and comparisons of samples, we have given necessary and sufficient conditions for theH-packings and H-coverings of complete graphs, complete bipartite graphs, and complete graphs with a hole, where H is a 4-cycle with a pendant edge. For complete bipartite graphs and complete graphs with a hole, we have given both restricted and unrestricted coverings.



---

*Source: 236298-2013-09-26.xml*