3-Cycle Systems and Structure within Graph Decompositions
by
Joe Cha ee
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
August 2, 2014
Keywords: graph decomposition, neighborhood graph, quadratic leave, quadratic excess
Copyright 2014 by Joe Cha ee
Approved by
Chris Rodger, Chair, Don Logan Endowed Chair of Mathematics, Department of
Mathematics and Statistics; Associate Dean for Research and Graduate Studies, COSAM
Curt Lindner, Distinguished University Professor, Department of Mathematics and
Statistics
Peter Johnson, Professor, Department of Mathematics and Statistics
Abstract
An H-decomposition of a graph G is a partition of the edge set E(G) such that each
element of the partition induces a subgraph isomorphic to H. A packing or cover of Kn
(with triples) is an ordered pair (V;B) where V is an n-element set and B is a set of 3-element
subsets of V called blocks such that each 2-element subset of V appears in at most blocks
or at least blocks respectively. De ne E(B) =ffx;yg;fx;zg;fy;zgjfx;y;zg2Bg. The
leave of a packing is de ned to be the multiset of edges L = E( Kn) E(B) and the excess
or padding of a cover is de ned to be the multiset of edges P = E(B) E( Kn).
In this dissertation, necessary and su cient conditions for the existence of K3-
decompositions of K = 1Km_ 2 1Kn are found when 1 2, vastly generalizing the
results in the literature on K3-decompositions of K. In a speci c case of this problem
(namely when n = 2), it is useful to know for which simple quadratic subgraphs Q of Kn
(so Q cannot have 2-cycles) do there exist a K3-decomposition of Kn E(Q) (that is, a
packing of Kn with leave equal to E(Q)). A complete solution to this question is provided;
in addition to being useful in proving the rst result, it is also signi cant in that it extends
a classic result of Colbourn and Rosa who answered the same question when = 1.
In terms of the quadratic leave problem, the previous result, while short and simple,
has a gap in that it does not allow Q to have 2-cycles; the next result resolves this issue.
In a packing of 2Kn, the neighborhood graph of a vertex v is de ned to be the graph
induced by the multiset of edges ffa;bgjfa;b;vg2Bg. In a maximum packing of 2Kn,
the neighborhood graph of a vertex is a 2-regular graph on either n 1 or n 2 vertices.
Colbourn and Rosa provided a chararterization of which 2-regular graphs on n 1 or n 2
vertices can be the neighborhood graph of a vertex in some maximum packing of 2Kn when
n 0 or 1 (mod 3); this dissertation provides such a characterization in the case where
ii
n 2 (mod 3). This result along with the Colbourn and Rosa result (n 0 or 1 (mod 3))
is used to nd necessary and su cient conditions for a K3-decomposition of Kn E(Q)
where Q is any 2-regular graph on at most n vertices (so Q can have 2-cycles).
Finally, having already found necessary and su cient conditions for Q to be a 2-regular
leave of Kn, the problem of when a quadratic graph Q has edge set equal to the excess of a
cover of Kn is considered, and necessary and su cient conditions for a K3-decomposition
of Kn +E(Q) appear in the dissertation.
iii
Acknowledgments
I would like to thank Chris Rodger for his guidance, advice, and patience in working
with me.
iv
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Group Divisible Designs with Two Associate Classes and Quadratic Leaves of
Triple Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 The Case where K has no parts of size 2 . . . . . . . . . . . . . . . . . . . . 9
2.4 Quadratic Leaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 The case where m = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Neighborhoods in Maximum Packings of 2Kn and Quadratic Leaves of Triple
Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 Neighborhoods for 2K3x+2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 Quadratic Leaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4 Neighborhoods in Maximum Packings of 2Kn- A Second Version . . . . . . . . . 48
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
v
5 Quadratic Excesses or Paddings of Covers with Triples of Kn . . . . . . . . . . 60
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
vi
List of Figures
1.1 2K9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 1Km_ 2 1Kn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 C8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
vii
Chapter 1
Introduction
This dissertation will focus on two main problems. First, it will look at nding K3-
decompositions of a speci c family of graphs. Second, it will look at structure within packings
and covers of Kn. This introduction will rst give a number of very general de nitions in
Section 1.1, and then discuss some previously solved problems related to the results in this
dissertation in Section 1.2. The remaining chapters of this dissertation will be devoted to
proving the results I have obtained over the past ve years.
1.1 De nitions
A graph G is an ordered pair (V(G);E(G)) where V(G) is a set of elements called
vertices and E(G) is a multiset of unordered pair of vertices; the elements of E(G) are called
edges. WhenjV(G)j= n, for notational purposes, it is often convenient to let V(G) = Zn =
f0;1;:::;n 1g. A graph H is said to be a subgraph of a graph G if V(H) V(G) and
E(H) E(G). Two particular graphs that appear extensively in this dissertation are Kn,
which is the graph with n vertices in which every pair of vertices is joined by edges, and
1Kn_ 2 1Km, which is the graph in which the vertex set is partitioned into two parts M
and N wherejMj= m,jNj= n, and each pair of vertices is joined by 1 edges if they are in
the same part and is joined by 2 edges if they are in di erent parts. Two vertices u and v
are said to be adjacent if fu;vg2E(G). If u and v are adjacent, we write u v. The edge
fu;vgis said to be incident with the vertices u and v. The degree of a vertex v, denoted by
degG(v) = deg(v), is the number of edges incident with v. A k-cycle is a graph on k vertices
in which every vertex has degree 2. When a cycle C is considered as a subgraph of Kn, C
is said to be a Hamilton cycle ifjV(C)j=jV(Kn)j= n and C is said to be a near-Hamilton
1
cycle if jV(C)j= n 1. Figures 1.1,1.2, and 1.3 show the graphs 2K9, 1Km_ 2 1Kn; and
C8 respectively.
Figure 1.1: 2K9
?1
?2
?1
Figure 1.2: 1Km_ 2 1Kn Figure 1.3: C8
1.2 History
An H-decomposition of a graph G is a partition of the edge set E(G) such that each
element of the partition induces a subgraph isomorphic to H. In this dissertation, K3-
decompositions of graphs will be studied. Perhaps the most famous problem related to this
topic is nding necessary and su cient conditions for the existence of a K3-decomposition
of Kn. This problem was solved by Kirkman who showed in [19] that there exists a K3-
decomposition of Kn if and only if n 1 or 3 (mod 6). A natural extension of this problem
is to nd necessary and su cient conditions for the existence of a K3-decomposition of Kn.
This was solved by Hanani in [17] where it was shown that there exists a K3-decomposition
of Kn if and only if (n 1) is even, (n)(n 1) is divisible by 3, and n6= 2. A -fold
triple system is an ordered pair (V;B) where V is a n-element set and B is a set of 3-element
subsets of V called blocks such that each 2-element subset of V appears in blocks of B.
The blocks of B are also called triples. It is straightforward to see that a -fold triple system
is equivalent to a K3-decomposition of Kn.
2
With the necessary and su cient conditions for aK3-decomposition of Kn well-established,
there are a few natural directions to go, three of which are as follows:
1. What are necessary and su cient conditions for K3-decompositions of more general
graphs G?
2. What type of structure is present in K3-decompositions of Kn?
3. What are some natural notions of closeness to K3-decompositions of Kn, and when
can they be achieved?
These three questions are the main focus of the work in this dissertation. The rst ques-
tion is studied almost exclusively in Chapter 2; hence terminology speci c to that question
will appear in Chapter 2. The other questions are studied throughout the dissertation, and
hence the rest of this introduction will provide some de nitions and history related to the
last two questions.
The two most natural notions of closeness to a K3-decomposition of a graph G are
packings and coverings. For the purposes of this dissertation, a packing of a graph G is a
K3-decomposition of a subgraph H of G. In the case where G = Kn, a packing is sometimes
referred to as a partial ( -fold) triple system. If (V;B) is a (partial) triple system, de ne the
set of edges E(B) =ffx;yg;fx;zg;fy;zgjfx;y;zg2Bg. If (V;B) is a packing of Kn, then
the leave of the packing is de ned to be the multiset of edgesL = E( Kn)nE(B). It will cause
no confusion to also refer to the leave as being the subgraph induced by E( Kn)nE(B). In
particular, in the special case where L =ffa;bg;fa;bgg, L is expressed as the 2-cycle (a;b).
A vertex v is said to be in the leave if there is some edge in the leave that is incident with v. A
maximum packing is a packing such that among all packings the number of edges in its leave
is as small as possible (with respect to the graph G). On the other hand, a cover of a graph
G is a K3-decomposition of E(G) +P where P is a multiset of edges with underlying vertex
set V(G); in this dissertation, the topic of covers will only appear when G = Kn. If (V;B)
is a cover of Kn, de ne the set of edges E(B) =ffx;yg;fx;zg;fy;zgjfx;y;zg2Bg; the
3
excess or padding of the cover is de ned to be E(B)nE( Kn). Much like with leaves, it is
commonplace to look at the subgraph induced by the excess as opposed to the excess itself.
A minimum cover is a cover such that among all covers the number of edges in its excess is
as small as possible (with respect to the graph G).
Maximum packings and minimum covers have also been well studied, and the leaves of
all maximum packings of Kn and the excesses of all minimum covers of Kn have been
found; for instance, see [23]. In this dissertation, quadratic leaves and excesses will be
studied, but before getting to this problem, a related problem is considered.
In any partial triple system (V;B) of 2Kn, the neighborhood of a vertex v2V is the
graph induced by ffx;ygjfv;x;yg2Bg. If (V;B) is a maximum packing of 2Kn then the
neighborhood of each vertex is a 2-regular graph, also called a quadratic graph. It will cause
no confusion to also refer to the neighborhood as a set of cycles, each being a component
of the neighborhood. It is natural to ask for which quadratic graphs Q does there exist
a maximum packing (V;B) of 2Kn in which there exists a vertex v 2 V for which the
neighborhood of v is Q? Colbourn and Rosa came up with a large part of the answer in [9].
Theorem 1.1. [9] Suppose n 0 or 1 (mod 3). A 2-regular graph Q on n 1 vertices is
the neighborhood of a vertex in a 2-fold triple system on n vertices if and only if (n;Q) =2
f(6;C2[C3);(7;C3[C3)g.
One purpose of looking at this structure within 2-fold triple systems is that it helps
determine when 2-fold triple systems are not isomorphic. The dissertation extends this
result by proving an analogous result for n 2 (mod 3); this result appears in Chapter 3.
A simpler proof of this result that also subsumes the Colbourn and Rosa result appears in
Chapter 4.
This structure problem seems unrelated to the earlier topic of quadratic leaves and
excesses, but in fact, the topic of quadratic leaves is related to this structure problem. In
most cases, deleting a vertex in a maximum packing of 2Kn induces a packing of 2Kn 1
where the leave induces a quadratic graph. For quadratic excesses, there is perhaps not as
4
clear a motivation for studying them, but they do form a natural complement to quadratic
leaves and are hence discussed. In terms of quadratic leaves and excesses, the only explicit
results prior to this dissertation are for = 1 and are as follows:
Theorem 1.2. [11] Let Q be a 2-regular (quadratic) simple graph. There exists a K3-
decomposition of Kn E(Q) if and only if
1. n is odd,
2. jE(Kn)j jE(Q)j is divisible by 3, and
3. (n;Q) =2f(7;C3[C3);(9;C4[C5)g.
Theorem 1.3. [10] Let Q be a quadratic graph on n vertices. Then Q is the excess of a
cover of Kn if and only if
1. n is odd, and
2. jE(Q)j+jE(Kn)j 0 (mod 3).
In this dissertation, both of these results are extended to the case where > 1, although
it should be mentioned that part of the the quadratic leave result for when = 2 is a direct
consequence of Theorem 1.1. The result for quadratic leaves appears in Chapter 3 although
a partial result is mentioned in Chapter 2, while the result for quadratic excesses appears in
Chapter 5.
More speci c terminology will be introduced in the chapters as it is needed and the
dissertation now goes into the speci c results obtained over the last ve years.
5
Chapter 2
Group Divisible Designs with Two Associate Classes and Quadratic Leaves of Triple
Systems
2.1 Introduction
A group divisible design with two associate classes GDD(v;fg1;:::;gng;k; 1; 2) is an
ordered triple (V;G;B) where V is a v-set of symbols, G is a partition of V into n sets
(called groups) of sizes g1;:::;gn (possibly gi = gj for some i6= j so fg1;:::;gng is regarded
as a multiset), and B is a set of k-element subsets of V known as blocks, such that any two
distinct elements of V appear together in 1 blocks if they are in the same group and 2
blocks otherwise. In the special case where 1 = 0, 2 = 1, and k = 3, it is common to use
GDD(v;fg1;:::;gng) instead of GDD(v;fg1;:::;gng;3;0;1), and the design is called a group
divisible design.
Bose and Shimamoto were among the rst to classify such designs [2]. Fu, Rodger, and
Sarvate solved the existence of these designs for k = 3 when all groups have the same size
[15; 16]. A more general problem is to settle the existence question for k = 3 when the
groups have di erent sizes. In general this is a di cult problem, perhaps the most di cult
case being when there are exactly two groups. Pabhapote and Punnim solved the existence
in this case under the assumptions that 2 = 1 and that neither m nor n is 2 [25]. In this
chapter, their result is generalized with a di erent proof, completely solving the interesting
case where one of the two groups has size 2 (see Section 2:5) and also solving the case where
2 1 (see Section 2:3). These results are stated in the major theorem of the chapter (see
Theorem 2:2).
The problem can be approached in terms of an equivalent graph decomposition problem.
Let K = K(M;N; 1; 2) = 1Km_ 2 1Kn where jMj= m and jNj= n be a graph on the
6
vertex set M[N (M and N are called the parts) in which for each x;y2M[N with x6= y,
there exist 1 edges between x and y if x and y are in the same part and 2 edges between x
and y otherwise. An edge e =fx;ygis said to be pure if x and y lie in the same part and is
said to be mixed otherwise. A K3-decomposition of a graph G is an ordered pair (V(G);B)
where B is a partition of E(G) into sets, each of which induces a K3; in this chapter focus
will be placed on the case where G = K. Sometimes the copies of K3 are called triples and
the K3-decomposition of K is called a triple system of K. It is straightforward to see that
such a graph decomposition is equivalent to a GDD(v = m+n;fm;ng;3; 1; 2). To begin,
some obvious necessary conditions for the existence of this K3-decomposition of K are given.
Some of these conditions appear in other papers (such as [13]), but the proof is included here
for completeness.
Lemma 2.1. Let K = 1Km_ 2 1Kn with jMj= m and jNj= n. Assume that n = 2 only
if m = 2. The following conditions are necessary for the existence of a K3-decomposition of
K.
1. 3 divides 1( m2 + n2 ) + 2mn,
2. 2 divides 1(m 1) + 2n and 2 divides 1(n 1) + 2m,
3. 2 1( m2 + n2 ) 2mn,
4. if m = 2 then 1 2n, and
5. if m = 2 and n 2 then 1 = 2.
Proof. The rst and second conditions are necessary since the total number of edges must
be divisible by 3 and the degree of each vertex must be divisible by 2 respectively. The last
three conditions come from looking at the types of triples that can be chosen. Note that
every triple that contains a mixed edge must use precisely two mixed edges and a pure edge;
thus, the third condition is necessary. If m = 2 then each triple that uses a pure edge in M,
7
must also use two mixed edges; thus, the fourth condition is necessary. Finally, if m = 2 and
n is less than or equal to 2 then every triple must use a pure edge and two mixed edges, so
the fth condition is necessary.
Note that under the assumption that 1 2, the third necessary condition simpli es
to requiring that either m> 1 or n> 1.
It seems reasonable to conjecture that the conditions of Lemma 2.1 are su cient as
well. As noted earlier, this conjecture is proved in the case where m = 2 (see Section 2:5:
Theorem 2.14) and where 1 2 (see Section 2:3: Theorem 2:11). These proofs culminate
in the following result.
Theorem 2.2. Let K = 1Km_ 2 1Kn with m = 2 if n = 2. Let 1 2 if m6= 2. There
exists a K3-decomposition of K if and only if
1. 3 divides 1( m2 + n2 ) + 2mn,
2. 2 divides 1(m 1) + 2n and 2 divides 1(n 1) + 2m,
3. 2 1( m2 + n2 ) 2mn,
4. if m = 2 then 1 2n, and
5. if m = 2 and n 2 then 1 = 2.
Another valuable result in this chapter is the generalization of the classic result by
Colbourn and Rosa establishing necessary and su cient conditions for the existence of a
K3-decomposition of Kn E(Q) where Q is a 2-regular subgraph of Kn (see Theorem 2:12).
In Section 2:4, the generalization of this problem to Kn E(Q) is completely solved as
long as Q is simple, the necessary and su cient conditions depending on n;Q; and (see
Theorem 2.13). This result is then used in the proof of Lemma 2.18, thus helping to settle
the m = 2 case (see Theorem 2.14).
8
2.2 Terminology
The following terminology will be used throughout the chapter so it is de ned here
and complements the terminology given in Chapter 1. In Kv with vertex set Zv, de ne the
di erence of an edge joining two vertices i and j as d(i;j) = minfji jj;v j(i j)jg. For
each D f1;:::;v 1g, let Gv(D) be the graph with vertex set Zv and edge set consisting of
all edges of di erences in D. A di erence d is said to be good if vgcd(v;d) is even. A di erence
triple is a triple (a;b;c) of unique integers from the set f1;:::;v 1g, such that a+b = c or
a+b+c = v.
For i2f1;3;5g, let Fi(V(G)) be a graph with vertex set V(G) in which one vertex has
degree i and the rest have degree 1; these graphs are known as 1-factors, 3-poles (tripoles),
and 5-poles when i = 1;3; and 5 respectively.
A graph G is said to be evenly equitable if each vertex of G has even degree and for all
u;v2V(G), jd(u) d(v)j 2.
2.3 The Case where K has no parts of size 2
In this section, Theorem 2.2 is proved in the case where neither part has size 2 (see
Theorem 2.11). First some lemmas that are used in the proof of the theorem are given. The
rst addresses the well-known existence of maximum packings and minimum covers of Kv
with triples.
Theorem 2.3. [17, 23] Let 1 and v 3. Let P (or L) be any multigraph with the least
number of edges in which all vertices have degree congruent to (v 1) (mod 2) and with
jE(P)j+ v(v 1)2 0 (mod 3) (or v(v 1)2 jE(L)j 0 (mod 3) respectively). Then there
exists a K3-decomposition of Kv[E(P) (or Kv E(L) respectively).
A latin square L of order n is an n n array containing the symbols 0;1;:::;n 1 such
that each symbol appears exactly once in each row and each column. If L is a latin square,
9
we refer to the symbol in cell (a;b) as being a b. With the operation , the latin square is
referred to as a quasigroup; the quasigroup is denoted by (L; ). A quasigroup is said to be
idempotent if i i = i for every i2f0;1;:::;n 1g. The next lemma shows that quasigroups
can be constructed so that they are not commutative; this result will be used later to build
a triple system with a desired property.
Lemma 2.4. For all n 4, there exists an idempotent quasigroup of order n that is not
commutative. That is, for all n 4, there exists an idempotent quasigroup of order n in
which there exist a and b such that a b6= b a.
Proof. If n is even, then the result follows since in every idempotent quasigroup, each symbol
appears once on the main diagonal and hence appears o the main diagonal an odd number
of times. If n is odd, then de ne i i = i and (i+1) (j+2) = i j for 0 i;j 2 and let Q be a quadratic simple graph on at most n vertices.
Then Q is the leave of a packing of Kn if and only if:
1. Either is even or n is odd,
17
2. 3 divides jE( Kn)j jE(Q)j, and
3. (a) if = 1 and n = 7, then Q6= C3[C3,
(b) if = 1 and n = 9, then Q6= C4[C5, and
(c) if = 2 and n = 6, then Q6= C3[C3.
Proof. Suppose there exists a packing of Kn E(Q). Since each vertex of Q has even degree
and each vertex of Kn E(Q) must have even degree, each vertex of Kn must have even
degree so Condition 1 is necessary. Since the edges of Kn E(Q) are partitioned into sets
of size 3, Condition 2 is necessary.
Conditions 3(a) and 3(b) follow from Theorem 2:12. Condition 3(c) follows from the fact
that the only K3-decomposition of 2K6 (up to isomorphism) does not contain two disjoint
triples. Thus Condition 3 is necessary.
The proof of the su ciency is broken into several cases, based on the congruence classes
(mod 6) of n. Let n; ; and Q satisfy Conditions (1 3). Theorem 2:12 handles the case
where = 1, so assume > 1, Also, if jE(Q)j = 0, then by Theorem 2:3, there exists a
K3-decomposition of Kn, which proves the result. Hence, assume jE(Q)j 3. (Note that
no simple quadratic graph has 1 or 2 edges.)
If n 1 (mod 6) or n 3 (mod 6), Condition 2 is satis ed if and only if jQj 0 (mod
3). So, unless > 1 and (n;Q)2f(7;C3[C3);(9;C4[C5)g, the result follows by taking a
triple system of Kn E(Q) (see Theorem 2:12) together with a triple system of ( 1)Kn.
If > 1 and (n;Q) = (7;C3 [C3), then by Theorem 2:3, the vertices of two triple
systems of K7 with vertex set V can be named to contain the triples T1 = fa1;b1;c1g and
T2 =fa2;b2;c2grespectively, with T1\T2 =;; let B1 be the union of the triples of these triple
systems with Q = T1[T2 removed. If > 1 and (n;Q) = (9;C4[C5), then by Theorem
2:12, let (V;B01) be a triple system of K9 L1 where L1 is the nine-cycle (0;1;2;3;4;5;6;7;8)
and let (V;B001) be a triple system of K9 L2 where L2 is the six-cycle (0;3;6;4;8;7). Let
18
B1 = B01[B001[ff3;4;6g;f0;7;8gg. In either case, let (V;B2) be a triple system of ( 2)Kn.
Then (V;B1[B2) is the required decomposition.
Suppose n 5 (mod 6). Let 2f1;2;3g with (mod 3). By Theorem 2:3,
let (V;B1) be a K3-decomposition of ( )Kn. The three values are now considered
separately.
Suppose = 1. By Theorem 2:12, let (V;B2) be a K3-decomposition of Kn E(Q).
Suppose = 2. Let Q0 be formed from Q by replacing one cycle, c = (0;1;:::;x), of
length x+ 1 4 in Q with the cycle (1;:::;x) (by Condition 2,jE(Q)j jE(2Kn)j 2 (mod
3) and hence there must be a cycle of length at least 4). By Theorem 2:12, let (V;B02) be a
K3-decomposition of Kn E(Q0). Let (V;B002) be a K3-decomposition of Kn E(L) where
L is the 4-cycle (0;1;2;x). Let B2 = B02[B002 [ff1;2;xgg.
Finally, suppose = 3. By Condition 2, jV(G[Q])j n 2 so say 0 =2V(G[Q]). Let
c = (1;2;:::;x) be any cycle in Q and set c0 = (0;1;:::;x). Form Q0 from Q by replacing c
with c0. Also by Condition 2, jE(Q)j jE( Kn)j 0 (mod 3), so jE(Q0)j 1 jE(Kn)j
(mod 3). So by Theorem 2:12, let (V;B02) be a K3-decomposition of Kn E(Q0). By Theorem
2:3, let (V;B002) be a K3-decomposition of 2Kn E(L) where L consists of two copies of the
edge f1;xg. Let B2 = B02[B002 [ff0;1;xgg.
In each case, (V;B1[B2) is the required K3-decomposition.
Suppose n 4 (mod 6). First suppose (n;Q) 6= (10;C4[C5). By Condition 1, is
even. By Theorem 2:3, let (V;B1) be a K3-decomposition of ( 2)Kn. By Condition 2,
jV(G[Q])j n 1 so say 0 =2 V(G[Q]). Let G = G[V(Kn)nf0g]. By Theorem 2:12, let
(V ;B2) be a K3-decomposition of G E(Q). Let (V;B3) be a maximum packing of Kn
with leave L, a tripole, that includes the edges f0;1g;f1;2g; and f1;3g. Finally, let B4 =
ffx;y;0gjfx;ygis an independent edge in Lg[ff0;1;2g;f0;1;3gg. Then (V;[4i=1Bi) is the
required decomposition. Now suppose (n;Q) = (10;C4[C5). Let (Z10;B1) be a maximum
packing ofK10 with leave consisting of the edgesf0;1g;f0;8g;f0;9g;f2;3g;f4;5g;andf6;7g,
and let (Z10;B2) be a maximum packing with leave consisting of the edges f0;3g;f1;2g,
19
f5;6g;f4;8g;f7;8g;f8;9g. Then (V;B1[B2[ff0;8;9gg) is the required packing of 2K10
and can be combined with a K3-decomposition of ( 2)Kn to get the result for higher
values of .
Suppose n 2 (mod 6). Note that n6= 2. By Condition 1, is even. Let 2f2;4;6g
and set (mod 6). By Theorem 2:3, let (V;B1) be a K3-decomposition of ( )Kn.
Suppose = 2.
First suppose that Q contains a cycle of length at least 5. Let Q0 be formed from Q
by replacing a cycle, c = (0;1;:::;x), of length x + 1 5 in Q with the cycle c0 = (2;:::;x).
Note that 0 =2 V(G[Q0]). Let G = G[V(Kn)nf0g]. Since 2 (mod 6) (since = 2
in this subcase), then jE(Q)j jE( Kn)j 2 (mod 3), and hence jE(Q0)j 0 (mod 3).
Further, n 1 1 (mod 6) so by Theorem 2:12, let (V ;B2) be a K3-decomposition of
G E(Q0). Now let (V;B3) be a maximum packing of Kn with leave L, a 1-factor, with
f1;2g and f0;xg as edges in the 1-factor. Finally, let B4 consist of the following triples:
ffx;y;0gjfx;yg2 (Lnff1;2g;f0;xgg)g[ff0;2;xgg. Then (V;[4i=1Bi) is the required
decomposition.
Now suppose Q contains only three and four cycles. There are at least two four cycles;
name them (0;1;2;3) and (4;5;6;7). Let Q0 be formed from Q by removing these two
four cycles and replacing them with the six-cycle (2;3;4;5;6;7). Note that 0 =2V(G[Q0]).
Let G = G[V(Kn)nf0g]. By the above argument, let (V ;B2) be a K3-decomposition of
G E(Q0). Now let (V;B3) be a maximum packing of Kn with leave L, a 1-factor, with
f1;2g,f4;7gandf0;3gas edges in the 1-factor. Finally, let B4 consist of the following triples:
ffx;y;0gjfx;yg2 (Lnff1;2g;f0;3g;f4;7gg)g[ff0;2;7g;f0;3;4gg. Then (V;[4i=1Bi) is
the required decomposition.
Suppose = 4. By Condition 2, jV(G[Q])j n 1 so say 0 =2 V(G[Q]). Let c =
(1;2;:::;x) be any cycle in Q and set c0 = (0;1;:::;x). Form Q0 from Q by replacing c with
c0. By the above case for = 2, let (V;B2) be a packing of 2Kn with leave Q0. By Theorem
20
2:3, let (V;B3) be a maximum packing of 2Kn with leave the double edge f1;xg. Then
(V;[3i=1Bi[ff0;1;xgg) is the required decomposition.
Suppose = 6. By Condition 2, jV(G[Q])j n 2 so say 0 =2 V(G[Q]). Let c =
(1;2;:::;x) be any cycle in Q and set c0 = (0;1;:::;x). Form Q0 from Q by replacing c with
c0. By the above case for = 4, let (V;B2) be a packing of 4Kn with leave Q0. By Theorem
2:3, let (V;B3) be a maximum packing of 2Kn with leave the double edge f1;xg. Then
(V;[3i=1Bi[f0;1;xg) is the required decomposition.
Finally, suppose n 0 (mod 6). The proof is similar to the case where n 2 (mod
6) with = 2 unless Q consists entirely of 3-cycles. It is rst assumed that Q contains a
5-cycle, then two edges are removed from a cycle of length at least 5, a vertex is deleted, and
then the leave is modi ed just as in the case where n 2 (mod 6) with = 2. If there are
no ve cycles, but at least one four cycle, then there are necessarily three four cycles since
jE(Q)j 0 (mod 3). Take two of the four cycles and then proceed in the same manner as
in the case where n 2 (mod 6) with = 2. Finally, if there are only 3-cycles, note that
n 12 (by assumption) and take a K3-decomposition of Kn that contains a parallel class
(n3 disjoint triples; take the Bx from Lemma 2:7 for example).
2.5 The case where m = 2
A proof of Theorem 2:2 in the case where m = 2 is given in this section. The proof
relies on results which follow it, but is worth reading rst before all the details potentially
cloud the idea.
Theorem 2.14. Let m = 2. Let 1; 2, and n be positive integers. Then there exists a
K3-decomposition of 1Kn_ 2 1K2 if and only if
1. 3 divides 1( m2 + n2 ) + 2mn,
2. 2 divides 1(m 1) + 2n and 2 divides 1(n 1) + 2m,
3. 2 1( m2 + n2 ) 2mn,
21
4. 1 2n, and
5. if n 2 then 1 = 2.
Proof. The necessity of Conditions (1 5) has been shown in Lemma 2:1, so the su ciency
is now proved. Let M =fm0;m1g.
For both n = 1 and n = 2, Condition 5 requires 1 = 2. If n = 1, then the su ciency
follows from taking 2 copies of a triple system on 3 vertices. If n = 2, then Condition 2
implies that 1 is even. Thus, the su ciency follows from taking 12 copies of a 2-fold triple
system of 2K4.
Suppose n 3. The following three steps are taken, although they are dependent upon
lemmas provided afterwards.
Step 1: Since m = 2, the number of mixed edges incident with each vertex of N is
even. Together with Condition 2, this implies that each vertex in 1Kn has even degree. Let
(N;B1) be a K3-decomposition of 1Kn E(L) where L is a subgraph of Kn such that:
(a) jE(L)j= 2n 1,
(b) the subgraph induced by E(L) is connected, and
(c) each vertex of L has even degree less than or equal to 2 2.
The existence of L is shown in Lemma 2:18, but at least it is noted here that 2n 1 0
by Condition 3.
Step 2: Since the subgraph of K induced by E(L), G = K[E(L)], is connected (by (b))
and since all vertices in G have even degree (by (c)), there exists an Euler circuit E of G.
Alternately color the edges of E with colors 0 and 1. By Condition 2, 2n 1 is even, so E
has even length, so for each vertex w in G, the number of edges in G incident with w colored
0 equals the number colored 1. Let B2 = ffmi;w;ugjfw;ug2E(L) is colored i;i2Z2g.
Then for each i2Z2 and each n2N, the number of triples containing the pair fmi;ng is
dG(n)
2 .
22
Step 3: By (c), 2 dG(n)2 is a nonnegative integer for each n2N. So let B3 be the
multiset of triples formed as follows: for each n2N, let B3 contain 2 dG(n)2 copies of the
triple fm0;m1;ng.
By (a), Pn2N( 2 dG(n)2 ) = n 2 jE(L)j = 1, so 1 triples in B3 contain the pair
fm0;m1g. Therefore (M[N;[3i=1Bi) is the required decomposition.
So the result form = 2 is proved provided that it can be shown that theK3-decomposition
of 1Kn E(L) in Step 1 actually exists. Conditions 3 and 1 imply that the number of edges
in 1Kn E(L) is nonnegative and divisible by 3 respectively. It is now show how the K3-
decomposition from Step 1 can be achieved. However, before showing the existence of L, a
powerful result due to Simpson is given along with a corollary that will frequently be used
in showing the existence of L.
A Langford sequence of order n and defect d with n>d is a sequence L = (l1;l2;:::;l2n)
of 2n integers satisfying the conditions
(a) for every k2fd;d+ 1;:::;d+n 1g, there exist exactly two elements li;lj2L such that
li = lj = k, and
(b) if li = lj = k, then ji jj= k.
A hooked Langford sequence of order n and defect d with n > d is a sequence L =
(l1;l2;:::;l2n;l2n+1) of 2n integers satisfying the conditions
(a) l2n = 0
(b) for every k2fd;d + 1;:::;d + n 1g, there exist exactly two elements li;lj 2Lnfl2ng
such that li = lj = k, and
(c) if li = lj = k, then ji jj= k.
Theorem 2.15. [29]
1. A Langford sequence of order n and defect d exists if and only if
23
(a) n 2d 1 and
(b) n 0;1 (mod 4) and d is odd, or n 0;3 (mod 4) and d is even.
2. A hooked Langford sequence of order n and defect d exists if and only if
(a) n(n 2d+ 1) + 2 0 and
(b) n 2;3 (mod 4) and d is odd, or n 1;2 (mod 4) and d is even.
Corollary 2.16. Let n 3, w d + 3n, 0 n, and D1 fd + i j i 2 Zng with
jD1j= n . If there exists a Langford sequence or a hooked Langford sequence of order n
and defect d, then there exists D fd+iji2Z3ng with jDj= 3 and D1\D =; such that
there exists a set of triples B0 such that B =fb+jjb2B0;j2Zwg is a K3-decomposition
of Gw(D).
The triples in B0 are said to generate the K3-decomposition of Gw(D).
Proof. Let L = (l1;:::;l2n) or (l1;:::;l2n 1;0;l2n+1). Let B0 =ff0;i+n;j+ngjli = lj;li =2D0g
so that the triplef0;i+n;j +ngcontains edges of di erences n+i, j +i and d(i;j). Then
(Zw;B) is the required decomposition.
The following useful result will also be used in the proof of Lemma 2:18.
Theorem 2.17. [27] For n6= 2 there exists an equitable partial triple system containing v
triples for any 1 v (n; ) where
(n; ) =
8>
>>>
<
>>>
>:
bn3b (n 1)2 cc 1 if n 2 (mod 6) and = 4 (mod 6)
if n 5 (mod 6) and = 1 or 4 (mod 6)
bn3b (n 1)2 cc otherwise
The following lemma shows the existence of the decomposition described in Step 1 of
the proof of the main theorem of this section.
24
Lemma 2.18. Let m = 2 and suppose the following ve conditions hold:
1. 3 divides 1( m2 + n2 ) + 2mn,
2. 2 divides 1(m 1) + 2n and 2 divides 1(n 1) + 2m,
3. 2 1( m2 + n2 ) 2mn,
4. 1 2n, and
5. if n 2 then 1 = 2.
Then there exists a subgraph L of 1Kn with 2n 1 edges which is evenly equitable and
connected for which there exists a K3-decomposition of 1Kn E(L).
Proof. This lemma is proved in several cases. The vertex set of Kn will be Zn. First small
values of are considered before a general construction is provided. For the small cases,
Corollary 2:16 is consistently used.
Case 1: First, suppose 1 = 1. Note that L being evenly equitable and having 2n 1
edges is equivalent to requiring that every vertex in the leave have degree 2 2 except for a
single vertex which has degree 2 2 2; the exceptional vertex in the following constructions
will be vertex 0;1 or 2. Conditions 1 and 2 imply that n 1;5 (mod 6) and 2 1 (mod
6). It can be assumed that 2 > 1 since otherwise, the problem simpli es to simply looking
for a K3-decomposition of K6x+3 or K6x+1 which are both known to exist. Set 2 = 6z + 1
with z 1.
Suppose n 5 (mod 6). It can be assumed that n 17, since if n = 5 or 11, then
Condition 3 in conjunction with the fact that 2 1 (mod 6) implies that 2 = 1. For
n = 6k + 5 17, using edges of only di erences 1 and 2, let B1 = ff3i;3i + 1;3i + 2gj
0 i 2k + 1g, where addition is done (mod 6k + 5). Note that every symbol ex-
cept 0 appears in exactly one triple; 0 appears in two. If n = 17;23;29; or 35, let B02 =
ff0;3;8g;f0;4;10gg;ff0;3;9g;f0;4;11g;f0;5;13gg;ff0;4;14g;f0;7;16g;f0;3;8gf0;6;17gg;
25
or ff0;3;17g;f0;5;11g;f0;7;20g;f0;9;19g;f0;4;12gg respectively. Otherwise, by Corol-
lary 2:16, let B02 be a set of triples that generate a K3-decomposition of Gn(D) where
D =f3;4;:::;3k + 2g.
First note that k 2z, since by Condition 3, 2 +n(n 1) 2 2n = (12z+ 2)n, so since
n 1 is an integer and n> 2 it follows that n 1 12z + 2, so 6k+ 4 12z + 2 so k 2z.
Therefore, B2 can be formed by removing 2z 2 triples from B02, one of which contains the
di erence 4. So jB2j=jB02j 2z = k 2z 0. Then (Zn;B1[fb + jjj2Zn;b2B2g) is
the required K3-decomposition, since if v2Znnf0g, then dL(v) = (n 1) 2 6(k 2z) =
12z + 2 = 2 2 and dL(0) = (n 1) 4 6(k 2z) = 2 2 2. So L is evenly equitable with
2n 1 edges. Since all edges of di erence 4 are in L, L is connected.
Suppose n 1 (mod 6). It can be assumed that n 19, since if n = 7 or 13, then
Condition 3 in conjunction with the fact that 2 1 (mod 6) implies that 2 = 1. For
n = 6k + 1 19, using edges of only di erences 1, 2, and 3, form triples as follows. Let
2f1;4;7g with n (mod 9). Let n = 9j + and B01 =ff9i;9i+ 1;9i+ 3g;f9i+ 1;9i+
2;9i+4g;f9i+2;9i+3;9i+5g;f9i+4;9i+6;9i+7g;f9i+5;9i+7;9i+8g;f9i+6;9i+8;9i+9gj
0 i j 1g. Note that symbols 0 and 9j appear in one triple; symbols 1;:::;9j 1 appear
in two.
If = 1, then let B001 =ff9j;0;2gg. If = 4, then let B001 =ff9j;9j + 1;9j + 3g;f9j +
1;9j + 2;0g;f9j + 2;9j + 3;1gg. If = 7, then let B001 =ff9j;9j + 1;9j + 3g;f9j + 1;9j +
2;9j + 4g;f9j + 2;9j + 3;9j + 5g;f9j + 4;9j + 6;0g;f9j + 5;9j + 6;1gg.
In any case, set B1 = B01[B001. Note that every symbol except y appears in exactly two
triples; y appears in three triples, where y = 2 if = 1 and y = 1 if = 4 or 7.
If n 25, then there exists a set B02 of triples that generates a K3-decomposition of
Gn(D =f4;5;:::;3kg). This follows from Corollary 2.16 if n 49. If n = 25;31;37; or 43, let
B02 =ff0;4;13g;f0;7;15g;f0;5;11gg;ff0;5;11g;f0;4;17g;f0;9;19g;f0;7;15gg;ff0;4;17g;
f0;7;18g;f0;6;14g;f0;5;15g;f0;9;21gg; or ff0;11;23g;f0;7;22g;f0;4;13g;f0;6;16g;
f0;5;19g;f0;8;25gg respectively.
26
Now use B02 to de ne B2. First note that k 1 2z, since by Condition 3, 2+n(n 1)
2 2n = (12z + 2)n, so since n 1 is an integer and n> 2 it follows that n 1 12z + 2, so
6k 12z+ 2, so k 1 2z. Therefore if n 25, then B2 can be formed by removing 2z 2
triples from B02, one of which contains the di erence 4. SojB2j=jB02j 2z = (k 1) 2z 0.
If n = 19, then 2 2f1;7g so it can be assumed that 2 = 7; this means that k 1 = 2z
so de ne B2 = ; in this case. Then for n 19, (Zn;B1[fb + j jj 2Zn;b2B2g) is the
required K3-decomposition, since if v2Znnfyg, then dL(v) = (n 1) 4 6((k 1) 2z) =
12z + 2 = 2 2 and dL(y) = (n 1) 6 6((k 1) 2z) = 2 2 2. So L is evenly equitable
with 2n 1 edges. Since all edges of di erence 4 are in L, L is connected.
Case 2: Now suppose 1 = 2. Then n 1;2;4; or 5 (mod 6). If 2 = 2, the result
follows from Theorem 2:3, so assume 2 > 2. Note that L being evenly equitable and having
2n 1 edges is equivalent to requiring that every vertex in the leave have degree 2 2 except
for two vertices each of which has degree 2 2 2.
Suppose n 1 or 5 (mod 6). Conditions 1 and 2 imply that 2 2 (mod 6). It can be
assumed that n 11 since if n = 5 or 7, then Condition 3 in conjunction with the fact that
2 2 (mod 6) implies that 2 = 2.
First supposen 17. By Case 1, there exists aK3-decomposition (Zn;B1) ofKn E(L1)
where L1 is a subgraph of Kn with ( 2 1)n ( 1 1) edges which is evenly equitable and
connected. By Theorem 2:12, there exists a K3-decomposition (Zn;B2) of Kn E(L2)
where L2 is a subgraph of Kn consisting of a n 1 cycle such that the vertex not in the
cycle has maximum degree in L1. Then (Zn;B1[B2) is the required decomposition with
L = G[E(L1)[E(L2)].
Suppose n = 11 or 13. Condition 3 implies that 2 = 2 or 8, so it can be assumed that
2 = 8. Forn = 11, letB =ff3i+j;3i+1+j;3i+2+jgj0 i 3;0 j 1g. Then (Zn;B)
is the required K3-decomposition, since if v2Znnf0;1g, then dL(v) = 2(10) 4 = 16 = 2 2
and dL(0) = dL(1) = 2(10) 6 = 2 2 2. So L is evenly equitable with 2n 1 edges.
Since all edges of di erence 4 are in L, L is connected. For n = 13, let B =ff0 +j;1 +j;3 +
27
jg;f1+j;2+j;4+jg;f2+j;3+j;5+jg;f4+j;6+j;7+jg;f5+j;7+j;8+jg;f6+j;8+j;9+
jg;f9+j;10+j;12+jg;f10+j;11+j;0+jg;f11+j;12+j;1+jgj0 j 1g. Then (Zn;B)
is the required K3-decomposition, since if v2Znnf1;2g, then dL(v) = 2(12) 8 = 16 = 2 2
and dL(1) = dL(2) = 2(12) 10 = 2 2 2. So L is evenly equitable with 2n 1 edges.
Since all edges of di erence 4 are in L, L is connected.
Now assume n 2 or 4 (mod 6). In this case, the half-di erence is present and used
only once. Instead of thinking of the di erences as 1;2;:::;n2;1;2;:::;n2 1, it is useful to
think of them as 1;2;:::;n 1 since, for instance, the di erence 1 can be thought of as a
di erence n 1. In both cases, by Condition 1, 2 2 (mod 3), so let 2 = 3z + 2.
Suppose n 2 (mod 6) with n> 2, and let n = 6k+ 2. Although, it seems unnecessary
at this point, 2 = 2 is allowed for cases where n 2 (mod 6) (see Cases 4 and 5 for the
use of this result). Using only di erences 1;2; and n 1 = 1, let B1 = ffi;i + 1;i + 2gj
0 i n 1;i 0;1 (mod 3)g. Then each vertex has degree 4 from the triples in B1
except 0 and 1 which have degree 6. Now assume n 20. Consider the di erences in
D0 = f3;4;:::;n 2g. Then jD0j 1 (mod 3). Let v = n 2 or n 3 if n 53 0;1
(mod 4) or 2;3 (mod 4) respectively. By Corollary 2:16, there exists a set of triples B02
that generates a K3-decomposition of Gn(D = D0nfvg). Note that 2k 1 z, since by
Condition 3, 4 + 2n(n 1) 2 2n = (6z + 4)n, so since n 1 is an integer and n > 2,
(n 1) (3z + 2), so 6k + 1 3z + 2, so 2k 1 z. Therefore, B2 can be formed
by removing z 0 triples from B02; if z 1, choose one that contains the di erence 3.
So jB2j = jB02j z = 2k 1 z 0. For n = 8, by Condition 3, 2 = 2 or 5. If
2 = 2, let B2 = ff0;2;5gg, and if 2 = 5 and let B2 = ;. For n = 14, by Condition
3, 2 = 2;5;8; or 11. If 2 = 2, let B2 = ff0;2;6g;f0;3;6g;f0;4;9gg. If 2 = 5, let
B2 = ff0;4;9g;f0;6;13gg. If 2 = 8, let B2 = ff0;4;9gg. If 2 = 11, let B2 = ;. Then
for n 8, (Zn;B1 [fb + j j j 2 Zn;b 2 B2g) is the required K3-decomposition, since
if v 2 Znnf0;1g, then dL(v) = (2n 2) 4 6((2k 1) z) = 6z + 4 = 2 2 and
dL(0) = dL(1) = (2n 2) 6 6((2k 1) z) = 2 2 2. So L is evenly equitable with
28
2n 1 edges. So it remains to show that L is connected. If 2 5 or if n 20 and
( 2;v)2(z;n 3), then since all edges of di erence 3 are in L, L is connected. For n 8,
the edges of di erence 1;2; and n 1 not used in B1 form n 23 vertex-disjoint 3-cycles, namely
L0 =f(i;i+ 1;i+ 2)ji 2 (mod 3);2 i n 3g. If n 20 and ( 2;v) = (2;n 2), then
since Gn(fn 2g) has two components (induced by odd and even vertices), L is connected
since it also contains (2;3;4) 2 L0. If n 2f8;14g, then L is formed from L0 by adding
E(Gn(fn2g)), so is easily seen to be connected.
Suppose n 4 (mod 6) and let n = 6k+4. If n 10, then using only di erences 1 and 2,
let B1 =ffi;i+1;i+2gj0 i n 4;i 0 (mod 3)g[ffn 2;n 1;0gg. Then each vertex
has degree 2 from the triples in B1 except vertices 0 and n 2 which have degree 4. Now
further assume n 22. Consider the di erences in D0 =f3;4;:::;n 1g. ThenjD0j 1 (mod
3). Let v = n 1 or n 2 if n 43 0;1 (mod 4) or 2;3 (mod 4) respectively. By Corollary
2:16, there exists a set of triples B02 that generates a K3-decomposition of Gn(D = D0nfvg).
Note that 2k z, since by Condition 3, 4 + 2n(n 1) 2 2n = (6z + 4)n, so since n 1
is an integer and n > 2, (n 1) (3z + 2), so 6k + 3 3z + 2, so 2k z. Therefore, B2
can be formed by removing z 1 triples from B02, one of which contains the di erence 3. So
jB2j=jB02j z = 2k z 0. For n = 10, by Condition 3, 2 = 2;5; or 8 so assume 2 = 5 or
8. If 2 = 5, let B2 =ff0;4;9gg, and if 2 = 8, let B2 =;. For n = 16, 2 = 2;5;8;11 or 14,
so assume 2 2f5;8;11;14g. If 2 = 5, let B2 =ff0;4;15g;f0;6;13g;f0;5;14gg. If 2 = 8,
let B2 = ff0;4;15g;f0;6;13gg. If 2 = 11, let B2 = ff0;4;15gg. If 2 = 14, let B2 = ;.
Then for n 10, (Zn;B1 [fb + j j j 2 Zn;b 2 B2g) is the required K3-decomposition,
since if v 2 Znnf0;n 2g, then dL(v) = (2n 2) 2 6(2k z) = 6z + 4 = 2 2 and
dL(0) = dL(n 2) = (2n 2) 4 6(2k z) = 2 2 2. So L is evenly equitable with
2n 1 edges. Since all edges of di erence 3 are in L, L is connected.
Finally, if n = 4, Condition 3 implies 2 = 2 so the result follows from Theorem 2:3.
29
Before proceeding to the general case, because of the limitations of Theorem 2:13, three
more special cases need to be handled, namely where 1 = 3 and n 5 (mod 6) and the two
cases where n 2 (mod 6) and 1 = 4 or 6.
Case 3: Suppose 1 = 3 and n 5 (mod 6). Conditions 1 and 2 imply that 2 3
(mod 6). First suppose n 11. By Case 2, there exists a K3-decomposition (Zn;B1) of
2Kn E(L1) where L1 is a subgraph of 2Kn with ( 2 1)n ( 1 1) edges which is evenly
equitable and connected. By Theorem 2:12, there exists a K3-decomposition (Zn;B2) of
Kn E(L2) where L2 is a subgraph of Kn consisting of an n 1 cycle; name the vertices
so that the vertex not in the cycle has maximum degree in L1. Then (Zn;B1[B2) is the
required decomposition with L = G[E(L1)[E(L2)]. Now suppose n = 5. Then Condition
3 in conjunction with the fact that 2 3 (mod 6) implies 2 = 3 so the result follows by
Theorem 2:3.
Case 4: Suppose 1 = 4 and n 2 (mod 6) with n > 2. Conditions 1 and 2 imply
that 2 1 (mod 3). By Case 2, there exist K3-decompositions (Zn;B1) and (Zn;B2) of
2Kn E(L1) and 2Kn E(L2) respectively where L1 is a subgraph of 2Kn with ( 2
2)n ( 1 2) edges which is evenly equitable and connected, and L2 is a subgraph of
2Kn with 2n 2 edges which is evenly equitable and connected. Name the vertices so that
G[E(L1)[E(L2)] is also evenly equitable. Then (Zn;B1[B2) is the required decomposition
with L = G[E(L1)[E(L2)].
Case 5: Suppose 1 = 6 and n 2 (mod 6) with n> 2. Conditions 1 and 2 imply that
2 0 (mod 3). By Cases 4 and 2, there exist K3-decompositions (Zn;B1) and (Zn;B2)
of 4Kn E(L1) and 2Kn E(L2) respectively where L1 is a subgraph of 4Kn with ( 2
2)n ( 1 2) edges which is evenly equitable and connected, and L2 is a subgraph of
2Kn with 2n 2 edges which is evenly equitable and connected. Name the vertices so that
G[E(L1)[E(L2)] is also evenly equitable. Then (Zn;B1[B2) is the required decomposition
with L = G[E(L1)[E(L2)].
30
To this point, the theorem is proved if 1 2f1;2g and if ( 1;n)2f(3;5 (mod 6));(4;2
(mod 6));(6;2 (mod 6))g. So now consider the remaining cases. A two-step approach is
taken in each of three cases, making use of Theorems 2:13 and 2:17.
Case 1: Suppose n 0;1;3; or 4 (mod 6). Let 0 2f1;2g with 0 n (mod 2).
Set = 1 0. Since either n or n 1 is divisible by 3 in this case, 1n(n 1)2 0 (mod
3). Also, 1n(n 1)2 ( 2n 1) = 1(1 + n(n 1)2 ) 2n = 1(m(m 1)2 + n(n 1)2 ) 2n
1(m(m 1)2 + n(n 1)2 ) + 2 2n (mod 3) 0 (mod 3) where the last step follows from Condition
1. Therefore, 2n 1 is divisible by 3 . By Condition 2, 2n 1 is even. Since n 0;1;3
or 4 (mod 6), 0n(n 1)2 is divisible by 3.
First, suppose 2n 1 n. By Theorem 2:13, there exists a packing (V;B1) of 0Kn
with leave a cycle on 2n 1 vertices. By Condition 1 and by de nition, both 1 and 0
respectively are even when n is even; hence is even when n is even. Since n 0;1 (mod
3) and is even when n is even, by Theorem 2:3, there exists a K3-decomposition (V;B2)
of Kn. Then (V;B1[B2) is the required packing.
Now suppose 2n 1 > n. By Theorem 2:13, let (V;B1) be a packing of 0Kn with
leave a cycle on = n vertices when n 0 (mod 3) and = n 1 vertices when n 1 (mod
3). Again is even if n is even so b (n 1)2 c = (n 1)2 . Further, since in this case either
n or n 1 is divisible by 3, bn3 (n 1)2 c = n3 (n 1)2 . So by Theorem 2:17, there exists an
evenly equitable partial triple system (V;B2) of Kn with
n(n 1)
2 ( 2n 1 )
3 triples; this is
an integral number of triples since each of n(n 1)2 , 2n 1, and is divisible by 3. Finally,
if n 1 (mod 3), then name the symbols in (V;B2) so that the vertex left out of the n 1
cycle gets maximum degree in the leave of (V;B2). Then (V;B1[B2) is the required packing
since jE(L)j= + ( n(n 1)2 3(
n(n 1)
2 ( 2n 1 )
3 )) = 2n 1 and L is easily seen to be
evenly equitable and connected.
Case 2: Suppose n 5 (mod 6) and 1 > 3. Let 02f1;2;3g with 0 1 (mod 3).
Let = 1 0. By the same argument as when n 0 or 1 (mod 3), Condition 1 implies
31
that 1n(n 1)2 ( 2n 1) is divisible by 3. Since 1 0 (mod 3), 0n(n 1)2 ( 2n 1) is
also divisible by 3.
First suppose that 2n 1 n. By Theorem 2:13, there exists a packing (V;B1) of
0Kn with leave a cycle on 2n 1 vertices. Since 0 (mod 3), by Theorem 2:3, there
exists a K3-decomposition (V;B2) of Kn. Then (V;B1[B2) is the required packing.
Now suppose 2n 1 > n. Since n 5 (mod 6), mn = 2n 1 (mod 3) and
m(m 1)
2 +
n(n 1)
2 2 (mod 3); hence, by Condition 1, 1 2 (mod 3). Since n 2 (mod 3)
in this case, and since 1 2 (mod 3), 2n 2 1 (mod 3) so 2n 1 1 (mod 3). Also,
since n(n 1)2 1 (mod 3), 0n(n 1)2 0 (mod 3). By Theorem 2:13, there exists a packing
(V;B1) of 0Kn with leave a cycle on = n 1;n; or n 2 vertices when 0 = 1;2 or 3
respectively. In this case, (n 1) is even and is divisible by 3, sobn3b (n 1)2 cc= n3 (n 1)2 .
So by Theorem 2:17, there exists an equitable partial triple system (V;B2) of Kn with
n(n 1)2 ( 2n 1 )
3 triples; this is an integral number of triples since
is divisible by 3 and
2n 1 1 0 (mod 3). Finally, if = n 1 orn 2, then name the symbols of (V;B2)
so that each vertex not in the n 1 or n 2 cycle gets no smaller degree in the leave of (V;B2)
than any vertex in the cycle. Then (V;B1[B2) is the required packing, since L is clearly
evenly equitable and connected andjE(L)j= +( n(n 1)2 3(
n(n 1)
2 ( 2n 1 )
3 )) = 2n 1.
Case 3: Finally, suppose n 2 (mod 6). By Condition 2, 1 is even, so it can be
assumed 1 > 6 (since all smaller cases were handled previously). Recall that n > 2. Let
02f2;4;6gwith 0 1 (mod 6). Set = 1 0. By the same argument as when n 0
or 1 (mod 3), Condition 1 implies that 1n(n 1)2 ( 2n 1) is divisible by 3. Since 1 0
(mod 3), 0n(n 1)2 ( 2n 1) is also divisible by 3.
First suppose that 2n 1 n. By Theorem 2:13, there exists a packing (V;B1) of
0Kn with leave a cycle on 2n 1 vertices. Since 0 (mod 6), by Theorem 2:3, there
exists a K3-decomposition (V;B2) of Kn. Then (V;B1[B2) is the required packing.
Suppose 2n 1 >n. Since n 2 (mod 6), mn = 2n 1 (mod 3) and m(m 1)2 +n(n 1)2
2 (mod 3); hence, by Condition 1, 1 2 (mod 3). Since n 2 (mod 3) in this case, and
32
since 1 2 (mod 3), 2n 2 1 (mod 3) so 2n 1 1 (mod 3). Also, since n(n 1)2 1
(mod 3), 0n(n 1)2 0 (mod 3). By Theorem 2:13, there exists a packing (V;B1) of 0Kn
with leave a cycle on = n;n 1; or n 2 vertices when 0 = 2;4 or 6 respectively. In this
case, is even and divisible by 3, so bn3b (n 1)2 cc = n3 (n 1)2 . So by Theorem 2:17, there
exists an equitable partial triple system (V;B2) of Kn with
n(n 1)
2 ( 2n 1 )
3 triples; this
is an integral number of triples since is divisible by 3 and 2n 1 1 0 (mod
3). Finally, if = n 1 or n 2, then name the symbols of (V;B2) so that each vertex not
in the n 1 or n 2 cycle gets no smaller degree in the leave of (V;B2) than any vertex in
the cycle. Then (V;B1[B2) is the required packing, since L is clearly evenly equitable and
connected and jE(L)j= + ( n(n 1)2 3(
n(n 1)
2 ( 2n 1 )
3 )) = 2n 1.
33
Chapter 3
Neighborhoods in Maximum Packings of 2Kn and Quadratic Leaves of Triple Systems
3.1 Introduction
In this chapter, the quadratic leave problem is considered again, this time with the focus
of allowing 2-cycles in the leave. To do this, a characterization of the possible neighborhood
graphs in maximum packings of 2Kn is given which in turn will be used to solve the quadratic
leave problem. As mentioned in the introduction, in [9], Colbourn and Rosa characterized
the possible neighborhood graphs in a 2-fold triple system on n vertices when n 0 or 1
(mod 3). (A 2-fold triple system is equivalent to a maximum packing in these two cases.) In
this chapter, a characterization of the possible neighborhood graphs of vertices in a maximum
packing of 2Kn for n 2 (mod 3) is given (see Theorem 3.9). When n 2 (mod 3) the leave
of a maximum packing (V;B) of 2Kn is the 2-cycle (a;b) for some a;b2V (with a6= b); see
Lemma 3.2. So in this case an additional interesting aspect of nding the neighborhood of
a vertex v in a maximum packing of 2Kn arises; the neighborhood is a 2-regular graph on
n 2 vertices if v2fa;bg and is a 2-regular graph on n 1 vertices otherwise. The proof
technique in this chapter builds on modern observations recently made independently in two
papers [3, 22] concerning the existence of leaves of partial hamilton cycle decompositions of
Kn.
Bryant, Horsley, and Maenhaut have some results which relate to Theorem 3.10. In
[4], they show that Kn can be decomposed into 2-regular subgraphs of orders m1;:::;mt
provided that n is odd, 3 mi n for 1 i t, and Pmi = n2 . Note that specifying
m1;m2;:::;mj (j < t) to be the lengths of the cycles described in Theorem 3.10 is not
su cient to force the 2-regular subgraphs to be cycles, nor to force the cycles in the quadratic
graph to be vertex disjoint. In [6], Bryant and Horsley extend their rst result by showing
34
that Kn can be decomposed into cycles of orders m1;:::;mt provided that n is odd, 3
mi n for 1 i t, and Pmi = n2 whenever n is su ciently large. Note that Theorem
3.10 cannot be obtained from this result in the special case where = 1 and n is large
enough since the cycles in the quadratic graph are not forced to be vertex disjoint.
Maximal cycle systems have also been of interest from another perspective. Rather
than study the structure of the leave, several papers have considered its size, addressing the
spectrum question of nding the set S of integers for which there exists a partial k-cycle
system with leave of size l for each l2S. Cycles of length 3 and hamilton cycles have been
of particular interest (see for instance [12, 8, 28]).
For any multiset D with elements chosen from f1;2;:::;n 1g, let Gn(fDg) be the
multigraph with vertex set Zn and edge multiset ffv;v + dgj d 2 D;v 2 Zng reducing
sums modulo n. Note that with this de nition Gn(fdg) = Gn(fn dg) and is a 2-regular
graph regardless of the value of d (if d = n2 then each component is a 2-cycle). The edges in
Gn(fdg) are said to have di erence d. This de nition is slightly non-standard since edges are
allowed to have di erence d> n2 , but this approach is very useful when decomposing 2Kn.
Iffa;b;cgis a triple on the vertex set Zn then de nefa;b;cg+j =fa+j;b+j;c+jg,
reducing sums modulo n. Similarly, if (a0;a1;:::;an) is a cycle on the vertex set Zn then
de ne (a0;a1;:::;an) +j = (a0 +j;a1 +j;:::;an +j), reducing sums modulo n.
Throughout the chapter, and n are assumed to be positive integers.
3.2 Preliminary Results
To start, a well-known result on quasigroups is given.
Lemma 3.1. [27] There exists an idempotent quasigroup of order n for all n6= 2.
The following is a speci c case of well-known results on packings of Kn, and is su cient
for the purposes of this chapter.
35
Lemma 3.2. [14] Suppose 1 and n6= 2. There exists a K3-decomposition of Kn if and
only if is divisible by
1. 2 if n 0 or 4 (mod 6),
2. 3 if n 5 (mod 6), and
3. 6 if n 2 (mod 6).
Furthermore, there exists a maximum packing of Kn with leave L where:
1. L is a 4-cycle if = 4 and n 2 (mod 3) or = 1 and n 5 (mod 6), and
2. L is a 2-cycle if = 2 and n 2 (mod 3).
The next result is a neat way to be able to deal with the many possibilities for Q.
Lemma 3.3. For any quadratic multigraph Q on n vertices, there exists a subgraph of
Gn(f1;1;2g) which is isomorphic to Q.
Proof. For each l with 2 l n, de ne the cycle c(l) of length l in Gn(f1;1;2g) as follows.
If l = 2 then let c(l) = (0;1). If l = 2x> 2 then let c(l) = (0;2;4;6;:::;2x 2;2x 1;2x
3;2x 5;:::;1). Finally, if l = 2x 1 then let c(l) = (0;2;:::;2x 2;2x 3;2x 5;:::;1).
Suppose that Q is the disjoint union of t cycles of lengths l1;:::;lt (possibly li = 2). For
1 i t let si = Pij=1lj, and let ci = c(li) + si 1, de ning s0 = 0. Then Sti=1ci is a
subgraph of Gn(f1;1;2g) and is isomorphic to Q.
The following result was proved by Petersen.
Lemma 3.4. [26] Let H be any 2k-regular multigraph. There exists a 2-factorization of H.
In constructing maximum packings, it will always be rst assumed that the desired
neighborhood contains a small cycle, the size of which will depend upon the current case.
The following lemma is a well-known approach that will allow for the extension of these
constructions to cases where the prescribed small cycle is not present by combining two
cycles in the neighborhood of a vertex v into a single cycle.
36
Lemma 3.5. Let (V;S) be a partial 2-fold triple system, and let v2V. Suppose that fa;bg
andfc;egare edges in disjoint cycles in the neighborhood of v, and further suppose that there
is some w2V with w6= v such that ffa;c;wg;fb;e;wgg S. Then there exists a partial
2-fold triple system (V;S0) such that
1. E(S) = E(S0),
2. the neighborhood of v in S0 is obtained from the neighborhood of v in S by replacing
one copy of the edges fa;bg and fc;eg with one copy of the edges fa;cg and fb;eg.
Proof. De ne S0 = (Snffv;a;bg;fv;c;eg;fw;a;cg;fw;b;egg)
[ffv;a;cg;fv;b;eg;fw;a;bg;fw;c;egg.
The next lemma settles cases that will be used in Section 3 for the general construction,
and includes a proof of Theorem 3:9 when n2f5;8g. When n2f4;6g, the results follow
from the results of Colbourn and Rosa but are included here for completeness.
Lemma 3.6. Let S =f(4;C3);(6;C5);(5;C3);(5;C4);(8;C3[C3);(8;C2[C4);(8;C2[C2[
C2);(8;C6);(8;C4[C3);(8;C2[C5);(8;C2[C2[C3);(8;C7)g. For each (n;Q)2S, there
exists a maximum packing of 2Kn such that the neighborhood of some vertex is Q.
Proof. Let the vertex set of Kn be V = fa;bg[Zn 2. In each case, a maximum packing
is formed with leave the 2-cycle (a;b) if n2f5;8g and the empty leave if n2f4;6g. All
addition in the following is de ned modulo n 2. In each case, the set of blocks de ned
produce a maximum packing of 2Kn.
Let n = 4. De ne B = ffa;b;0g;fa;b;1g;fa;0;1g;fb;0;1gg. Then the neighborhood
of a is C3.
Let n = 6. De ne B =ffa;b;0g;fa;b;1g;fa;0;2g;fa;1;3g;fa;2;3g;fb;0;3g;fb;1;2g;
fb;2;3g;f0;1;2g;f0;1;3gg. Then the neighborhood of a is C5.
Let n = 5. De ne B =ffj;i;i + 1gjj2fa;bg;0 i 2g. Then the neighborhood of
a is C3 and the neighborhood of 0 is C4.
37
Let n = 8. De ne B1 = ffi;i + 1;i + 3g;fa;i;i + 2g;fb;i;i + 1gj i 2 Z6g, B2 =
ffi;i+ 1;i+ 2g;fa;i;i+ 3g;fb;i;i+ 2gji2Z6g, B3 =ff0;2;4g;f0;2;5g;f0;3;5g;f1;2;4g;
f1;3;4g;f1;3;5g;fb;0;3g, fb;0;4g;fb;1;2g;fb;1;5g;fb;2;3g;fb;4;5g;fa;0;1g;fa;0;1g;
fa;2;3g;fa;3;4g;fa;4;5g;fa;2;5gg, andB4 =ffa;0;1g;fa;0;1g;f0;2;3g;f0;2;3g;f0;4;5g;
f0;4;bg;f0;5;bg, fa;2;4g;fa;2;5g;fa;3;4g;fa;3;5g;f1;2;4g;f1;2;bg;f1;3;5g;f1;3;bg;
f1;4;5g;f2;5;bg;f3;4;bgg. In B1, the neighborhood of a is C3[C3 and of b is C6. In B2, the
neighborhood of a is C2[C2[C2. In B3, the neighborhood of a is C2[C4, of 0 is C2[C5,
and of 2 is C7. In B4, the neighborhood of 0 is C2[C2[C3. Finally, using an approach
similar to Lemma 3.5, the neighborhood of 0 in (B4nff0;1;ag;f0;2;3gfa;2;5g;f1;3;5gg)[
ffa;0;2g;f0;1;3g;fa;1;5g;f2;3;5gg is C4[C3.
Before proceeding to the main theorem of this chapter, the powerful result on Langford
sequences that was proved over a series of papers is given again (see for example [29]).
A Langford sequence of order m 1 and defect 1 is a sequence L = (l1;l2;:::;l2m)
of 2m positive integers satisfying the conditions
(a) for every k2f ; + 1;:::; + m 1g, there exist exactly two integers li;lj in L such
that li = lj = k, and
(b) if li = lj = k, then ji jj= k.
A hooked Langford sequence of order m 1 and defect 1 is a sequence L =
(l1;l2;:::;l2m;l2m+1) of 2m+ 1 nonnegative integers satisfying the conditions
(a) l2m = 0
(b) for every k2f ; + 1;:::; + m 1g, there exist exactly two integers li;lj in L such
that li = lj = k, and
(c) if li = lj = k, then ji jj= k.
For emphasis, a Langford sequence is sometimes called a perfect Langford sequence.
38
Theorem 3.7. [29] A Langford sequence of order m and defect exists if and only if
1. m 1, and
2. either m 0;1 (mod 4) and is odd, or m 0;3 (mod 4) and is even.
A hooked Langford sequence of order m and defect exists if and only if
3. m(m 2 + 1) + 2 0, and
4. either m 2;3 (mod 4) and is odd, or m 1;2 (mod 4) and is even.
Remark: Notice that every pair of integers m and satis es either Condition 2 or
Condition 4. Also, if = 2 then Conditions 1 and 3 are satis ed for all m 1 when
Conditions 2 and 4 respectively are satis ed.
The following well-known result is the purpose of introducing these sequences.
Lemma 3.8. If there exists a Langford sequence or a hooked Langford sequence of order
m and defect then, for each n > + 3m, there exists a K3-decomposition of Gn(f ; +
1;:::; + 3m 1g) or of Gn(f ; + 1;:::; + 3m 2; + 3mg) respectively.
Proof. Let (l1;:::;l2m) or (l1;:::;l2m+1) be a Langford sequence or a hooked Langford se-
quence respectively. De ne B =ff0; +m 1 +i; +m 1 +jg+tjli = lj;t2Zng. Then
(Zn;B) is the required decomposition.
3.3 Neighborhoods for 2K3x+2
The rst of the two main results of this chapter is now stated and proved.
Theorem 3.9. Let n 2 (mod 3) with n> 2, and let Q be a 2-regular multigraph on either
n 2 or n 1 vertices. Then there exists a maximum packing of 2Kn with leave a 2-cycle
such that the neighborhood graph of some vertex is Q if and only if (n;Q)6= (5;C2[C2).
39
Proof. If there exists a maximum packing of 2K5 such that the neighborhood of some vertex
is C2 [C2, then deleting the triples containing this vertex leaves the graph 2K2;2 which
contains no K3; so this case is not possible.
The su ciency is now proved. So let Q be a 2-regular graph on n 2 or n 1 vertices,
n 2 (mod 3), and (n;Q)6= (5;C2[C2). Let jV(Q)j= n 2 + with 2f0;1g. In each
case, a maximum packing (V;B) of 2Kn is produced in which the neighborhood of the vertex
10 is Q. If n2f5;8g then the result follows from Lemma 3.6, so it can be assumed that
n = 3k + 5 11.
Note that if jV(Q)j = n 2 then 10 must be in the leave, so the maximum packing
will be constructed with leave the 2-cycle (10;11). If jV(Q)j= n 1 then 10 cannot be
in the leave, so for notational convenience the maximum packing will be constructed with
leave the 2-cycle (11;13).
Case 1: Suppose that Q contains a cycle c of length 3 + . Let V = S4i=0f1ig[Z3k
and name the cycle c = (12 ;13 ;:::;14). By Lemma 3.6, let (f1i ji2Z5g;B0) be
a maximum packing of 2K5 with leave the 2-cycle (11;13 ) in which the neighborhood of
10 is the (3 + )-cycle c.
By Lemma 3:3, let G0 be a subgraph of G3k(f1;3k 2;3k 1g) isomorphic to Qnfcg.
Since G3k(f1;3k 2;3k 1g) E(G0) is a 4-regular graph, by Lemma 3:4 it has a 2-
factorization fG1;G2g. Let d = 3k 4 if k 2 0 or 3 (mod 4) and let d = 3k 5 if
k 2 1 or 2 (mod 4). By Lemma 3:4 letfG3;G4gbe a 2-factorization of G3k(f3k 3;dg).
Let B1 =ff1i;y;zgjfy;zg2E(Gi);0 i 4g. So the neighborhood of 10 is Q, and all
that remains to do is to partition the edges of G3k(f2;3;:::;3k 4gnfdg) into triples; note
that if k = 2 then this graph has no edges, so it can be assumed that k 3. By the remark
following Theorem 3.7, there exists either a perfect or a hooked Langford sequence of order
k 2 1 and defect 2, so the choice of d ensures that by Corollary 3.8 there exists a K3-
decomposition (Z3k;B2) of G3k(f2;3;:::;3k 4gnfdg). Then (f1iji2Z5g[Z3k;S2i=0Bi)
is the required decomposition.
40
Case 2: Suppose that Q contains a cycle c0 of length x + 4 + 5 + . Let V =
S4
i=0f1ig[Z3k and name the cycle c0 = (0;1;:::;x 1;12 ;13 ; :::;14;x). De ne
the cycles c00 = (12 ;13 ;:::;14) and c000 = (0;1;2;:::;x 1;x) (so if x = 1 then c000 is
a 2-cycle). Let Q0 be formed from Q by replacing c0 with c00[c000. Since Q0 contains a cycle
of length exactly 3 + , the argument in Case 1 can be used to produce a packing (V;B0) of
2Kn 5 with leave S4i=0Gi where G0 = Q0nfc00gandfG1;:::;G4gis a 2-factorization of G0 =
G3k(f1;3k 1;3k 2;3k 3;dg) E(G0) withd2f3k 4;3k 5g. Note thatfx 1;xg V(c000)
and that x+1 =2V(c000) since x+4+ jV(Q)j= n 2+ = 3k+2+ implies that x 3k 2
(so x + 16= 0). Therefore G0 contains two copies of the edge fx;x + 1g (one of di erence 1
and one of di erence 3k 1) and one copy of the edgefx 1;x+ 1g(of di erence 3k 2), so
one copy of the edge fx;x+ 1g must be in a di erent 2-factor than the edge fx 1;x+ 1g;
say these 2-factors are G4 and G2 respectively. By Lemma 3.6, let (f1iji2Z5g;B1) be
a maximum packing of 2K5 with leave the 2-cycle (11;13 ) such that the neighborhood of
10 is the ( +3)-cycle c00. Then (f1iji2Z5g[Z3k;B0[B1[ff1i;a;bgjfa;bg2E(Gi)g)
is a maximum packing of 2Kn such that the neighborhood of10 is Q0. Finally, by applying
Lemma 3.5 to this maximum packing with v =10, w = x+1, a =12 , b =14, c = x 1,
and e = x, a maximum packing of 2Kn in which the neighborhood of 10 is Q is produced.
Case 3: Suppose that = 1 and each cycle in Q is a 2-cycle. Then n is odd so let n =
6l+5 with l 1. Let V =f10g[(Z3l+2 Z2). By Lemma 3:1, let (Z3l+2; ) be an idempotent
quasigroup. By Lemma 3.2, there exists a maximum packing (Z3l+2 f1g;B1) of 2K3l+2 with
leave a 2-cycle c. Then (f10g[Z3l+2 Z2;B1[ff(a;0);(b;0);(a b;1)g;f(a;0);(b;0);(b
a;1)gj 0 a < b 3l + 1g[ff10;(a;0);(a;1)g;f10;(a;0);(a;1)gja2 Z3l+2g) is the
required decomposition with leave c.
Case 4: In view of Cases 1 and 2, suppose that if = 0 then each cycle in Q has length
2 or 4, and if = 1 then each cycle in Q has length 2;3; or 5. In view of Case 3, if = 1
then also assume that Q contains at least one cycle of length 3 or 5.
41
Case 4.1: Assume that n 17. In this subcase it is convenient to rede ne k so that
n = 3k + 8; so k 3. Let V =f1iji2Z8g[Z3k.
Suppose = 0. If Q contains only 4-cycles then let Q0 be formed from Q be replacing
one 4-cycle, say (1;16;17;2), with the two 2-cycles (16;17) and (1;2), and if Q contains
a 2-cycle, say (16;17), then let Q0 = Q. We can assume that either Q0 contains both
the 4-cycle c1 = (12;13;14;15) and the 2-cycle c2 = (16;17), or Q0 contains the three
2-cycles c1 = (12;13);c2 = (14;15); and c3 = (16;17); let c = fc1;c2g or fc1;c2;c3g
respectively.
Suppose = 1 (and hence jV(Q)j = n 1 1 (mod 3)). Since jV(Q)j 1 (mod
3), Q contains at least two cycles of length 2 (mod 3). If Q contains two 5-cycles then let
them be (0;1;16;17;2) and c1 = (11;12;13;14;15); form Q0 from Q be replacing the
rst 5-cycle with the two cycles c2 = (16;17) and c3 = (0;1;2), and let c = fc1;c2g. If
Q contains exactly one 5-cycle and a 2-cycle then let them be c1 = (11;12;13;14;15)
and c2 = (16;17); let Q0 = Q and c = fc1;c2g. If Q contains no 5-cycles then it must
contain two 2-cycles and a 3-cycle (in view of Case 3), say c1 = (11;12), c2 = (16;17),
and c3 = (13;14;15); let Q0 = Q and c =fc1;c2;c3g.
In either case, by Lemma 3:6 let (f1i ji2 Z8g;B0) be a maximum packing of 2K8
with leave the 2-cycle (11;13 ) such that the neighborhood of 10 is c .
By Lemma 3:3, let G0 be a subgraph of G3k(f1;3k 2;3k 1g) isomorphic to Q0nfc g.
Let d = 3k 7 if k 3 0 or 3 (mod 4) and let d = 3k 8 if k 3 1 or 2 (mod 4).
Since G = G3k(f1;3k 1;3k 2;3k 3;3k 4;3k 5;3k 6;dg) E(G0) is a 14-regular
graph, by Lemma 3:4 it has a 2-factorization fG1;G2;:::;G7g. Note that if Q06= Q, then
Q0nc contains either the cycle (1;2) or the cycle (0;1;2), which implies that G0 does not
contain any copies of the edge f1;3g or f2;3g and hence that G contains two copies of the
edge f2;3g and one copy of the edge f1;3g. Thus one copy of the edge f2;3g must be in a
di erent 2-factor than the edge f1;3g; say these 2-factors are G7 and G6 respectively. Let
B1 = ff1i;y;zgjfy;zg2E(Gi);0 i 7g. So the neighborhood of 10 is Q0, and all
42
that remains to do is to partition the edges of G3k(f2;3;:::;3k 7gnfdg) into triples; to
do so, note that this graph is graph is empty if k = 3, so we can assume that k 4. There
exists either a perfect or a hooked Langford sequence of order k 3 1 and defect 2, so
the choice of d ensures that by Corollary 3.8 there exists a K3-decomposition (Z3k;B2) of
G3k(f2;3;:::;3k 7gnfdg). Then (f1iji2Z8g[Z3k;S2i=0Bi) is a maximum packing of
2Kn such that the neighborhood of10 is Q0. If Q06= Q then apply Lemma 3.5 with v =10,
w = 3, a =16, b =17, c = 1, and e = 2 to produce a maximum packing of 2Kn in which
the neighborhood of 10 is Q.
Case 4.2: Assume that n = 14, jV(Q)j = 13, and Q contains a 5-cycle, c. By Lemma
3.6, let (f1i ji2Z6g;B1) be a K3-decomposition of 2K6 such that the neighborhood of
10 is the 5-cycle c2Q. By Lemma 3:3, let G0 be a subgraph of G8(f1;6;7g) isomorphic to
Qnfcg. Since G8(f1;6;7g) E(G0) is a 4-regular graph, by Lemma 3:4 it has a 2-factorization
fG1;G2g. Let B2 =ff0;2;5g;f1;3;6gg. Then (G8(f2;3;4;5g))n(E(B2)[f4;7g[f4;7g) is
a 6-regular graph so it has a 2-factorization fG3;G4;G5g. Then (f1i ji2Z6g[Z8;B1[
B2[ffa;b;1igjfa;bg2E(Gi);0 i 5g) is the required decomposition (with leave the
2-cycle (4;7)).
Case 4.3: Assume that n = 14,jV(Q)j= 13, and Q contains a 3-cycle, c. By Lemma 3.6,
let (f1iji2Z4g;B1) be a K3-decomposition of 2K4 such that the neighborhood of10 is the
3-cycle c2Q. By Lemma 3:3, let G0 be a subgraph of G10(f1;8;9g) isomorphic to Qnfcg.
Since G10(f1;8;9g) E(G0) is a 4-regular graph, by Lemma 3:4 it has a 2-factorization
fG1;G2g. LetB2 =ff0;2;5g;f0;5;7g;f1;3;6g;f1;6;8g;f2;4;7g;f2;7;9g;f3;5;8g;f0;3;8g;
f0;4;6g;f1;5;9g;f0;3;7g;f1;4;7g;f1;4;8g;f3;6;9g;f2;6;9g;f2;5;8gg[ff13;i;i+4gji2
Z10g. Then (f1iji2Z4g[Z10;B1[B2[ffa;b;1igjfa;bg2E(Gi);0 i 2g) is the
required decomposition (with leave the 2-cycle (4;9)).
Case 4.4: Assume that n = 14,jV(Q)j= 12, and Q contains 4-cycles where 0 3.
Let B = (ffi;i + 3;i + 4g;fi;i + 2;i + 5g;fi;i + 4;i + 5g;f10;i;i + 6g;f11;i;i + 2gji2
Z12gnffj;j + 3;j + 4g;fj + 4;j + 6;j + 9g;f10;j;j + 6g;f10;j + 3;j + 9gj 1 j
43
g)[ffj;j + 4;j + 6g;fj + 3;j + 4;j + 9g;f10;j;j + 3g;f10;j + 6;j + 9gj1 j g.
Then (Z12[f10;11g;B) is a maximum packing of 2K14 with leave (10;11) such that the
neighborhood of 10 consists of 4-cycles and 12 4 2 2-cycles as required.
Case 4.5: Assume that n = 11. It is impossible forjQj= 9 and to have Q consist only of
2-cycles and 4-cycles, so assume that jQj= 10. Let B =ff10;0;1g;f10;0;1g;f10;2;3g;
f10;2;3g;f10;4;5g;f10;4;6g;f10;5;6g;f10;7;8g;f10;7;9g;f10;8;9g;f0;2;4g;
f0;2;7g;f0;3;5g;f0;3;8g;f1;2;6g;f1;2;9g;f1;3;4g;f1;3;7g;f0;4;8g;f0;5;9g;f0;6;7g;
f0;6;9g;f1;4;9g;f1;5;7g;f1;5;8g;f1;6;8g;f2;4;8g;f2;5;8g;f2;5;9g;f2;6;7g;f3;4;9g;
f3;5;7g;f3;6;8g;f3;6;9g;f4;5;6g;f7;8;9gg. Then (V = f10g[Z10;B) is a maximum
packing of 2K11 with leave (4;7) in which the neighborhood of10 is C2[C2[C3[C3. Since
the triples f0;4;8g;f1;5;8g2B, apply Lemma 3.5 to (V;B) with v = 10, w = 8, a = 0,
b = 1, c = 4, and e = 5, to replace the cycles (0;1) and (4;5;6) in the neighborhood of 10
with the cycle (0;1;5;6;4), so in the resulting maximum packing (V;B0) the neighborhood
of 10 is C5[C2[C3. Finally, since the triples f2;7;6g;f3;9;6g2B0, apply Lemma 3.5 to
(V;B0) with v =10, w = 6, a = 2, b = 3, c = 7, and e = 9, to replace the cycles (2;3) and
(7;8;9) in the neighborhood of10 with the cycle (2;3;9;8;7), so in the resulting maximum
packing (V;B00) the neighborhood of 10 is C5[C5.
3.4 Quadratic Leaves
Having proved Theorem 3:9, it can now be used along with the corresponding Colbourn
and Rosa result (see [9]) to assist in proving the second main result of this chapter.
Theorem 3.10. Let Q be a quadratic graph in Kn. There exists a K3-decomposition of
Kn E(Q) if and only if
1. (n 1) is even,
2. jE( Kn)j jE(Q)j is divisible by 3,
3. ( ;n;Q) =2f(1;7;C3[C3);(1;9;C4[C5);(2;6;C3[C3);(2;5;C2[C3)g, and
44
4. if 6= 2 then n6= 2.
Proof. To see the necessity of Conditions (1 4) consider the following. If ( ;n;Q) 2
f(1;7;C3[C3);(1;9;C4[C5)g then by the Colbourn and Rosa result (see Theorem 1.2),
there is no K3-decomposition of Kn E(Q). If ( ;n;Q) 2f(2;5;C2[C3);(2;6;C3[C3)g
and if there exists a K3-decomposition (Zn;B1) of 2Kn E(Q) then (Zn+1;B1[ffn;a;bgj
fa;bg2E(Q)g) is a K3-decomposition of 2Kn+1 in which the neighborhood of n is Q; but
this contradicts Theorem 1.1. This proves the necessity of Condition (3). The necessity of
Conditions (1) and (2) follows since each vertex in each triple has even degree and each triple
contains 3 edges respectively. The necessity of Condition (4) is clear since K2 contains no
copies of K3.
To prove the su ciency, the result is clear if n 2, and the result follows from Theorem
1.2 if = 1, so assume that n 3 and 2. Let Q be a quadratic graph such that
Conditions (1 3) are satis ed.
Case 1: Suppose = 2.
If (n;Q) 2f(5;C2);(6;C3)g then the result follows in each case from Lemma 3.2 by
taking a maximum packing of 2Kn, then removing any one triple if n = 6. By Condition
2, jE(Q)j n (mod 3) where = 1 if n 1 (mod 3) and = 0 otherwise. Form the
2-regular graph Q0 on n vertices by adding n jE(Q)j 3 3-cycles to Q (by Condition (2) this
is an integral number of 3-cycles). Let B =ffx;y;zgj(x;y;z)2Q0nQg. It can be assumed
that (n+1;Q0) =2f(7;C3[C3);(6;C2[C3)gsince (n+1;Q0)2f(7;C3[C3);(6;C2[C3)gonly
if (n;Q)2f(5;C2);(6;C3);(5;C2[C3);(6;C3[C3)g, where the rst two are handled at the
beginning of this case and the last two are prohibited by Condition 3. So by either Theorem
1.1 or 3.9 there exists a maximum packing (Zn+1;B0) of 2Kn+1 in which the neighborhood
of the vertex n is Q0. Then (Zn;(B0nfb2B0jn2bg)[B) is the required decomposition.
Case 2: Suppose > 2 and n 0 or 1 (mod 3). First suppose that (n;Q)6= (6;C3[C3).
By Condition 2, jE(Q)j 0 (mod 3) regardless of the value of . By the result of Case 1,
let (Zn;B0) be a K3-decomposition of 2Kn E(Q). Let (Zn;B1) be a K3-decomposition of
45
( 2)Kn; this exists by Lemma 3.2 since n 0 or 1 (mod 3) and since if n is even then
2 is even by Condition (1). Then (Zn;B0[B1) is the required decomposition. Using
Lemma 3.2, if (n;Q) = (6;C3[C3) then let (Z6;B1) and (Z6;B2) be K3-decompositions of
2K6 such that f0;1;2g2B1 and f3;4;5g2B2, and let (Z6;B3) be a K3-decomposition of
( 4)K6. Then (Z6;B1[B2[B3nff0;1;2g;f3;4;5gg) is the required decomposition.
Case 3: Suppose > 2 and n 2 (mod 3). Let V(Q) Zn. By Condition (4), n6= 2.
First suppose that n 6= 5. Let (mod 3) with 2f2;3;4g if n 5 (mod 6) and
2f2;4;6g if n 2 (mod 6). By Lemma 3.2 and Conditions (1) and (2) there exists a
K3-decomposition (Zn;B0) of ( )Kn.
If = 2 then by Condition (2) jE(Q)j 2 (mod 3), so by Case 1 let (Zn;B1) be a
K3-decomposition of 2Kn E(Q).
If = 4 then by Condition (2)jE(Q)j 1 (mod 3) sojE(Q)j n 1, so say 0 =2V(Q)
and that (1;:::;x) is a cycle in Q. Form Q0 from Q by replacing the cycle (1;:::;x) in Q with
the cycle (0;1;:::;x). By Case 1 there exists a K3-decomposition (Zn;B01) of 2Kn E(Q0).
By Lemma 3.2 let (Zn;B001) be a maximum packing of 2Kn with leave the 2-cycle (1;x). Let
B1 = B01[B001 [f0;1;xg.
If 2f3;6g then by Condition (2) jE(Q)j 0 (mod 3), so say 0;1 =2 V(Q). Form
Q0 from Q by adding the 2-cycle (0;1). By Case 1 let (Zn;B01) be a K3-decomposition of
2Kn E(Q0). By Lemma 3.2 let (Zn;B001) be a maximum packing of ( 2)Kn with leave
the 4-cycle (2;0;3;1). Let B1 = B01[B001 [ff0;1;2g;f0;1;3gg.
Then for each 2f2;3;4;6g, (Zn;B0[B1) is the required decomposition.
Finally, suppose that n = 5. Based on the above argument, it su ces to nd packings
of K5 with leave Q for ( ;Q)2f(2;C5);(3;C3);(4;C4);(4;C2[C2);(5;C2[C3)g. ( ;Q) =
(2;C5) was handled in Case 1. When ( ;Q) = (3;C3), by Lemma 3.2 let (Z5;B) be a K3-
decomposition of 3K5 and let b2B; then (Z5;Bnb) is the required decomposition. When
( ;Q) = (4;C4) the result follows from Lemma 3.2 by taking a maximum packing of 4K5.
When ( ;Q) = (4;C2[C2), by Lemma 3.2 let (Z5;B1) and (Z5;B2) be maximum packings of
46
2K5 with leaves (0;1) and (2;3) respectively; then (Z5;B1[B2) is the required decomposition.
Finally, when ( ;Q) = (5;C2[C3), by Lemma 3.2 let (Z5;B1) be a K3-decomposition of
3K5 that contains the triple f0;1;2g, and let (Z5;B2) be a maximum packing of 2K5 with
leave the 2-cycle (3;4); then (Z5;B1[B2nf0;1;2g) is the required decomposition.
47
Chapter 4
Neighborhoods in Maximum Packings of 2Kn- A Second Version
4.1 Introduction
Having completed the solution to the neighborhood graph problem in the last chapter
by solving the case where n 2 (mod 3), this chapter focuses on nding a uni ed proof
for the neighborhood graph problem. While the proof technique used in the last chapter
for n 2 (mod 3) is similar in principle to the proof technique used in the corresponding
Colbourn and Rosa result, it does not seem that the techniques used in either proof can be
used to readily obtain the other result, even if one \allows" extreme cases (such as the case
when each cycle in the neighborhood has length two) to be handled using alternate methods.
In this chapter, a new, simpler, and uni ed proof that obtains both results is provided (see
Theorem 4.5). However, this new proof relies heavily on a major result, namely a recent
and quite powerful result due to Bryant, Horsley, and Pettersson (see Theorem 4.3). Section
4:2 will begin with some well-known lemmas that are useful in handling extreme cases of
Theorem 4.5. The theorem of Bryant, Horsley, and Pettersson will then be given and used
to establish a lemma that will be used in several cases of the proof of the main theorem.
Finally, Section 4:3 contains the new proof of the main theorem.
4.2 Preliminary Results
To begin this section, two well-known results are given, one being on idempotent quasi-
groups and the other on maximum partial triple systems. These lemmas will be used to
handle extreme cases of the main theorem (speci cally the cases where n 1 or 5 (mod 6)
and Q contains only 2-cycles).
48
Lemma 4.1. [27] There exists an idempotent quasigroup of order n for all n6= 2.
The second lemma is more extensive than what appears below; however, what appears
below is su cient for this chapter.
Lemma 4.2. [14] The leave of a maximum partial triple system of Kn is
1. ? if = 2 and n 0;1 (mod 3),
2. a 2-cycle if = 2 and n 2 (mod 3),
3. a K1;3 and n 42 independent edges if = 1 and n 4 (mod 6), and
4. a 1-factor if = 1 and n 2 (mod 6).
The powerful cycle-decomposition theorem of Bryant, Horsley, and Petterson from [5]
appears next.
Theorem 4.3. [5]
1. Let n be odd. There exists a decomposition of Kn into cycles of length m1;:::;mt if
and only if
(a) 3 mi n for 1 i t and
(b) Pti=1mi = n2 .
2. Let n be even. There exists a decomposition of Kn into cycles of length m1;:::;mt and
a 1-factor F if and only if
(a) 3 mi n for 1 i t and
(b) Pti=1mi = n2 n2 .
This result provides the backbone of the proof technique used in this chapter, estab-
lishing that Kn minus the edges of a certain set of cycles and possibly a 1-factor can be
decomposed into triples.
49
The full power of this result is not needed for the main theorem, since at most three
cycle lengths are chosen for any particular case. However, while older and more basic results
can be used in many of the cases, it does not seem like older results are su cient to handle all
cases in the proof of the theorem (for instance, the case in which Kn needs to be decomposed
into a 1-factor, a Hamilton cycle, a near Hamilton cycle, and triples.)
A lemma that will be used in multiple cases in the proof of Theorem 4.5 is now given.
The lemma and the proof of it will look quite similar to the proofs that appear in the cases
of the proof of the main theorem; this lemma is stated here however since it is used in several
cases of the main theorem.
Lemma 4.4. Let n 0 (mod 3) and let Q be a 2-regular graph on n vertices. Then for any
integer 2 k n 1, there exists a decomposition of 2Kn into triples and k 2-factors, one
of which is Q.
Proof. Let 2f0;1g with n (mod 2). Let Q = fc0;:::;cq 1g, where for each i2Zq,
the cycle ci = (ci;1;:::;ci;li) has length li. Since n 0 (mod 3), the number of edges in any
Hamilton cycle of Kn and any 1-factor of Kn is a multiple of 3. Further, since jE(Kn)j 0
(mod 3), by Theorem 4.3, Kn can be decomposed into j Hamilton cycles for 0 j n 2+ 2 ,
1 1-factors, and triples. So let (Zn;B1) be a K3-decomposition of Kn E(G1), where G1
consists of the h = minfk 1;n 2+ 2 g Hamilton cycles H1;:::;Hh, along with the 1-factor
F0 if = 0. In particular, let H1 = (c0;1;:::;c0;l0;c1;1;:::;c1;l1;:::;cq 1;1;:::;cq 1;lq 1).
Let (Zn;B2) be a K3-decomposition of Kn E(G2) where G2 contains the k h 1 +
Hamilton cycles Hh+2 ;:::;Hk, along with the 1-factor F1 if = 0. Note that if = 1,
then k h 1 + = k h k (k 1) = 1 so G2 contains a Hamilton cycle in this
case. If = 1 then let Hh+1 = (c0;1;c0;l0;c1;1;c1;l1;:::;cq 1;1;cq 1;lq 1;v1;:::;vn 2q) where
v1;:::;vn 2q are arbitrarily named. If = 0 then name the vertices so that q of the edges in
F1 are in ffci;1;ci;ligji2Zqg and let Hh+1 = F0[F1.
Let H01 be the 2-factor induced by (E(H1)[ffci;1;ci;ligji2Zqg)nffci;li;ci+1;1gji2Zqg
reducing the sum in the subscript modulo q. Then H01 Q. The graph H0h+1 induced by
50
E(H1)[E(Hh+1) E(H01) is a 2-factor. Finally, for i2f1;2;:::;kgnf1;h+1g, let H0i = Hi.
Then (Zn;B1[B2[[i2ZkH0i) is the required decomposition.
4.3 Main Result
The main theorem is now stated and proved. The theorem was previously proved by
Colbourn and Rosa in [9] when n 0 or 1 (mod 3) and in Chapter 3 when n 2 (mod 3).
Theorem 4.5. [7, 9] Suppose n6= 2. Let Q be a 2-regular multigraph on n 1 vertices
with 2f0;1g. Then there exists a maximum packing of 2Kn (possibly the leave is empty)
such that the neighborhood graph of some vertex is Q if and only if
1. = 0 if n 0 or 1 (mod 3) and
2. (n;Q) =2f(5;C2[C2);(6;C2[C3);(7;C3[C3)g.
Proof. If n 0 or 1 (mod 3), then a maximum packing of 2Kn is a 2-fold triple system, so
the neighborhood graph of every vertex will be a 2-regular graph on n 1 vertices so = 0
in these cases, which shows the rst condition is necessary.
If (n;Q) = (5;C2[C2);(6;C2[C3); or (7;C3[C3) and there exists a maximum packing
of 2Kn such that the leave of some vertex v is Q, then deleting the triples containing v leaves
the graph K2W2K2, K2W2K3, or K3W2K3 respectively. So each graph can be thought of
as a graph with two parts with 2 edges joining each pair of vertices in di erent parts. In
each case, any triple that contains an edge with its incident vertices in di erent parts (a
mixed edge) contains 2 such edges and 1 edge whose incident vertices lie in the same part (a
pure edge). But in each case, there are more than twice as many mixed edges as pure edges
remaining. Hence these cases are not possible.
To prove the su ciency, two extreme cases (Case 1) will be followed by 9 main cases.
While this is a large number of cases, most follow from Lemma 4.4 or from similar ideas.
Let Q be a 2-regular multigraph on n 1 vertices (with the size of Q speci ed in each
case) such that (n;Q) =2f(5;C2[C2);(6;C2[C3);(7;C3[C3)g.
51
Case 1: Suppose n 1 or 5 (mod 6) and that Q consists entirely of 2-cycles (so since
n is odd then = 0). By assumption (n;Q) 6= (5;C2[C2), and the case where n = 1 is
trivial. So it can be assumed that n 7; let n = 6l + 1 + with l 1 and 2f0;4g.
Let V = f11g[(Z3l+ 2 Z2). By Lemma 4:1, let (Z3l+ 2; ) be an idempotent quasigroup
(l 1, so 3l + 2 3, so the quasigroup exists). By Lemma 4.2, there exists a maximum
packing (Z3l+ 2 f1g;B1) of 2K3l+ 2 with leave c where c is a 2-cycle if = 4 and c = ?
otherwise. Then (f11g[(Z3l+ 2 Z2);B1[ff(a;0);(b;0);(a b;1)g;f(a;0);(b;0);(b a;1)gj
0 a** 8, a maximum packing is constructed on the vertex set Zn 4[f1jj1 j 4g
where the neighborhood of11 is Q =fc0;:::;cq 1g, where c0 = (12;13;14), and the q 1
other-cycles are de ned on the vertex set Zn 4. The maximum packing will be constructed
so that the leave will be (13;a), where a is de ned below.
54
For each i2(Zqnf0g), let ci = (ci;1;:::;ci;li) where li is the length of ci. In this case,
n 4 4 (mod 6) and 10 and thus (n 4)2 (n 4) n 42 (n 4 1) and (n 4)2 (n 4) n 42
are both divisible by 3 and nonnegative. So by Theorem 4.3, let (Zn 4;B1) be a K3-
decomposition of Kn 4 (E(H1)[E(H3)[E(F1)) and let (Zn 4;B2) be a K3-decomposition
of Kn 4 (E(H2)[E(F2)) where H1 and H2 are Hamilton cycles, H3 is a near-Hamilton
cycle with arbitrarily named vertex a2Zn 4 omitted, F1 and F2 are 1-factors, and H1 and
H2 are named as follows: Let H1 = (c1;1;:::;c1;l1;c2;1;:::;c2;l2;:::;cq 1;1;:::;cq 1;lq 1). Let
H2 = (c1;1;c1;l1;c2;1;c2;l2;:::;cq 1;1;cq 1;lq 1;v1;:::;vn+2 2q) where v1;:::;vn+2 2q are arbi-
trarily named.
Let H01 be the graph induced by (E(H1)[ffci;1;ci;ligji2Zqnf0gg)n(ffci;li;ci+1;1gji2
Zqnf0;q 1gg[ffcq 1;lq 1;c1;1gg). Let H2 be the graph induced by (E(H1)[E(H2))nE(H01).
Then H01 and H02 are 2-regular spanning subgraphs of Kn 4, with the set of cycles formed
by the components in H01 being Qnc0. Let H03 = H3 and H04 be the graph induced by
E(F1)[E(F2).
Let (f1j j1 j 4g;B3) be a K3-decomposition of 2K4 (where the neighborhood of
11 is the 3-cycle (12;13;14)).
Then (Zn 4[f1j j1 j 4g;B1[B2[B3[ff1i;ai;bigjfai;big2E(H0i)g) is the
required decomposition.
Case 6: Suppose n 0 (mod 3), = 0, and that Q has a 2-cycle.
A maximum packing is constructed on the vertex set Zn 3 [ff1jg j 1 j 3g
where the neighborhood of 11 is Q = fc0;:::;cq 1g, where c0 = (12;13), and the q 1
other-cycles are de ned on the vertex set Zn 3.
Note that n6= 6, since otherwise Q = C2[C3 and (n;Q)6= (6;C2[C3) by assumption.
The case n 3 is trivial. Otherwise w = n 3 0 (mod 3) and 3 w 1, so by Lemma
4.4, there exists a K3-decomposition (Zn 3;B) of 2Kn 3 (E(H01)[E(H02)[E(H03)) where
H01; H02; and H03 are 2-regular graphs and H01 Qnc0.
55
Let (ff1jgj1 j 3g;B3) be a K3-decomposition of 2K3 (where the neighborhood
of 11 is the 2-cycle (12;13)).
Then (Zn 3[ff1jgj 1 j 3g;B1[B2[B3[ff1i;ai;bigjfai;big2E(H0i)g) is
the required decomposition.
Case 7: Suppose n 0 (mod 6), = 0, and that Q has no cycles of length 2 (and hence
one of length at least 4).
First, suppose n = 6. De ne B =ff11;5;0g;f11;5;1g;f11;0;2g;f11;1;3g;
f11;2;3g;f5;0;3g;f5;1;2g;f5;2;3g;f0;1;2g;f0;1;3gg. Then (Z5[f11g;B) is a maximum
packing of 2K6 such that the neighborhood of 11 is C5.
Otherwise for n 12, a maximum packing is constructed on the vertex set Zn 2 [
ff1jgj1 j 2g where the neighborhood of 11 is Q =fc0;:::;cq 1g.
For each i2Zq, let ci = (ci;1;:::;ci;li) where li is the length of ci, cj;k 2Zn 2 for all
(j;k)6= (0;2), andc0;2 =12. In this case, n 2 4 (mod 6) and thus (n 2)2 n 22 (n 2 3)
and (n 2)2 n 22 1 are both divisible by 3, and since n 2 10, both quantities are nonneg-
ative. So by Theorem 4.3, let (Zn 2;B1) be a K3-decomposition of Kn 2 (E(H1)[E(F1))
and by Lemma 4.2, let (Zn 2;B2) be a K3-decomposition of Kn 2 E(H2) where H1 is a n 5
cycle, H2 consists of a K1;3 and (n 2) 42 independent edges, F1 is a 1-factor, and H1 and H2 are
named as follows: If l0 = 4, let H1 = (c1;1;:::;c1;l1;c2;1;:::;c2;l2;:::;cq 1;1;:::;cq 1;lq 1) (so
that c0;1;c0;3; and c0;4 are omitted) and if l0 5, let H1 = (c0;4;c0;5;:::;c0;l0;c1;1;:::;c1;l1;c2;1;
:::;c2;l2;:::;cq 1;1;:::;cq 1;lq 1 1) (so that c0;1;c0;3; and cq 1;lq 1 are omitted). If l0 = 4, let
H2 be de ned to contain the edges fci;1;ci;lig for each i2Zq as well as the edges fc0;4;c0;3g
andfc0;4;c1;2g(note that c1;2 6= c1;l1 since all cycles have length greater than 2 and note that
c0;4 is the vertex of degree 3 in H2) and nally (n 2) 4 2(q 1)2 arbitrarily named edges. If
l0 5, let H2 be de ned to contain the edges fci;1;ci;lig for each i2Zq as well as the edges
fc0;3;c0;4g;fcq 1;lq 1;cq 1;lq 1 1g; and fcq 1;lq 1;c1;2g (note that c1;2 6= c1;l1 since all cycles
have length greater than 2, c0;4 6= c0;l0 since l0 5, and cq 1;lq 1 is the vertex of degree 3 in
H2) and nally (n 2) 4 2q2 arbitrarily named edges.
56
Note that in each case[q 1i=1E(ci)[E(c00) E(H1)[E(H2) where c00 is formed from c0 by
removing the edges fc0;1;c0;2g and fc0;2;c0;3g. Let H01 be the graph induced by [q 1i=1E(ci)[
E(c00) and let H02 be the graph induced by (E(H1)[E(H2))nE(H01). Then every vertex has
degree 2 in H01 and H02 except c0;1 and c0;3 both of which have degree 1 in both H01 and H02.
Then (Zn 2 [ff1jg j 1 j 2g;B1 [B2 [ff1i;ai;big j fai;big 2 E(H0i)g[
ff11;12;c0;lgjl2f1;3gg) is the required decomposition.
Case 8: Suppose n 1 or 3 (mod 6), = 0, and that Q has a cycle of length at least 4.
A K3-decomposition of 2Kn will be constructed on the vertex set Zn 2[f11;12gsuch
that the neighborhood of the vertex 11 is Q.
Let Q =fc0;:::;cq 1g where for each i2Zq, the cycle ci = (ci;1;:::;ci;li) has length li,
cj;k 2Zn 2 unless (j;k) = (0;2), c0;2 = 12, and l0 4. Since n 2 1 or 5 (mod 6), by
Theorem 4.3, there exists a decomposition of Kn 2 into triples and a near-Hamilton cycle.
So let (Zn 2;B1) be a K3-decomposition of Kn 2 E(H1), where H1 is a near-Hamilton
cycle named so that H1 = (c0;3;c0;4;c0;5;:::;c0;l0;c1;1;:::;c1;l1;:::;cq 1;1;:::;cq 1;lq 1) (so
c0;1 is omitted). Let (Zn 2;B2) be a K3-decomposition of Kn 2 E(H2), where H2 is the
near-Hamilton cycle H2 = (c0;1;c0;l0;c1;1;c1;l1;:::;cq 1;1;cq 1;lq 1;v1;:::;v(n 2) 1 2q) where
v1;:::;v(n 2) 1 2q omit c0;3 and are otherwise arbitrarily named. (Note that c0;3 6= c0;l0 since
l0 4.) Then c0;1 has degree 2 in H2 and degree 0 in H1, c0;3 has degree 2 in H1 and degree
0 in H1, and every other vertex in Zn 2 has degree 2 in both H1 and H2.
Let H01 be the graph induced by (E(H1)[ffci;1;ci;ligji2Zqg)n(ffci;li;ci+1;1gji2Zqg[
ffc0;3;cq 1;lq 1gg) reducing the sum in the subscript modulo q. (Note that fc0;1;cq 1;lq 1g=2
E(H1) so this edge is not removed). Note that in H01 every vertex in Zn 2 has degree 2
except c0;1 and c0;3, both of which have degree 1. Let H02 be the graph induced by (E(H1)[
E(H2))nE(H01). Note that in H02, every vertex in Zn 2 has degree 2 except c0;1 and c0;3,
both of which have degree 1. The set of cycles formed by the components in H01 contains
the cycles c1;:::;cq 1 and c00 where c00 is formed from c0 by deleting the edges fc0;1;c0;2g and
fc0;2;c0;3g.
57
Then (Zn[f11;12g;B1[B2[ff1i;ai;bigjfai;big2E(H0i);1 i 2g[ff11;12;c0;lgj
l2f1;3gg) is the required K3-decomposition.
Case 9: Suppose n 1 (mod 3), = 0, and that Q has a 3-cycle.
A maximum packing is constructed on the vertex set Zn 4[ff1jgj1 j 4gwhere
the neighborhood of 11 is Q = fc0;:::;cq 1g, where c0 = (12;13;14), and the q 1
other-cycles are de ned on the vertex set Zn 4.
When n = 4, the result is trivial, and Q cannot have a 3-cycle when n = 1 (obviously)
or when n = 7 (since then Q = C3[C3, and (n;Q)6= (7;C3[C3) by assumption). So it can
be assumed that n 10. Then w = n 4 0 (mod 3) and 4 w 1. So by Lemma 4.4,
there exists a K3-decomposition (Zn 4;B) of 2Kn 4 (E(H1)[E(H2)[E(H3)[E(H4))
where H1; H2;H3, and H4 are 2-regular graphs and H1 Qnc0.
Let (ff1jgj1 j 4g;B3) be a K3-decomposition of 2K4 (where the neighborhood
of 11 is the 3-cycle (12;13;14)).
Then (Zn 4[ff1jgj1 j 4g;B[B3[ff1i;ai;bigjfai;big2E(Hi);1 j 4g
is the required decomposition.
Case 10: Suppose n 4 (mod 6), = 0, and that Q has a cycle of length at least 5.
A maximum packing is constructed on the vertex set Zn 2[ff1jgj1 j 2gwhere
the neighborhood of 11 is Q =fc0;:::;cq 1g.
For each i 2 Zq, let ci = (ci;1;:::;ci;li) where li is the length of ci, l0 5, cj;k 2
Zn 2 for all (j;k) 6= (0;2), and c0;2 = 12. In this case, n 2 2 (mod 6) and thus
(n 2)
2
n 2
2 (n 2 2) and
(n 2)
2
n 2
2 are both divisible by 3, and since n 2 8,
both quantities are nonnegative. So by Theorem 4.3, let (Zn 2;B1) be a K3-decomposition
of Kn 2 (E(H1)[E(F1)) and let (Zn 2;B2) be a K3-decomposition of Kn 2 (E(F2))
where H1 is a n 4 cycle, F1 and F2 are 1-factors, and H1 and F2 are named as follows: Let
H1 = (c0;4;c0;5;:::;c0;l0;c1;1;:::;c1;l1;c2;1;:::;c2;l2;:::;cq 1;1;:::;cq 1;lq 1) (so that c0;1 and
c0;3 are omitted). Let F2 be de ned to contain the edges fci;1;ci;lig for each i2Zq as well
58
as the edge fc0;3;c0;4g and nally n 2 2q 22 arbitrarily named edges. (Note that c0;4 6= c0;l0
since l0 5.)
Note that[q 1i=1E(ci)[E(c00) E(H1)[E(H2) where c00 is formed from c0 by removing
the edges fc0;1;c0;2g and fc0;2;c0;3g. Let H01 be the graph induced by [q 1i=1E(ci)[E(c00) and
let H02 be the graph induced by (E(H1)[E(H2))nE(H01). Then every vertex has degree 2
in H01 and H02 except c0;1 and c0;3 both of which have degree 1 in both H01 and H02.
Then (Zn 2 [ff1jg j 1 j 2g;B1 [B2 [ff1i;ai;big j fai;big 2 E(H0i)g[
ff11;12;c0;lgjl2f1;3gg) is the required decomposition.
Note that this covers all the cases since Q must contain an odd cycle when n 2 (mod
6) and = 0, Q cannot contain all 3-cycles when n 0 (mod 3) (jQj= 2 (mod 3)), and Q
cannot consist entirely of even cycles when n 4 (mod 6).
59
Chapter 5
Quadratic Excesses or Paddings of Covers with Triples of Kn
5.1 Introduction
Having found a solution to the quadratic leave problem (completed in Chapter 3), this
chapter will focus on the quadratic excess problem. As mentioned in the introduction,
Colbourn and Rosa found necessary and su cient conditions for a quadratic graph to be the
excess of a cover of Kn when = 1 (see [10]). In this chapter, their results are extended to
all (see Theorem 5.2).
5.2 Results
In this section, the main result of the chapter is given, namely necessary and su cient
conditions for a quadratic graph to be the excess of a cover of Kn (naturally it is assumed
that 1 in this chapter). However, to begin a very well known theorem on maximum
packings and minimum covers of Kn (packings and covers for which the leave and excess
have as few edges as possible) is given.
Theorem 5.1. [14, 23] Let 1 and n6= 2. Let P (or L) be any multigraph with the least
number of edges in which all vertices have degree congruent to (n 1) (mod 2) and with
jE(P)j+ n(n 1)2 0 (mod 3) (or n(n 1)2 jE(L)j 0 (mod 3) respectively). Then there
exists a K3-decomposition of Kn[E(P) (or Kn E(L) respectively).
The statement and proof of the main theorem are now given.
Theorem 5.2. Let Q be a quadratic graph on n vertices. Then Q is the excess of a cover
of Kn if and only if
60
1. (n 1) is even,
2. jE(Q)j+jE( Kn)j 0 (mod 3), and
3. n6= 2.
Proof. The necessity of Conditions (1) and (2) follows since each vertex in each triple has
even degree and each triple contains 3 edges respectively. The necessity of Condition (3) is
clear since K2 +E(Q) contains no copies of K3.
To prove the su ciency, suppose that (1 3) hold. Several cases are considered in turn.
Case 1: n 1;3 (mod 6)
By Theorem 5.1, let (V;B1) be a K3-decomposition of ( 1)Kn (with L = ;). By
Condition (2) and Theorem 1.3, let (V;B2) be a cover of Kn with excess Q. Then (V;B1[B2)
is the required cover.
Case 2: n 5 (mod 6)
Let 2f1;2;3g with (mod 3). Note that jE( Kn)j jE( Kn)j (mod 3). Since
n 5 (mod 6), by Theorem 5.1, there exists a K3-decomposition (V;B1) of ( )Kn.
If = 1 then by Condition (2) and Theorem 1.3, let (V;B2) be a cover of Kn with excess
Q.
Suppose = 2. By Condition (2),jE(Q)j 1 (mod 3). Sincen 2 (mod 3), some vertex
inV has degree 0 inQ, sayx. Letc = (c0;c1;:::;ci) be a cycle inQand letc0 = (c0;x;c1;:::;ci).
Form Q0 from Q by replacing c with c0. Q0 is quadratic on the vertex set V andjE(Q0)j 2
(mod 3), so by Theorem 1.3, let (V;B02) be a cover of Kn with excess Q0. By Theorem 5.1,
let (V;B002) be a maximum packing of Kn with leave the 4-cycle (c0;x;c1;d) where d is any
vertex in V other than c;x0; and x1 (this exists since in this case n 5 (mod 6) so n 5).
Let B2 = B02[B002 [ffc0;c1;dgg.
If = 3 then by Condition 2 jE(Q)j 0 (mod 3). Since n 2 (mod 3), some vertex in
V has degree 0 in Q, say x. Let c = (c0;c1;:::;ci)2Q and let c0 = (c0;x;c1;:::;ci). Form Q0
from Q by replacing c with c0. Q0 is quadratic on the vertex set V andjE(Q0)j 1 (mod 3),
61
so by the previous case in this proof when = 2, let (V;B02) be a cover of 2Kn with excess Q0.
By Theorem 5.1, let (V;B002) be a maximum packing of Kn with leave the 4-cycle (c0;x;c1;d)
where d is any vertex in V other than x;c0; and c1. Let B2 = B02[B002 [ffc0;c1;dgg.
Then in each subcase ( = 1;2; and 3), (V;B1[B2) is the required cover.
Case 3: n 4 (mod 6)
Since n 4 (mod 6), by Condition (1), is even. By Theorem 5.1, let (V;B1) be a
K3-decomposition of ( 2)Kn.
By Condition (2), jE(Q)j 0 (mod 3). Hence, Q also satis es the conditions for an
excess for v = n 1 and = 1. So let x 2 V be an isolated vertex in Q (in this case
jV(Q)j 1 (mod 3) andjE(Q)j 0 (mod 3) so such an x exists) and let (V nfxg;B2) be a
cover of Kn 1 with excess Q. By Theorem 5.1, let (V;B3) be a maximum packing of Kn with
leave Q0 consisting of a K1;3 and n 42 independent edges, where the vertex set of the K1;3 is
fw;x;y;zg V with y being the vertex of degree 3. Then (V;B1[B2[B3[ffx;ai;bigj
fai;bigis an independent edge in Q0g[ffx;y;zg;fx;y;wgg) is the required decomposition.
Case 4: = 2 and n 0;2 (mod 6)
First suppose Q consists entirely of 2-cycles and isolated vertices. HencejE(Q)jis even,
and by Condition (2),jE(Q)j 0 or 1 (mod 3) when n 0 or 2 (mod 6) respectively (recall
= 2 in this case). Hence jE(Q)j 0 or 4 (mod 6) when n 0 or 2 (mod 6) respectively
and thus the number of isolated vertices in Q is equivalent to 0 or 4 (mod 6) when n 0 or 2
(mod 6) respectively. If Q contains no isolated vertices (so n 0 (mod 6)), then by Theorem
5.1, for each k2f1;2glet (V;Bk) be a minimum cover of Kn with the same 1-factor excess.
Then (V;B1[B2) is the required cover. Otherwise Q contains at least 4 isolated vertices,
and this case is handled below by using the observation in the next paragraph.
Note that if Q is a quadratic graph in which there are three isolated vertices, say a;b;
and c, in Q, then Q is a quadratic excess if and only if Q[ffa;bg;fa;cg;fb;cggis a quadratic
excess. If Q contains at least 3 isolated vertices, then add a cycle of length 3 on three of the
isolated vertices to Q.
62
In light of the last two paragraphs, to complete the proof of Case 4 it now su ces to
consider the situation where Q has a cycle c = (v0;v1;:::;vx) of length x + 1 3. Form Q0
from Q by replacing c with c0 = (v1;v2;:::;vx). Note thatjE(Q0)j 2 (mod 3) and 0 (mod 3)
when n 0 and 2 (mod 6) respectively. Further note that v0 =2V(Q0) and that Q0 satis es
the conditions for an excess when = 1 and n0 = n 1 5 (mod 6) and for an excess when
= 1 and n0 = n 1 1 (mod 6). So by Theorem 1.3, let (Vnfv0g;B1) be a cover of Kn 1
with excess Q0.
By Theorem 5.1, let (V;B2) be a maximum packing of Kn with leave a 1-factor F
named to contain the edges fv1;vxg and fv0;dg where d is a vertex for which fv1;vx;dg2
B1. Then (V;(B1 [B2 nffv1;vx;dgg)[ffv0;ai;bigjfai;big2 F nffv1;vxg;fv0;dggg[
ffv0;v1;dg;fv0;v1;vxg;fv0;vx;dgg) is the required cover.
Case 5: > 2 and n 0 (mod 6)
By Condition (1), is even. Hence, by Theorem 5.1, let (V;B1) be a K3-decomposition
of ( 2)Kn. By Condition (2), jE(Q)j 0 (mod 3). Hence, by Case 4, let (V;B2) be a
cover of 2Kn with excess Q. Then (V;B1[B2) is the required cover.
Case 6: > 2 and n 2 (mod 6)
By Condition 1, is even. Let 2f2;4;6g with (mod 6). Note that jE( Kn)j
jE( Kn)j(mod 3) and (mod 2) so Q satis es the necessary conditions for an excess of
Kn precisely when it satis es the necessary conditions for an excess of Kn. By Condition
(3), n 8, so by Theorem 5.1, let (V;B1) be a K3-decomposition of ( )Kn.
If = 2, by Case 4, let (V;B2) be a cover of 2Kn with excess Q.
If = 4 then by Condition 2 jE(Q)j 2 (mod 3). First suppose Q consists only of
2-cycles and isolated vertices. SincejE(Q)j 4 n (mod 6), the number of isolated vertices
in Q must be a multiple of 6. If Q has no isolated vertices, then let Q0 consist of two of the
2-cycles and Q00 consist of the remaining n2 2 2 2-cycles (n 8 in this case). Note that
jE(Q0)j jE(Q00)j 1 (mod 3) so by Case 4, let (V;B02) be a cover of 2Kn with excess Q0
63
and (V;B002) be a cover of 2Kn with excess Q00. Let B2 = B02[B002. Otherwise Q has at least
6 isolated vertices; add a 3-cycle on three of the isolated vertices to Q.
It remains to consider the case where Q has a cycle c = (v0;v1;:::;vx) of length x+1 3.
Form Q0 from Q by replacing c with c0 = (v1;v2;:::;vx). NotejE(Q0)j 1 (mod 3) so by Case
4, let (V;B02) be a cover of 2Kn with excess Q0. By Theorem 5.1, let (V;B002) be a packing of
2Kn with leave ffc1;cxg;fc1;cxgg. Let B2 = B02[B002 [ffc0;c1;cxgg.
If = 6 then jE(Q)j 0 (mod 3). Since n 2 (mod 6), there are at least two vertices,
say v0 and v1 such that v0;v1 =2V(Q). Form Q0 from Q by adding the 2-cycle (v0;v1). Note
jE(Q0)j 2 (mod 3), so by the previous case where = 4, let (V;B02) be a cover of 4Kn with
excess Q0. By Theorem 5.1, let (V;B002) be a packing of 2Kn with leave ffv0;v1g;fv0;v1gg.
Let B2 = B02[B002.
In each case, (V;B1[B2) is the required cover, so the result is proved.
64
Chapter 6
Conclusion
To conclude this dissertation, it seems appropriate to mention some applications of
the work done as well as some future directions of research. Some of the mathematical
applications of the results in this dissertation (such as telling when two 2-fold triple systems
are isomorphic) were already discussed, so at this point, a couple of applications of the
general topic of graph decompositions and structure within them are mentioned in relation
to other topics. One useful application of graph decompositions involves scheduling problems.
For instance, a 1-factorization of K12 would correspond to an 11 week football schedule in
which each team plays each other team exactly once. A structure question related to this
application is whether the schedule could be made so that six xed games, say rivalry games,
appear on the last week of the season. (Incidentally, this can be done.) In terms of more
scienti c applications, there is the following application. In research on viruses, a method
known as the Ouchterlony method tests how antigens interact. Around the edge of a Petri
dish, v ofnantigens are placed where they can di use, and then the interaction of neighboring
antigens is observed. For research purposes, it may be bene cial to have each pair of antigens
appear as neighbors on exactly Petri dishes. This can be modeled mathematically as a v-
cycle-decomposition of Kn. In terms of the research in this dissertation, the topics covered
in Chapter 2 directly correspond to a slight variant of the Ouchterlony method. Suppose
now that there are n + m antigens which are to be placed into two groups, one of size m
and one of size n (for instance one group may share a speci c trait while the other group
may share a di erent trait). It may be desirable to see how two antigens in the same group
interact 1 times while only seeing how antigens in di erent groups interact 2 times. This
65
corresponds to a decomposition of the graph 1Kn_ 2 1Km that was discussed in Chapter
2.
In terms of future research, several problems seem interesting. An original topic for
this dissertation involved nding necessary and su cient conditions for a gregarious K3-
decomposition of 1Km_ 2 1Kn, where in this setting gregarious simply means that each
triple contains two mixed edges and one pure edge. In [13], El-Zanati, Punnim, and Rodger
solved this problem when 1 = 1 and 2 = 2. Little other work has been done on the
subject, although some minor results have been obtained. This would be an interesting
problem to consider, as would the problem of nding necessary and su cient conditions
for a K3-decomposition (not necessarily gregarious) of 1Km_ 2 1Kn when 1 < 2; both
problems seem di cult.
66
Bibliography
[1] A. Bialostocki and J. Sch onheim, Packing and Covering of the Complete Graph with
4-cycles, Canadian Mathematical Bulletin 18 (5) (1975), 703-708.
[2] R.C. Bose and T. Shimamoto, Classi cation and analysis of partially balanced incom-
plete block designs with two associate classes, Journal of the American Statistical As-
sociation 47 (1952) 151 184.
[3] D. Bryant, Hamilton cycle rich two-factorizations of complete graphs, Journal of Com-
binatorial Designs 12 (2) (2004), 147 155.
[4] D. Bryant, D. Horsley and B. Maenhaut, Decompositions into 2-regular subgraphs and
equitable partial cycle decompositions, Journal of Combinatorial Theory. Series B 93
(1) (2005), 67 72.
[5] D. Bryant, D. Horsley, and W. Pettersson, Cycle decompositions V: Complete graphs
into cycles of arbitrary lengths, submitted.
[6] D. Bryant and D. Horsley, An asymptotic solution to the cycle decomposition problem
for complete graphs, Journal of Combinatorial Theory. Series A 117 (8) (2010), 1258
1284.
[7] J. Cha ee and C.A. Rodger, Neighborhoods in Maximum Packings of 2Kn and
Quadratic Leaves of Triple Systems, Jounral of Combinatorial Designs, to appear.
[8] C.J. Colbourn, D.G. Ho man and R. Rees, A new class of group divisible designs with
block size three, Journal of Combinatorial Theory Series A 59 (1) (1992) 73 89.
[9] C.J. Colbourn and A. Rosa, Element neighbourhoods in twofold triple systems, Journal
of Geometry 30 (1) (1987), 36 41.
[10] C.J. Colbourn and A. Rosa, Quadratic excesses of coverings by triples, Ars Combinatoria
24 (1987), 23-30.
[11] C.J. Colbourn and A. Rosa, Quadratic leaves of maximal partial triple systems, Graphs
and Combinatorics 2 (4) (1986), 317-337.
[12] C.J. Colbourn, A. Rosa, and S. Zn am, The spectrum of maximal partial Steiner triple
systems, Designs, Codes and Cryptography. An International Journal 3 (3), (1993),
209 219.
67
[13] S.I. El-Zanati, Narong Punnim, C.A. Rodger, Gregarious GDDs with two associate
classes, Graphs and Combinatorics, 26 (6) (2010), 775-780.
[14] M.K. Fort Jr. and G.A. Hedlund, Minimal coverings of pairs by triples, Paci c Journal
of Mathematics 8 (1958), 709 719.
[15] H.L. Fu and C.A. Rodger, Group divisible designs with two associate classes: n = 2 or
m = 2, Journal of Combinatorial Theory A 83 (1) (1998) 94 117.
[16] H.L. Fu, C.A. Rodger and D.G. Sarvate, The existence of group divisible designs with
rst and second associates, having block size 3, Ars Combinatoria 54 (2000) 33 50.
[17] Haim Hanani, The existence and construction of balanced incomplete block designs,
Annals of Mathematical Statistics, 32 (1961), 361-386.
[18] D.G. Ho man, C.A. Rodger, and A. Rosa, Maximal sets of 2-factors and Hamiltonian
cycles, Journal of Combinatorial Theory. Series B 57 (1) (1993), 69 76.
[19] Thomas P. Kirkman, On a problem in combinations, Cambridge and Dublin Math, J 2
(1847), 191-204.
[20] H. Lenz and G. Stern, Steiner triple systems with given subspaces; another proof of the
Doyen-Wilson-Theorem, Unione Matematica Italiana. Bollettino. A (5), 17 (1) (1980)
109 114.
[21] C.C. Lindner and C.A. Rodger, Design theory, CRC Press, Boca Raton, FL, 2009.
[22] L. McCauley and C.A. Rodger, Hamilton cycle rich 2-factorizations of complete multi-
partite graphs, Graphs and Combinatorics 24 (1) (2008), 47 52.
[23] E. Mendelsohn, N. Shalaby and H. Shen, Nuclear designs, Ars Combinatoria 32 (1991),
225-238.
[24] S. Milici, Minimum coverings of the complete graph with 5-cycles, Journal of Combi-
natorial Mathematics and Combinatorial Computing, 57 (2006), 33-46
[25] N. Pabhapote and N. Punnim, Group divisible designs with two associate classes and
2 = 1, International Journal of Mathematics and Mathematical Sciences (2011).
[26] J. Petersen, Die Theorie der regul aren graphs, Acta Mathematica 15 (1) (1891), 193
220.
[27] C.A. Rodger and S.J. Stubbs, Embedding partial triple systems, Journal of Combina-
torial Theory Series A 44 (2), (1987) 241 252.
[28] E.A. Severn, Maximal Partial Triple Systems, Computer Science Technical Report
172=84, University of Toronto (1984).
[29] J.E. Simpson, Langford sequences: perfect and hooked,Discrete Math 44 (1) (1983)
97 104.
68
**