K4 ? e Designs with a Hole
by
Roxanne Isabell Back
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial fulfillment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
December 13, 2010
Approved by:
Dean Hoffman, Chair, Professor of Mathematics
Chris Rodger, Professor of Mathematics
Curt Lindner, Professor of Mathematics
Abstract
In this paper we look at K4 ?e designs on Kw?v +v. We settle the case when w and v
are of the same parity.
ii
Acknowledgments
Dr. Hoffman, thank you for your patience, guidance, optimism and support. Thank you
for your willingness to share your knowledge and ideas. I have thoroughly enjoyed working
with you and taking your classes. You are a model teacher; one in which I aspire to be like.
Although this dissertation would have been impossible for me without the help and
influence of Dr. Hoffman, there are a series of people and events that clearly led me to
the math program at Auburn University, beginning of course, with my parents. Thank you
for setting me on the path to college and for your love and support during all my years
in school. I thank my father for teaching me about algebra in elementary school and my
aunt Heather for the many Mensa books she gave me as birthday and Christmas gifts. I
would like to thank my 8th grade math teacher who moved me into the advanced math class
which eventually allowed me to take AP Calculus in high school. I thank my college math
professor, Susan Serrano, who on the day I needed to declare a major convinced me to major
in math. Dr. Serrano encouraged me to attend graduate school at Auburn University as she
herself had received her Ph.D. there under Dr. Hoffman.
I would like to thank my son for being a source of joy and inspiration. I thank my
colleagues at Mount Mary College who have been patient and supportive of the completion
of my dissertation. In fact, I need to thank every family member and friend, past and
present, for making me who I am and helping me to get to this place in my life.
iii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 a is even . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 a is odd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 5|d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
iv
List of Figures
1.1 Kd +v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 K4 ?e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Kn?1 + 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Kn?2 + 2 and Kn?3 + 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 Zt ?{1,2}+v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6 Graph H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.7 Block types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1 Bridge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Bridges for (34,16) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 2,3,8 bridge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.1 One class of ? blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Dead Zone for Lemma 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Extra ? block needed in Lemma 4.2 . . . . . . . . . . . . . . . . . . . . . . . 17
5.1 Number of edge colors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 Another construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3 K10t +h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.4 Bridges for Case 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
v
Chapter 1
Introduction
A G-design of H is an edge-disjoint decomposition of H into isomorphic copies of the
graph G. When H is the complete graph on n vertices, H = Kn, it is called a G-design
of order n. The spectrum problem for G, i.e. solving for which values of n there exists a
G-design of order n, has been solved for many graphs G, including all graphs G on less than
6 vertices. [1, 2] A complete graph with a hole of size v, Kn\Kv, is a complete graph on n
vertices where the edges of a complete subgraph of size v have been removed.
Let V be an independent set of vertices of size v. The graph G+v is a graph G where
every vertex in V is adjacent to every vertex in G. So, Kd +v = Kn\Kv where d = n?v.
Kd
... V
Figure 1.1: Kd +v
G-designs with holes of size v partition the edges of Kd + v into edge disjoint copies of
G. These designs were first studied by Doyen and Wilson in 1973 where G = K3. [3]
1
A Steiner Triple System of order v, STS(v), is an ordered pair (S,T), where S is a finite
set of points of size v, and T is a set of 3-element subsets of S called triples, where any two
distinct points lie in exactly one triple. (S1,T1) is a subsystem of (S,T) if, S1 ? S, T1 ? T,
and (S1,T1) is a STS.
Doyen and Wilson?s theorem give the necessary and sufficient conditions of a STS(w)
which contains a STS(v) as a subsystem to be w ? 1 or 3 (mod 6) and v ? 1 or 3 (mod 6)
and w ? 2v + 1. Since the structure of the subsystem plays no role in the design on w, the
subsystem could just be a hole. Thus we have a K3 design on Kw?v + v. These also exist
when w ? v ? 5 (mod 6).
This result has been extended to find G-designs on graphs with holes where G is a cycle
of length at most 14 and a triangle with a pendent edge. [4, 5]
A packing of Kn with a graph G is a triple, (S,T,L), where S is the vertex set of Kn,
T is a collection of edge disjoint copies of G from the edge set of Kn, and L is the collection
of edges in Kn not belonging to one of the copies of G in T. The collection of edges in L is
called the leave. When |L| is as small as possible, (S,T,L) is called a maximum packing of
order n.
We look at the case when G = K4 ? e, the complete graph on four vertices minus
one edge. We will denote a K4 ? e, as shown in Figure 1.2, by any of the quadruples
(a,b,c,d),(a,b,d,c),(b,a,c,d) or (b,a,d,c).
= K4 ? e
a b
c d
Figure 1.2: K4 ?e
In 1977, Bermond and Schonheim showed a K4 ?e design of order n exists if and only
if n ? 0 or 1 (mod 5) and n ? 6. Hoffman, Lindner, Sharry, and Street, in 1993, solved
2
maximum packings of Kn, with K4 ? e. [6] These two results solve the K4 ? e design on
Kd + v when v = 0,1,2,3. (A K4 ? e design of order n can be considered a Kn + 0 or a
Kn?1 + 1.)
Figure 1.3: Kn?1 + 1
The maximum packing paper tells us precisely when Kn has a leave of a single edge or
a triangle. These graphs may be considered a Kn?2 + 2 and Kn?3 + 3 respectively.
Figure 1.4: Kn?2 + 2 and Kn?3 + 3
3
The two main tools we use are difference methods and 1-factors. When d is even let
d = 2t. We will depict Kd as Zt ?{1,2} with all possible edges between the sets (see Figure
1.5). We refer to the edges and vertices in Kd as being upstairs and the vertices in V as
downstairs.
0
1
2
t ? 1
Zt
..
.
...
210 v ? 1
0
1
2
t ? 1
Zt
..
.
V
Figure 1.5: Zt ?{1,2}+v
If a and b are integers, define |b?a|t, the difference of a and b (mod t), to be the smallest
non-negative integer congruent to b?a or a?b (mod t). So, 0 ? |b?a|t ? t/2. The edges
of the complete graph on vertex set Zt are partitioned into differences 1,2,...,?t/2? and the
edge ab is defined to be of pure difference |b?a|t. When t/2 is an integer this is called the
half difference and will generate t/2 edges in each Zt. All other pure differences will generate
t edges in each Zt. Mixed differences describe the distance between vertices in different sets.
Let (x,1) be a vertex in Zt?{1} and let (y,2) be a vertex in Zt?{2}. The mixed difference
between them is y ?x (mod t). There are t mixed differences each consisting of t edges.
Let Dt = {1,2,...,?t/2?}, the set of differences in Zt. If S is a subset of Dt, we define
G[S] to be the graph on t vertices induced by the differences in S. We call x ? Dt a good
difference if t/gcd(x,t) is even.
4
A 1-factor is a perfect matching, i.e. a set of a single edges that contain each vertex
exactly once. When the edges of a graph can be partitioned into a set of 1-factors, this is
called a 1-factorization.
Lemma 1.1 (Stern and Lenz) Let ? negationslash= S ? Dt. G[S] has a 1-factorization if and only
if S contains at least one good difference.
In the proof they use:
Lemma 1.2 Let G be a simple regular graph and G? an isomorphic copy of G. Form the
graph H by adding an edge between each vertex in G and its isomorphic mate in G?. Then
H, the graph shown below, has a 1-factorization.
..
.
..
.
G?
Graph H
..
.
..
.
G
x x?
Figure 1.6: Graph H
To ensure the use of these lemmas is possible while constructing blocks, we will use the
same pure differences in each Zt ? {1} and Zt ? {2} and make sure we have at least one
mixed difference remaining.
Let S,U ? Dt, let T ? Zd. Define the graph G[S,T,U] on vertex set Zt ? {1,2} as
follows: It?s edges are those edges on Zt ? {1} induced by the pure diferences in S, edges
5
on Zt ? {2} are induced by the pure differences in U, and those edges between Zt ? {1}
and Zt ? {2} induced by the mixed differences in T. Since the edges of any single mixed
difference are a 1-factor, Lemma 1.2 implies that G[S,T,S] has a 1-factorization whenever
T negationslash= {?}.
In a K4 ?e design on Kd +v, there are four possible types of blocks, ?,?,?, and ?.
? ? ? ?
Kd
V
Figure 1.7: Block types
Counting the edges of each block type gives us two helpful equations. In Kd, each ?
block contributes one edge, ? blocks 2 edges, ? blocks 3 edges, and ? blocks 5 edges. Let A,B,
?, and ? represent the number of blocks of each respective type. Thus A+2B+3?+5? =
(1/2)d(d?1). Counting the edges contributed by each block type between sets v and d yields
4A+ 3B + 2? = vd. We also know that A,B,?,? ? 0.
In every construction we use Lemma 1.2 to find 1-factors and create ? blocks. Each
1-factor of Kd can be used to create t ??s that will contain all the edges between Kd and
two vertices in V. Suppose a and b are vertices in V. For each xy in a particular 1-factor,
we create the ? block (x,y,a,b).
We will construct many blocks using difference methods (mod t). In the constructions,
all ? and ? blocks will be defined explicitly. Blocks of type ? and ? will most often be
described as base blocks. Base blocks are K4 ? e quadruples, where initial values for the
vertices in Zt will be given. Base blocks represent a set of t total blocks. They are developed
6
(mod t) by taking each vertex that is an element of Zt and adding the integers (mod t). Let
(a,b,c,d) be an ? base block where, a,b ? Zt and c and d are vertices in v. The ? base
block is developed (mod t) by taking all blocks (a + i,b + i,c,d) where 0 ? i ? t ? 1. Let
(x,y,w,z) be a ? base block where x,y,w,z ? Zt. The ? base block is developed (mod t) by
taking all blocks (x+i,y +i,w +i,z +i) where 0 ? i ? t?1.
Let?s consider some necessary conditions for a K4 ? e design on Kd + v. First, the
number of edges K4 ?e must divide the number of edges of Kd +v.
5|d(d+ 2v ?1). (1.1)
Second, v cannot be too large. Each block must use at least one edge upstairs. The number
of blocks must be less than or equal to the number of edges in Kd. This simplifies to
v ? 2(d?1). (1.2)
When d is odd, each vertex in V will be of odd degree. The only block type that uses an
odd number of edges incident to a vertex in V is ?. Each ? block uses 2 edges upstairs and
each vertex in V must be contained in at least one ? block. This gives us another necessary
condition when d is odd:
v ? 2d(d?1)d+ 5 . (1.3)
Although K5+2 satisfies the above three necessary conditions, it was proved in the maximum
packing paper that the design does not exist. Therefore, when d is odd, these conditions are
not sufficient.
When d is odd, 1-factors do not exist. Therefore, many of our constructions do not
apply when d is odd. Thus, the main purpose (of this dissertation) is to settle the case when
d is even, i.e. d = 2t. This is our main theorem:
Theorem 1.1: There exists a K4 ?e design on Kd +v when d is even if and only if
1. 5|d(d+ 2v ?1)
2. v ? 2(d?1) and v negationslash= 2d?3, v negationslash= 2d?4
7
Chapter 2
Recursion
Let W = {(d,v): there exists a K4 ?e design on Kd +v}. Recall we are now assuming
d = 2t.
Part of our proof of the Main Theorem will be by induction on d+v, using the following
Lemma and Theorem:
Lemma 2.1 If (d?x,v +x) and (x,v) ? W then (d,v) ? W.
x
Kd
V
Figure 2.1: Recursion
Proof The union of the blocks from the designs on Kd?x + (v + x) and Kx + v form a
design on Kd +v. square
Let R = {(d,v) : 5|d(d+ 2v ?1), d is even, and v ? 2d?5}.
Theorem 2.1 Let (d,v) ? R and v ? 4/5d ? 17. Then for some x, (d ? x,v + x) and
(x,v) ? R.
Proof The conditions on d,v,x for (d ? x,v + x) and (x,v) ? R simplify to x ? 0 or
3v + 1 (mod 5) and v/2 + 1 ? x ? 1/3(2(d ? 1) ? v)). Since x must also be even, we are
8
guaranteed to find a value of x ? 0 or 3v+1 (mod 5) in the interval if it is at least of length
ten. This is the case when v ? 4/5d?17. square
The alert reader may notice that v is restricted to be less than or equal to 2d?5 rather
than the before mentioned 2(d?1). The reason for this will become apparent in Chapter 5.
Although Theorem 2.1 guarantees an x value for which we may use the recursion to find
a design on (d,v) there are many cases in which v notlessorslnteql 4/5d ? 17 and a viable x value still
exists. In these cases the x value will be stated explicitly.
9
Chapter 3
a is even
To satisfy necessary Condition 1.1, 5 must divide d or d+2v?1. We will first consider
when the latter case is true. This condition is satisfied when v is the maximum value, 2(d?1).
Let a = 1/5(2(d?1)?v) ? 0 and this condition will also be satisfied.
Lemma 3.1 (d,v) ? W when d = 2t, v = 2(d?1)?5a, and a is even.
Proof Let d = 2t. Let A = t(2t?1?5/2a), B = 0, ? = 0, and ? = ta/2.
We require (a/2) ? base blocks. These will be constructed using bridges. Bridges are
produced by listing the mixed differences and taking two connected arcs, the length of which
are pure differences. The bridge
a b c
Figure 3.1: Bridge
represents the ? base block ((0,1),(b,2),(c,2),(b?a,1)). Pure differences 1 through a/2
will be used exactly once in each Zt upstairs.
For example: (34,16), a = 10 requires 5 ? base blocks.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 160
1
3
5
1
3
5
2
4
2
4
Figure 3.2: Bridges for (34,16)
10
The bridge
2 3 8
1
5
Figure 3.3: 2,3,8 bridge
describes the base block ((0,1),(3,2),(8,2),(1,1)) and uses pure differences 1 from
Zt ?{1}, 5 from Zt ?{2} and mixed differences 2,3, and 8.
The odd pure differences between 1 and a/2 form the ? base blocks:
((0,1),(?a/4?+j,2),(2j + 1,1),(3?a/4??j ?1,2)) where 1 ? 2j + 1 ? a/2
The even pure differences between 1 and a/2 form ? base blocks:
((0,1),(3?a/4?+?a/4?+j,2),(2j,1),(3a/2?j + 2,2)) where 2 ? 2j ? a/2.
The ? blocks have used 3a/2 mixed differences and a/2 pure differences. So, |T| =
t? 3a/2 and |S| = ?t/2?? a/2. The graph G[S,{t},S] will form t?a 1-factors and leaves
t?3a/2?1 mixed difference 1-factors.
Therefore we have the required 2t?1?5/2a ? base blocks. A 1-factorization of the re-
maining edges may be found using Lemma 1.2 to create ? blocks using the method described
in Chapter 1.
The half difference may not be used in the construction of ? blocks. We need a/2 <
?d/4?. However, the requirement on mixed differences is more restrictive. The ? block
construction requires the number of mixed differences, when a ? 3, to be at least 3a/2 + 2.
Therefore, d ? 3a+4. All pairs d and a are either covered by this construction, or a special
case of the recursion with values listed below.
11
(38,14) x = 10, (30,8) x = 10, (32,12) x = 10, (26,10) x = 10, (24,6) x = 4, (20,8) x = 10,
(18,4) x = 8, (14,6) x = 4, (12,2) x = 2
square
12
Chapter 4
a is odd
Lemma 4.1 (d,v) ? W when t = 3s and v = 2(d?1)?5a.
Proof The cases where v ? 3 have been previously solved. Lemma 3.1 solves the case
when a is even. We now assume that v > 3 and a is odd.
Let A = t(2t?1?4a+ 3(a?1)/2),B = 2t,? = 0,? = t(a?1)/2.
The ? blocks are constructed using pure differences 1 and 2 and the first 3 vertices in V.
Each ? connects a vertex in V with 3 vertices in Zt. The vertices in Zt can be partitioned
into three parallel classes. Each class contains s disjoint sets of size 3. These sets of size 3,
along with a single vertex in V, will create a ? block using an edge of pure difference 1 and
2. Each of the three classes uses s edges of each difference 1 and 2 therefore exhausting all
2t edges of these differences.
1 2
v
30
copy of Zt ?{1}
Figure 4.1: One class of ? blocks
13
All ? blocks are defined by:
((i,3),(i+3j,1),(i+3j+2,1),(i+3j+1,1)) and ((i,3),(i+3j,2),(i+3j+2,2),(i+3j+1,2))
where 0 ? i ? 2 and 0 ? j ? s?1.
The (a ? 1)/2 ? base blocks are constructed using a similar method as in Lemma 3.1.
In this case however, since pure differences 1 and 2 have been used in the ? blocks, we use
pure differences 3 through (a?1)/2 + 2.
Let ?? = (a?1)/2.
The following are ? base blocks and are developed (mod t):
((0,1),(???/2?+ 1 +j,2),(2j + 1,1),(3???/2?+ 4?j,2)) where 3 ? 2j + 1 ? ?? + 2
((0,1),(3???/2?+???/2?+ 5 +j,2),(2j,1),(3?? + 11?j,2)) where 4 ? 2j ? ?? + 2
The half difference may not be used in the construction of ? blocks. So, we need
(a ? 1)/2 + 2 < ?d/4?. However, the requirement on mixed differences is more restrictive.
The ? block construction requires the number of mixed differences, when a ? 4, (?? ? 2), to
be at least 3?? + 10. Therefore, d ? 3a+ 17.
The shaded region in the following graph, referred to as the dead zone, indicates pairs
(a,d) that are not covered by this construction and are not guaranteed to be covered by the
recursion.
14
17
Dead
Zone
DNE
(7.8,22.5)
a
construction
applies
d
(23.1,86.4)
Theorem 2.1 applies
Figure 4.2: Dead Zone for Lemma 4.1
Several of these cases can be covered by modifying the above the construction to using
only odd pure differences in the ? blocks by replacing the ? base blocks with:
((0,1),(?? + 1 +j,2),(2j + 1,1),(3?? + 4?j,2)) where 1 ? j ? ??
This modification is used for designs on: (54,41), (48,39), (42,37), (36,35), (30,33),(30,23)
and (24,21). The remaining dead zone cases needed for this lemma are:
(60,43): In the main construction above replace ? base blocks with:
((0,1),(8 +j,2),(2j + 1,1),(25?j,2)) where 1 ? j ? 6 and ((0,1),(14,2),(8,1),(22,2))
(42,27): In the main construction above replace the ? base blocks with:
((0,1),(5 +j,2),(2j + 1,1),(16?j,2)) where 3 ? 2j + 1 ? 9
((0,1),(11,2),(6,1),(17,2))
(36,25): In the main construction above replace the ? base blocks with:
((0,1),(4 +j,2),(2j + 1,1),(13?j,2)) where 3 ? 2j + 1 ? 7
((0,1),(9,2),(6,1),(15,2))
(12,7): ? blocks: ((0,3),(5,1),(2,1),(1,1)),((0,3),(3,2),(3,1),(1,2)), ((0,3),(0,1),
15
(4,1),(0,2)),((0,3),(2,2),(5,2),(4,2)),((1,3),(3,1),(0,1),(5,1)),
((1,3),(1,2),(1,1),(5,2)),((1,3),(4,1),(2,1),(4,2)),((1,3),(0,2),(3,2),(2,2)),
((2,3),(1,1),(4,1),(3,1)),((2,3),(2,1),(0,1),(2,2)),((2,3),(5,2),(5,1),(3,2)),
((2,3),(4,2),(0,2),(1,2))
? base block: ((0,1),(2,2),(1,1),(3,2))
Create ? blocks with pure differences 4 and 5 and the remaining four vertices in V.
(6,5): Let {0,1,2,3,4,5} be the vertices of K6.
(1,(0,3),5,0),(4,(0,3),2,3),(2,(1,3),0,1),(5,(1,3),3,4),(3,(2,3),1,2),
(0,(2,3),4,5),(0,3,(3,3),(4,3)),(1,4,(3,3),(4,3)),(2,5,(3,3),(4,3)).
Special cases of the Recursion: (84,51) x = 30, (78,49) x = 28, (72,47) x = 30, (66,45)
x = 26, (60,33) x = 20, (54,31) x = 20, (48,29) x = 18, (42,17) x = 20, (36,15) x = 10,
(30,13) x = 10, (24,11) x = 10, (18,9), x = 8. square
Lemma 4.2 (d,v) ? W when t = 3s+ 1 and v = 2(d?1)?5a.
Proof The cases where v ? 3 have been previously solved. Lemma 3.1 solves the case
when a is even. We now assume that v > 3 and a is odd.
Let A = t(2t?1?4a + 3(a?1))/2, B = 2t,? = 0,? = t(a?1)/2. Similar to Lemma
4.1, s ? blocks are constructed using pure differences 1 and 2 with each of the first 3 vertices
in V. We need one more ?, which will contain vertex (3,3), to exhaust the edges of pure
differences 1 and 2. Mixed difference 0 will then be used to create ? blocks with the first
five vertices in V. These ? blocks will use all remaining edges adjacent to those five vertices
in V. Here are the details:
16
1 2 3 40
copy of Zt ?{1}
V
Figure 4.3: Extra ? block needed in Lemma 4.2
All ? blocks are defined by:
((i,3),(i+3j+2,1),(i+3j,1),(i+3j+1,1)),((i,3),(i+3j+2,2),(i+3j,2),(i+3j+1,2)) where
0 ? i ? 2 and 0 ? j ? s?1. ((3,3),(1,1),(0,1),(t?1,1)) and ((3,3),(1,2),(0,2),(t?1,2)).
Since mixed difference 0 is used in the ? blocks, the ? bridges begin at mixed difference 1.
Let ?? = (a?1)/2.
The following are ? base blocks and are developed (mod t):
((0,1),(???/2?+ 2 +j,2),(2j + 1,1),(3???/2?+ 5?j,2)) where 3 ? 2j + 1 ? ?? + 2
((0,1),(3???/2?+???/2?+ 6 +j,2),(2j,1),(3?? + 12?j,2)) where 4 ? 2j ? ?? + 2
The last blocks to be constructed are ? blocks. First, the remaining edges between the
vertices upstairs and the first five vertices in V will be exhausted. Each vertex upstairs needs
to be connected with two of the five vertices downstairs.
These ? blocks are as follows:
((1,1),(1,2),(2,3),(4,3)),((0,1),(0,2),(1,3),(4,3)),((t ? 1,1),(t ? 1,2),(0,3),(4,3)),((t ?
2,1),(t?2,2),(3,3),(4,3)) and ((j,1),(j,2),(3,3),(4,3)) where 2 ? j ? t?3
All other ? blocks are constructed as described in Chapter one with all vertices v ? 5.
17
The dead zone indicates pairs (a,d) that are not covered by this construction and are not
guaranteed by Theorem 2.1.
We must also ensure that all cases when v ? 5 are covered.
As in Lemma 4.1, many of these cases are covered by the following modification on ?
blocks where only odd pure differences are used.
Use the above construction replacing the ? base blocks with:
((0,1),(?? + 2 +j,2),(2j + 1,1),(3?? + 5?j,2)) where 1 ? j ? ??
This modification works for the following cases: (70,43),(64,41) (62,47), (56,45), (50,43),
(44,31), (38,29), (38,39), (32,27), (32,37), and (26,25).
(14,11):
? base block: ((0,1),(0,2),(3,1),(3,2))
? blocks: ((0,1),(j,3),(5,1),(6,1)),((0,2),(j,3),(5,2),(6,2)) where 1 ? j ? 6
? blocks: ((1,1),(2,2),(0,3),(5,3)),((2,1),(1,2),(0,3),(5,3)),((3,1),(4,2),(0,3),(2,3)),
((2,1),(3,2),(1,3),(6,3)),((3,1),(1,2),(1,3),(6,3)),((4,1),(5,2),(1,3),(3,3)),
((5,1),(4,2),(1,3),(3,3)),((5,1),(6,2),(4,3),(2,3)),((6,1),(5,2),(4,3),(2,3)),
((6,1),(0,2),(5,3),(3,3)),((0,1),(6,2),(5,3),(3,3)),((0,1),(1,2),(6,3),(4,3)),
((1,1),(0,2),(6,3),(4,3)). The two one factors from mixed differences 2 and 5 are then used
to make ? blocks with vertices 7,8,9, and 10 in V.
(20,13): Inthemain constructionabove replace? baseblocks with: ((0,1),(9,2),(4,1),(3,2))
and ((0,1),(4,2),(3,1),(7,2)).
Special cases of the Recursion:
(92,57) x = 40, (86,55) x = 30, (80,53) x = 30, (74,51) x = 30, (68,49) x = 28, (68,39)
x = 30, (62,37) x = 22, (56,35) x = 20, (50,33) x = 20, (44,21) x = 20, (38,19) x = 18,
(32,17) x = 12, (26,15) x = 10, (26,5) x = 10. square
18
Lemma 4.3 (d,v) ? W when t = 3s+ 2 and v = 2(d?1)?5a.
Proof The cases where v ? 3 have been previously solved. Lemma 3.1 solves the case
when a is even. We now assume that v > 3 and a is odd.
Let A = t(2t?1?4a+ 3(a?1)/2), B = 2t, ? = 0, ? = t(a?1)/2
Similar to Lemma 4.1, in each Zt ?{1} and Zt ?{2}, s ? blocks are constructed using
pure differences 1 and 2 with the first 3 vertices in v. We need two more ??s in each Zt?{1}
and Zt ? {2} to exhaust the edges of pure differences 1 and 2. One of which will contain
vertiex (3,3), and the other (4,3). Mixed difference 0 will then be used to create ? blocks
with the first five vertices in V. These ? blocks will use all remaining edges adjacent to those
first five vertices in V. Here are the details:
All ? blocks are defined by:
((i,3),(i+3j+2,1),(i+3j,1),(i+3j+1,1)),((i,3),(i+3j+2,2),(i+3j,2),(i+3j+1,2)) where
0 ? i ? 2 and 0 ? j ? s ? 1. ((4,3),(1,1),(0,1),(t ? 1,1)),((4,3),(1,2),(0,2),(t ? 1,2)),
((3,3),(0,1),(t?1,1),(t?2,1)), and ((3,3),(0,2),(t?1,2),(t?2,2))
Since mixed difference 0 is used in the ? blocks, the ? bridges begin at mixed difference 1.
Let ?? = (a?1)/2.
The following are ? base blocks and are developed (mod t):
((0,1),(???/2?+ 2 +j,2),(2j + 1,1),(3???/2?+ 5?j,2)) where 3 ? 2j + 1 ? ?? + 2
((0,1),(3???/2?+???/2?+ 6 +j,2),(2j,1),(3?? + 12?j,2)) where 4 ? 2j ? ?? + 2
Now the remaining edges between the vertices upstairs and the first five vertices in V will
be exhausted. Each vertex upstairs will be connected with two of the first five vertices
downstairs in ? blocks as follows:
((0,1),(0,2),(2,3),(1,3)),((1,1),(1,2),(2,3),(3,3)),((t?1,1),(t?1,2),(1,3),
(0,3)),((t?2,1),(t?2,2),(3,3),(1,3)), ((t?3,1),(t?3,2),(3,3),(4,3)) and
((j,1),(j,2),(3,3),(4,3)) where 2 ? j ? t?4. All other ? blocks are constructed as described
in Chapter one with the remaining vertices v ? 5.
19
This lemma has the same restrictions as Lemma 4.2 and thus has the same dead zone.
The same modification on the ? blocks as in Lemmas 4.1 and 4.2 cover the following dead
zone cases: (46,35), (34,31), (40,33), (62,47), (28,29), and (22,17).
(52,37): Use the main construction for ? and ? blocks. Use the following ? base blocks:
((0,1),(7 +j,2),(2j + 1,1),(20?j,2)) where 1 ? j ? 5 and ((0,1),(14,2),(8,1),(22,2)).
(58,39): Use the main construction of this lemma for ? and ? blocks. The ? base blocks
are((0,1),(15?j,2),(15?2j,1),(16+j,2)) where3 ? 2j+1 ? 13and((0,1),(16,2),(8,1),(24,2)).
(40,23): Usemainconstrcutionabove replacingthe? baseblocks with: ((0,1),(6,+j,2),(2j+
1,1),(17?j,2)) where 1 ? j ? 4 and ((0,1),(12,2),(6,1),(18,2)).
(28,19): Use the main construction of this lemma for ? and ? blocks. The ? base blocks
are ((0,1),(5,2),(3,1),(10,2)),((0,1),(6,2),(5,1),(9,2)), and ((0,1),(4,2), (8,1),(12,2)).
Special cases of the Recursion: (76,45) x = 30, (52,27) x = 20, (46,25) x = 16, (34,21)
x = 14, (34,11) x = 10, (28,9) x = 8, (22,7) x = 10, (16,5) x = 6. square
20
Chapter 5
5|d
Lemma 5.1 When d is even, 5|d, and v = 2d?3 or v = 2d?4 a K4 ?e design does not
exist, on Kd +v.
? ? ? ?
2 1 1
1
0 0
0
0 0
0 0Kd
V
Figure 5.1: Number of edge colors
Proof Assign each vertex in V a unique color. We then assign colors to the edges upstairs
in accordance with the block type and vertices downstairs as follows: Each edge upstairs in
an ? block will be assigned two colors. These are the colors of the two vertices in V that are
contained in the ? block. Each edge upstairs in a ? block will be assigned the one color of
the vertex v contained in the ? block. Let e be the edge in a ? block that is incident to both
vertices upstairs that are adjacent to the vertex in v. Color e the same color as the vertex
in V. The other two edges in a ? block and all edges in a ? block will not be assigned colors.
Let p be the number of edges upstairs that are assigned two colors. Let q be the number
of edges upstairs that are assigned one color in ? blocks. Let r be the number of pairs of
one colored edges in ? blocks and s is the number of uncolored edges upstairs.
21
Counting edges upstairs at a particular vertex we get the equation d?1 = p+q+2r+s.
Counting colors at each a vertex upstairs we get v = 2p + q + r. From necessary Condition
1.2 we know that 2(d?1)?v ? 0. Call this value the deficiency.
The deficiency, 2(d?1)?v = q + 3r + 2s.
Case 1: The deficiency = 1 = q + 3r + 2s.
Thus, q = 1, r = s = 0. Since this is the only possible combination, all vertices upstairs
must have this coloring. However, the single one colored edge (q = 1) cannot come from a
? block because there are no uncolored edges (s = 0). The single one colored edge cannot
come from a ? block because there are no pairs of single colored edges (r = 0). The other
block types do not contain single one colored edges. Therefore, the deficiency cannot equal
one and there does not exist a K4 ?e design when v = 2d?3.
Case 2: The deficiency = 2 = q + 3r + 2s.
There are two possibilities, 2 = q and r = s = 0 or q = r = 0 and s = 1. In either case,
since r = 0, there are no ? blocks. The two single one colored edges (q = 2) must come from
? blocks. However, a ? block cannot exist unless there is a vertex with 2 uncolored edges
and s = 0 or 1. Therefore, the deficiency cannot equal two and there does not exist a K4 ?e
design when v = 2d?4. square
Lemma 5.2 If (d,v) ? W then (dk,v + 2d(k ?1)) ? W.
Proof Create the graph Kdk + v by taking each vertex upstairs in Kd + v with a (d,v)
design and blowing it up by k. Then k copies of the (d,v) design will exhaust all edges
incident to vertices in V and (kd(d?1)2 ) edges upstairs. By Lemma 1.2 the remaining edges
upstairs can be partitioned into d(k ? 1) one-factors. For each one-factor, add a pair of
vertices downstairs and the appropriate edges to obtain Kdk + (v + 2d(k ? 1)). Now each
one-factor and pair of vertices downstairs can be partitioned into ? blocks. square
22
Ka,b,c is a complete multipartite graph. Let S = {(a,b,c): there exits a K4 ? e design
on Ka,b,c.
Lemma 5.3 If (a,b,c) ? S, (b,v) and (c,v) ? W then (b+c,a+v) ? W.
b
a
c b c
v a
Figure 5.2: Another construction
Proof The union of the blocks from the designs (a,b,c), (b,v), and (c,v) create a (b +
c,a+v) design. square
Lemma 5.4 (10,10,10) ? S.
Proof The following blocks form (10,10,10):
((0 +i,a),(0 +i,b),(2 +i,c),(3 +i,c))
((0 +i,b),(0 +i,c),(2 +i,a),(3 +i,a))
((0 +i,c),(0 +i,a),(2 +i,b),(3 +i,b))
((5 +i,a),(0 +i,b),(1 +i,c),(6 +i,c))
((5 +i,b),(0 +i,c),(1 +i,a),(6 +i,a))
((5 +i,c),(0 +i,a)(1 +i,b),(6 +i,b)), for 0 ? i ? 9 square
23
Lemma 5.5 (d,v) ? W when 5|d, and v ? 2(d?1) and v negationslash= 2d?3, v negationslash= 2d?4.
Proof Since 5|d and d is even, let d = 10t.
Case 1: t = 1
Previously solved cases: v = 1,2,3 [6], v = 4 [6, example 4.2], v = 7 [6, example 4.5],
and v = 9 [6, example 4.9]
When v = 8,13 and 18, v = 2(d?1)?5a and are solved in Chapters 3 and 4.
(10,4): Let {1,2,3,4,5,6,7,8,9,10} be the vertices upstairs (5,6,(2,3),(3,3)),
(4,10,(2,3),(3,3)), (3,9,(2,3),(3,3)), (2,8,(2,3),(3,3)), (1,7,(2,3),(3,3)), ((1,3),3,1,7),
(1,4,2,8),(2,5,3,9),(3,(0,3),4,10),(4,7,5,6),(5,8,(0,3),(1,3)), ((0,3),9,7,1),(7,10,8,2),
(8,6,9,3), (9,(1,3),10,4),(10,1,6,5),(6,2,(1,3),(0,3)).
(10,5): Let {0,1,2,3,4,5,6,7,8,9} be the set of vertices upstairs. ((1,3),1,0,2),
(9,3,(1,3),1), ((1,3),6,5,7), (8,3,(1,3),6), (7,1,5,8), (7,2,3,4), (6,2,0,3), (3,4,5,0),
(8,9,5,0), (1,4,(2,3),(3,3)), (6,9,(2,3),(3,3)), (6,1,(0,3),(4,3)), (0,4,(0,3),(4,3)),
(5,2),(2,3),(3,3)), (8,3,(2,3),(3,3)), (7,0,(2,3),(3,3)), (5,0,(0,3),(4,3)), (7,3,(0,3),(4,3)),
(8,2,(0,3),(4,3)). [7, page 12]
(10,6): Z5 ? {1} ? (0,3) and Z5 ? {2} ? (0,3) each form a copy of K6 and can be de-
composed in 6 blocks. The following blocks complete the design. ((1,3),(0,1),(0,2),(1,2)),
((2,3),(1,1),(1,2),(2,2)), ((3,3),(2,1),(2,2),(3,2)), ((4,3),(3,1),(3,2),(4,2)),
((5,3),(4,1),(4,2),(0,2)), ((1,3),(2,2),(4,1),(3,1)), ((2,3),(3,2),(0,1),(4,1)),
((3,3),(4,2),(1,1),(0,1)), ((4,3),(0,2),(2,1),(1,1)), ((5,3),(1,2),(3,1),(2,1)),
((0,1),(2,2),(4,3),(5,3)), ((1,1),(3,2),(1,3),(5,3)), ((2,1),(4,2),(1,3),(2,3)),
((3,1),(0,2),(2,3),(3,3)), ((4,1),(1,2),(3,3),(4,3)).
(10,7): Let{1,2,3,4,5,6,7,8,9,10}betheverticesupstairs. ((0,3),7,5,8), ((0,3),10,6,9),
(1,2,(0,3),(4,3)), (3,4,(0,3),(1,3)), ((1,3),1,7,9), ((1,3),2,10,8),(6,5,(1,3),(2,3)),
((2,3),8,1,3), ((2,3),9,2,4),(7,10,(2,3),(3,3)), ((3,3),4,1,5), ((3,3),3,2,6),(8,9,(3,3),(4,3)),
((4,3),5,3,10), ((4,3),6,4,7), ((5,3),5,1,8),(3,10,(5,3),1), ((5,3),6,2,9),(4,7,(5,3),2),
((6,3),5,2,9),(3,7,(6,3),9), ((6,3),6,1,8),(4,10,(6,3),8).
24
(10,9): Let {1,2,3,4,5,6,7,8,9,10} be the vertices upstairs. ((0,3),1,4,10),
((0,3),7,2,3), (5,8,(0,3),(2,3)), (6,9,(0,3),(1,3)), ((1,3),1,2,8),
((1,3),5,3,4), (7,10,(1,3),(2,3)), ((2,3),1,3,9), ((2,3),6,2,4),(1,5,(3,3),(4,3)),
(2,8,(3,3),(4,3)), (3,4,(3,3),(4,3)), (6,7,(3,3),(4,3)), (9,10,(3,3),(4,3)),
(1,6,(5,3),(6,3)), (2,4,(5,3),(6,3)), (3,9,(5,3),(6,3)), (5,7,(5,3),(6,3)),
(8,10,(5,3),(6,3)), (1,7,(7,3),(8,3)), (2,3,(7,3),(8,3)), (4,10,(7,3),(8,3)),
(8,9,(7,3),(8,3)), (2,5,9,10),(3,6,8,10),(4,7,8,9).
(10,10): Let {0,1,2,3,4,5,6,7,8,9} be the set of vertices upstairs.
((i,3),i,8,9) for 0 ? i ? 7, ((0,3),7,2,1), ((6,3),5,0,7),((7,3),6,1,0),(0,1,(4,3)(6,3)),
(1,2,(5,3),(7,3)),(2,2,(0,3),(6,3)),(3,4,(1,3),(7,3)),(4,5,(0,3),(2,3)),
(5,6,(1,3),(3,3)),(6,7,(2,3),(4,3)),(7,0,(5,3)(3,3)),
(8,9,(8,3),(9,3)),(0,4,(8,3),(9,3)),(1,5,(8,3),(9,3)),
(2,6,(8,3),(9,3)),(3,7,(8,3),(9,3)).
(10,11): Put a (5,1) deisgn on Z5 ?{1}?(0,3) and Z5 ?{2}?(0,3). Then use mixed
differences 0 through 4 to create ? blocks with the last 10 vertices in V.
(10,12): Let {1,2,3,4,5,6,7,8,9,10} be the vertices upstairs. ((i,3),i,7,8) for 1 ? i ?
6, ((j + 1,3),j,9,10) for 1 ? j ? 5, ((1,3),6,9,10),
(1,6,(3,3),(4,3)),(1,2,(5,3),(6,3)),(3,6,(2,3),(3,3)),(3,4,(1,3),(6,3)),
(1,5,(7,3),(8,3)),(4,6,(7,3),(8,3)),(2,3,(7,3),(8,3)),(7,8,(7,3),(8,3)),
(9,10,(7,3),(8,3)),(1,3,(11,3),(12,3)),(2,4,(11,3),(12,3)),(5,6,(11,3),(12,3)),
(7,9,(11,3),(12,3)),(8,10,(11,3),(12,3)),(1,4,(9,3),(10,3)),(2,6,(9,3),(10,3)),
(3,5,(9,3),(10,3)),(8,9,(9,3),(10,3)),(7,10,(9,3),(10,3)).
(10,14): ((1,3),(0,1),(4,1),(1,1)),((1,3),(0,2),(4,2),(1,2)),
((2,3),(1,1),(4,1),(2,1)),((2,3),(1,2),(4,2),(2,2)),((3,3),(2,1),(4,1),(3,1)),
((3,3),(2,2),(4,2),(3,2)),((4,3),(3,1),(4,1),(0,2)),((4,3),(3,3),(4,2),(0,1)),
((3,1),(3,2),(1,3),(2,3)),((2,1),(2,2),(1,3),(4,3)),((1,1),(1,2),(3,3),(4,3)),
((0,1),(0,2),(2,3),(3,3)),((3,1),(4,2),(5,3),(6,3)),((2,1),(0,1),(4,3),(6,3)),
25
((0,1),(0,2),(5,3),(6,3)),((4,1),(2,2),(5,3),(6,3)),((3,2),(1,2),(5,3),(6,3)),
((3,1),(2,2),(7,3),(8,3)),((2,1),(0,2),(7,3),(8,3)),((1,1),(3,2),(7,3),(8,3)),
((0,1),(1,2),(7,3),(8,3)),((4,2),(4,1),(7,3),(8,3)),((3,1),(0,1),(9,3),(10,3)),
((2,1),(4,2),(9,3),(10,3)),((1,1),(2,2),(9,3),(10,3)),((4,1),(1,2),(9,3),(10,3)),
((3,2),(1,2),(0,3),(10,3)),((3,1),(1,2),(11,3),(12,3)),((2,1),(3,2),(11,3),(12,3)),
((1,4),(4,2),(11,3),(12,3)),((0,1),(2,2),(11,3),(12,3)),((4,1),(0,2),(11,3),(12,3)),
((3,1),(1,1),(13,3),(14,3)),((0,1),(4,2),(13,3),(14,3)),((4,1),(3,2),(13,3),(14,3)),
((0,1),(4,2),(13,3),(14,3)),((4,1),(3,2),(13,3),(14,3)),((2,2),(0,2),(13,3),(14,3)),
((2,1),(1,2),(13,3),(14,3)).
(10,15): ((1,3),(4,1),(0,1),(1,1)),((1,3),(4,1),(0,2),(1,1)),
((2,3),(3,1),(0,1),(1,1)),((2,3),(3,2),(0,2),(1,2)),((3,3),(2,1),(0,1),(1,1)),
((3,3),(2,2),(0,2),(1,2)),((0,1),(0,2),(6,3),(7,3)),((1,1),(1,2),(6,3),(7,3)),
((2,1),(2,2),(4,3),(7,3)),((3,1),(3,2),(6,3),(7,3)),((4,1),(4,2),(5,3),(7,3)),
((3,1)(2,1),(1,3),(5,3)),((3,2),(2,2),(1,3),(5,3)),((4,1),(2,1),(2,3),(6,3)),
((4,2),(2,2),(2,3),(6,3)),((3,1),(4,1),(3,3),(4,3)),((3,2),(4,2),(3,3),(4,3)),
((0,1),(1,1),(4,3),(5,3)),((0,2),(1,2),(4,3),(5,3)). Use mixed differences 1,2,3, and 4 to
make ? blocks with vertices 8 through 15 in V.
We will now assume that t > 1.
(The edges of pure difference t and 2t and mixed differences 0, t, 2t, 3t, and 4t produce
t copies of K10 upstairs. This set of edges is replaced with K10 +h in Lemma 5.2).
26
0
t
2t3t
4t
0
t
2t3t
4t
h
Figure 5.3: K10t +h
For 20t ? 20 ? v ? 20t ? 2, use (10,h), 0 ? h ? 18, in Lemma 5.2. In these designs,
d(k ? 1) one-factors are used to make ? blocks with 2d(k ? 1) vertices downstairs. For
every 5 sets of one-factors that we can turn into ? blocks, we reduce the number of vertices
downstairs by 10. For each ? base block we can construct, we can cover the values of v where
20t?20?10? ? v ? 20t?2?10?. Here are the details:
Case 2: t is odd
? base blocks:
((0,1),(2t?1?i,2),(2t?2?2i,1),(2t + 1 +i,2)) where 0 ? i ? t?2
((0,1),(3t+ 2,2),(1,1),(3t + 3,2)),
((0,1),(4t+ 1 +j,2),(3 + 2j,1),(5t?1?j,2)) where 0 ? j ? t?32 ?1
27
4
2
2t ? 4
2t ? 2
2t 3tt0
3t
5
3
t ? 2
t ? 4
4t 5t ? 1
1 1
Figure 5.4: Bridges for Case 2
This produces (t + t?32 ) ? base blocks and v ? 5t?5, which is small enough to overlap
with the recursion when t ? 3. As shown in figure 5.4 the construction of the odd ? blocks
requires t ? 6. Modifications on this construction to cover t = 3 and 5 will be described
following Case 3.
Case 3: t is even
The even pure difference construction of ? blocks as described in Case 2 produces (t?1)
? base blocks. When t is even, there are an odd number of ? base blocks produced and the
bridge when i = t?22 will look like
x x
where x = t. Since the pure difference t has already been used, this ? block may not be
constructed.
? base blocks:
((0,1),(2t?1?i,2),(2t?2?2i,1),(2t+1+i,2)) where 0 ? i < t?22 and t?22 < i ? t?2
((0,1),(3t+ 2,2),(1,1),(3t + 3,2)),
28
((0,1),(4t+ 2 +j,2),(3 + 2j,1),(5t?1?j,2)) where 0 ? j ? t?42 ?1
This construction of the ? blocks requires t ? 6. However, (t ? 1 + t?42 ) ? base blocks are
produced which will allow v to overlap with the recursion when t > 8. Modifications on this
construction and special cases of the recursion to cover t = 2,4,6,8 will be described.
Here are the details for t = 2,3,4,5, 6, and 8.
(20,v):
For 20 ? v ? 38 use Lemma 5.2 and (10,h) where 0 ? h ? 18. When v = 18, Lemma
3.1 applies. When v = 13, Lemma 4.3 applies.
v = 10,11,12,14,15,16,17 and 19:
Use Lemma 5.3 where (a,b,c) = (10,10,10) and v = 0,1,2,4,5,6,7 and 9 respectively.
v = 9:
Use the Recursion with x = 8.
4 ? v ? 8:
Use the Recursion with x = 10.
(30,v):
Modifytheaboveconstructionusing? baseblocks((0,1),(4,2),(2,1),(8,2)) and((0,1),(5,2),
(4,1),(7,2)) to cover values 20 ? v ? 58.
v = 19:
Use the Recursion with x = 13.
v = 18: Lemma 3.1 applies.
v = 16 and 17:
Use the Recursion with x = 14 and 12 respectively.
11 ? v ? 15:
Use the Recursion with x = 10.
v ? 10: The Recursion applies.
(40,v):
For 20 ? v ? 78 modify the above construction using ? base blocks:
29
((0,1),(2,2),(1,1),(3,2)), ((0,1),(0,2),(3,1),(14,2)),
((0,1),(10,2),(5,1),(13,2)), ((0,1),(17,2),(2,1),(19,2)).
v = 19: Use the Recursion with x = 13.
v ? 18: The Recursion applies.
(50,v):
For 20 ? v ? 98 use the above construction replacing the ? base blocks with:
((0,1),(6,2),(2,1),(14,2)), ((0,1),(7,2),(4,1),(13,2)),((0,1),(8,2),(6,1),(12,2)), ((0,1),(9,2),
(8,1),(11,2)),((0,1),(18,2),(1,1),(21,2)),((0,1),(22,2),(3,1),(23,2)).
v ? 20: The Recursion applies.
(60,v):
For 30 ? v ? 118 use the above construction with the additional ? base block:
((0,1),(15,2),(12,1),(27,2)).
v < 30: The Recursion applies.
(80,v):
For 50 ? v ? 158: Lemma 5.5 applies.
v = 49,48: Use the Recursion with x = 30.
v ? 47: The Recursion applies. square
30
Chapter 6
Conclusion
Theorem 6.1 There exists a K4 ?e design on Kd +v when d is even if and only if
1. 5|d(d+ 2v ?1)
2. v ? 2(d?1) and v negationslash= 2d?3, v negationslash= 2d?4
Proof This is a direct result from Lemmas 3.1, 4.1, 4.2, 4.3, 5.1 and 5.5. square
To solve the case when d is odd, new techniques will need to be applied. The use of
difference methods in the construction of ? blocks and the use of 1-factors is not applicable
when d is even. However, Lemma 2.1, the Recursion, and Lemma 5.3 are true regardless of
the parity of d and may be useful tools in the future.
31
Bibliography
[1] J. C. Bermond, and J. Scaonhein, G-Decomposition of Kt, where G has Four Vertices
or Less. Discrete Mathematics 19 (1977) 113-126.
[2] J. C. Bermond, C. Huang, A. Roda and D. Sotteau, Decomposition of Complete Graphs
into Isomorhphic Subgraphs with Five Vertices. Ars Combinatoria 10 (1980) 211-254.
[3] J. Doyen and R. M. Wilson, Embedding of Steiner Triple Systems. Discrete Mathematics
5 (1973) 229-239.
[4] D. E. Bryant, C. A. Rodger and E. R. Spicer, Embedding m-cycle systems, and incom-
plete m-cycle systems: m ? 14 Discrete Mathematics 171 (1997) 55-75.
[5] D. G. Hoffman and K. S. Kirkpatrick, Another Doyen-Wilson Theorem. Ars Combina-
toria 54 (2000), pp 87-92.
[6] D. G. Hoffman, C. C. Lindner, Martin J. S. Harry and Anne Penfold Street, Maximum
Packing of Kn with copies of K4 ?e. Aequationes Mathematicae 51 (1996) 247-269.
[7] E. J. Billington, C. C. Lindner, E. S. Yazici, The triangle intersection problem for K4?e
designs. Utilitas Mathematica 73 (2007) 3-21.
32