Enclosings of Small Cycle Systems
Except where reference is made to the work of others, the work described in this
dissertation is my own or was done in collaboration with my advisory committee. This
dissertation does not include proprietary or classifled information.
Nicholas Newman
Certiflcate of Approval:
Peter D. Johnson, Jr.
Professor
Mathematics and Statistics
Chris Rodger, Chair
Scharnagle Professor
Mathematics and Statistics
Dean Hofiman
Professor
Mathematics and Statistics
George T. Flowers
Dean
Graduate School
Enclosings of Small Cycle Systems
Nicholas Newman
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
May 9, 2009
Enclosings of Small Cycle Systems
Nicholas Newman
Permission is granted to Auburn University to make copies of this dissertation at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Nicholas Newman, son of Larry and Myong Newman, was born on October 7, 1981 on
MacDill Air Force Base in Florida. He has three older brothers Tony, Ray, and Brady. He
graduated from Carroll High School in 2000. He then attended Troy State University and
graduated with a Bachelor of Science degree in Mathematics in May 2004. He enrolled in
Graduate School at Auburn University the following August.
iv
Dissertation Abstract
Enclosings of Small Cycle Systems
Nicholas Newman
Doctor of Philosophy, May 9, 2009
(M.A.M, Auburn University, 2006)
(B.S., Troy State University, 2004)
54 Typed Pages
Directed by Chris Rodger
In 2003 Hurd and others considered the problem of enclosing a triple system TS(v;?)
in a triple system TS(v + s;? + m) [13, 14], focusing on smallest possible enclosings. In
the second chapter, their result is generalized using a new proof based on a graph-theoretic
technique.
Four constructions are presented; they are exhaustive in the sense that, for each possible
congruence of the parametersv orsandm, at least one construction can be applied to obtain
an enclosing. In each construction, the value of v or s is restricted.
This naturally led to the question of whether or not a ?-fold 4-cycle system could be
enclosed for all possible values. In the third chapter, we completely solve the enclosing
problem by construction for ?-fold 4-cycle systems for u ? 2.
v
Acknowledgments
I would flrst like to thank Dr. Chris Rodger for his invaluable knowledge, guidance,
and patience. I am indebted to him. I would also like to thank Drs. Dean Hofiman and
Pete Johnson and the rest of the Auburn faculty for guiding me throughout my graduate
career.
I would also like to thank Dr. Ken Roblee whose undergraduate research project led
me to this point, and Holly for being particularly understanding during the writing of this
dissertation. Finally, I would like to thank my family -Larry, Myong, Tony, Ray, and Brady,
and my friends for their love and support throughout my life.
vi
Style manual or journal used Journal of Approximation Theory (together with the style
known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speciflcally LATEX)
together with the departmental style-flle aums.sty.
vii
Table of Contents
List of Figures ix
1 Introduction 1
1.1 Deflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Enclosings of 3-Cycle Systems 5
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Enclosings when jSj is (?+m)-admissible . . . . . . . . . . . . . . . . . . . 8
2.3 Enclosings when jSj+1 is (?+m)-admissible . . . . . . . . . . . . . . . . . 11
2.4 Enclosings when jSj+3 is (?+m)-admissible . . . . . . . . . . . . . . . . . 13
2.5 Other Enclosings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.6 Large Enclosings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Enclosings of 4-Cycle Systems 27
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Enclosings when u ? 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Enclosings when u = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4 Conclusions 42
Bibliography 44
viii
List of Figures
1.1 K5 and 2K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 1-factor of K4 (in bold) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Steiner Triple System of order 7 . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1 Using the 1-factor in Theorem 2.5 Case 1 . . . . . . . . . . . . . . . . . . . 10
2.2 Using the 2-factor (not necessarily connected) in Theorem 2.5 Case 2 . . . . 10
2.3 Idea of the construction of Theorem 2.6 Case 2 . . . . . . . . . . . . . . . . 13
2.4 Idea of the construction of Theorem 2.7 . . . . . . . . . . . . . . . . . . . . 15
2.5 Example bordering the bounds of Theorem 2.3 . . . . . . . . . . . . . . . . 23
3.1 4-cycle decomposition of K9 . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Connecting the Euler Tour (2 4-cycles constructed as an example) . . . . . 40
3.3 Constructing 4-cycles from P2?s . . . . . . . . . . . . . . . . . . . . . . . . . 41
ix
Chapter 1
Introduction
1.1 Deflnitions
A complete graph on v vertices, denoted by Kv, is a simple graph in which there is
an edge between every pair of its vertices. A ?-fold complete graph on v vertices, denoted
?Kv, is a multi-graph in which there are ? edges between every pair of its vertices.
Figure 1.1: K5 and 2K5
A k-factor of a graph G is a spanning k-regular subgraph of G. This means that the
k-factor is incident to each vertex of G and that each vertex has the same degree k in the
subgraph. In particular, a 1-factor of a graph G would be a spanning subgraph of G of
independent edges.
Let Zn = f0;1;:::;n ? 1g. A k-cycle (v0;v1;:::;vk?1) is a graph with vertex set
fvi j i 2 Zng and edge set ffvi;vi+1g j i 2 Zng (reducing the subscript modulo n). A
k-cycle system of a multi-graph G is an ordered pair (V;C) where V is the vertex set of G
and C is a set of k-cycles, the edges of which partition the edges of G. A k-cycle system of
Kn is known in the literature as a k-cycle system of order n.
1
Figure 1.2: 1-factor of K4 (in bold)
Figure 1.3: Steiner Triple System of order 7
2
A k-cycle system of ?Kv is conveniently denoted by kCS(v;?). A 3CS(v;1) is more
commonly known as a Steiner triple system, or STS(jVj) for short. It is clear that if there
exists a kCS(v;?) then:
(i) ?(v ?1) is even,
(ii) k divides ?v(v ?1)=2, and
(iii) v ? k.
For each k, v is said to be ?-admissible if (i)-(iii) are satisfled.
A kCS(v;?), (V;C), is said to be enclosed in a kCS(w;? + m), (W;P), if V ? W,
C ? P, and m ? 1. In the related situation when the number of vertices increases but the
index does not (i.e. m = 0), then the kCS(v;?) is said to be embedded in the larger system.
All other deflnitions used can be found in Lindner and Rodger?s, \Design Theory," [17]
or West?s \Introduction to Graph Theory" [22].
1.2 History
Doyen and Wilson [7] solved the embedding problem for Steiner triple systems, answer-
ing the question: for which values of w can a STS(v) always be embedded in a STS(w)?
The generalization of this question has also been answered for cycles of lengths greater than
3 in many cases [3, 12]. These have become known as Doyen-Wilson problems.
A similar problem occurs when discussing a partial k-cycle system. A partial k-cycle
system of order n and index ? is a subgraph of ?Kn the edges of which are partitioned into
k-cycles. Numerous results on embeddings and enclosings of k-cycle systems and partial
k-cycle systems can be seen in various papers including Treash [21] who produced a flnite
embedding of a partial triple system. Further efiorts were done by Lindner [15], and by
Andersen, Hilton, and Mendelsohn [1] improving the bounds until recently Bryant and
Horsley constructed best possible embeddings of partial STS(v)?s into STS(w)?s for all
admissible w ? 2v+1 [4]. The enclosing problem for 3-cycle systems is yet to be completely
solved. We address this subject in this dissertation being motivated by the work done by
Munson, Hurd and Sarvate [13, 14]; see Chapter 2. Work on embedding 4-cycle systems
3
and partial 4-cycle systems have been addressed by Horak and Lindner [11], and Horton,
Lindner, and Rodger [12] among others. Chapter 3 addresses the enclosings of ?-fold 4-cycle
systems.
4
Chapter 2
Enclosings of 3-Cycle Systems
We begin with constructions that will enclose ?-fold triple systems. Four constructions
are presented; they are exhaustive in the sense that, for each possible congruence of the
parameters v or s and m, at least one construction can be applied to obtain an enclosing.
In each construction, the value of v or s is restricted.
We begin with some deflnitions that are more speciflc to enclosing ?-fold triple systems.
2.1 Preliminaries
A (partial) balanced incomplete block design, or (partial) BIBD(v;k;?), is an ordered
pair (V;B) where B is a collection of subsets of a set V of order v, each subset being called
a block, such that all blocks have size k and each pair of symbols in V appears together in
(at most) ? blocks. When k = 3, a BIBD(v;3;?) is often called a triple system, a TS(v;?).
In this section, we allow repeated elements in all sets, except for blocks, and use X  Y
to denote the fact that each element occurs at least as many times in Y as it does in X.
The TS(v;?), (V1, B1), is said to be enclosed in the TS(v +s, ?+m), (V2, B2), if V1  V2
and B1  B2.
Over the past flve years, Hurd, Munson, and Sarvate [13, 14] have addressed the subject
of minimal enclosings of triple systems proving two results:
Theorem 2.1. [13] Each TS(v;?) can be minimally enclosed into a TS(v + 1;? + m) in
the case where m > 0 is as small as possible.
In the second paper, they presented partial results for the enclosing of a TS(v;?) into
a TS(v + s;? + 1) where s is as small as possible [14]. Theorem 2.1 is an immediate
corollary of our approach (see Corollary 2.1). Their latter results head in a related but
5
difierent direction, considering the problem when the index is increased by exactly 1. They
considered the problem related to the existence of enclosings of triple systems for any v,
with 1 ? ? ? 6, of BIBD(v;3;?) into a BIBD(v + s;3;? + 1) for minimal positive s. The
non-existence of enclosings for otherwise suitable parameters is proved, and the di?cult
cases for even ? were considered. They completely solve the case for ? ? 3 and ? = 5, and
partially complete the cases ? = 4 and 6. In some cases a 1-factorization of a complete
graph or complete n-partite graph is used to obtain the minimal enclosing. A list of open
cases for ? = 4 and ? = 6 was also included [14].
We should make note of a new necessary condition found in [13] regarding enclosings of
block designs. Of particular interest in this dissertation is the application to triple systems.
Theorem 2.2. [13] A necessary condition for enclosing X = BIBD(v;3;?) into Y =
BIBD(v +s;3;?+m) is that
s ? 1+v2 ?
p(1+v)2(?+m)2 ?4mv(v ?1)(?+m)
2(?+m) or
s ? 1+v2 +
p(1+v)2(?+m)2 ?4mv(v ?1)(?+m)
2(?+m) :
This theorem is presented in the context that the following theorems in Chapter 3
provide constructions for enclosings that do not encompass all possible values of v;s;?; and
m due to additional restrictions placed on the bounds presented above.
Here, we present a new construction of enclosings making extensive use of a graph-
theoretic result. A partial triple system of index ? is said to be equitable if for each pair
of symbols v and w, jt(v) ? t(w)j ? 1, where t(v) is the number of triples containing v.
If T = (V;B) is a partial triple system of index ?, then let G(T) be the graph with the
vertex set V in which the vertices x;y 2 V are joined by z edges if and only if the pair
fx;yg occurs in ??z triples in B. The edges in G(T) represent the pairs that need to be
placed in triples to boost T to a TS(v;?). Fu and Rodger [8] found necessary and su?cient
6
conditions for the existence of an equitable triple system T of index ? for which G(T) has,
for example, a 1-factorization, proving the following results.
Theorem 2.3. [8] Suppose that ? ? 1 and ? ? 3. Then
i) there exists an x-regular graph H on ? vertices and of multiplicity at most ? whose
edges can be partitioned into triples, such that
ii) ?K? ?E(H) has a 1-factorization
if and only if
(a) 0 ? x ? ?(? ?1),
(b) if x > 0 then 3 divides x?,
(c) if x < ?(? ?1) then 2 divides ?, and
(d) 2 divides x.
They also proved the following companion result.
Theorem 2.4. [8] Suppose that ?;? ? 1 :
(a) 0 ? x ? ?(? ?1),
(b) 3 divides x?, and
(c) ?(? ?1) and x are even.
Then there exists an x-regular multigraph H of maximum multiplicity no greater than
? with ? vertices whose edges can be partitioned into triples, such that ?K? ?E(H) has a
2-factorization.
We discuss some terminology and history before moving on to the enclosings.
Table 2.1 [17] below provides the necessary and su?cient conditions for the existence
of ?-fold triple systems. An integer v is said to be ?-admissible if:
(i) v 6= 2
(ii) 3 divides ?v(v ?1)/2, and
(iii) ?(v ?1) is even.
7
This deflnition is made in the context of the existence of triple systems, conditions
(i)-(iii) being obvious necessary conditions for their existence. An interpretation of Table
2.1 [17] is that there exists a TS(v;?) if and only if v is ?-admissible.
? Restrictions on v
0 (mod 6) v 6= 2
1, 5 (mod 6) 1, 3 (mod 6)
2, 4 (mod 6) 0, 1 (mod 3)
3 (mod 6) All odd v
Table 2.1
Using Table2.1 as aguideline, weconstruct enclosings of aTS(v;?)in aTS(v+s;?+m),
ensuring that for all congruence classes (mod 6) of v;s;? and m at least one construction
is applicable (see Tables 2.2 and 2.3).
2.2 Enclosings when jSj is (?+m)-admissible
In this section we provide our flrst su?cient conditions for the existence of an enclosing.
Theorem 2.5. Let v;?;m, and s be positive integers. Then every TS(v;?) can be enclosed
in a TS(v +s;?+m), if:
(a) s ? m(v ?1)=(?+m), and
(b) both v +s and s are (?+m)-admissible.
Proof Let T = (Zv;B1) be a TS(v;?); so v is ?-admissible. We now add s new vertices
in S = fn1;n2;:::;nsg to form an enclosing (Zv [ S;B0) of T as follows. Let (S;B2) be
a TS(s;? + m) (this exists by assumption (b)). The remaining edges not yet occurring in
triples are therefore the edges in mKv, and the ? + m edges joining each vertex in Zv to
each vertex in S. Then there are mv(v?1)=2+vs(?+m) remaining edges so, since v +s
is (?+m)-admissible, it must be that the number of remaining edges is divisible by 3:
mv(v ?1)=2+vs(?+m) ? 0 (mod 3), so
8
mv(v ?1)+2vs(?+m) ? 0 (mod 3), and
mv(v ?1)?vs(?+m) ? 0 (mod 3);
and so 3 divides xv, where x = (m(v?1)?s(?+m)). We intend to apply Theorems 2.2 and
2.3, when v is even and odd respectively, with x = (m(v?1)?s(?+m)), ? = m, and ? = v
in both cases. Note that by assumption (a), x ? 0. We have just checked that condition
(b) in each of Theorems 2.2 and 2.3 holds, and condition (a) clearly holds by assumption
(a). We now check the remaining conditions considering the cases where v is even and odd
in turn.
Case 1: Suppose v is even. Condition (c) of Theorem 2.3 clearly holds, so it remains
to show that 2 divides x. Since v is even and ?-admissible, by (iii), it must be the case
that ? is even. If m is even, then m(v ?1)?s(? + m) is clearly even. If m is odd, then
(? + m) is odd which, by (iii), implies (v + s) is odd, since it is (? + m)-admissible, and
thus m(v ?1)?s(?+m) is even.
So by Theorem 2.3 there exists a set of triples B3 which induces an x = (m(v?1)?s(?+
m))-regular subgraph on the vertex set Zv whose complement in mKv has a 1-factorization
into the s(?+m) 1-factors in F = fF1;F2;:::Fs(?+m)g.
Let B4 = ffnj;a;bg j 1 ? j ? s, i ? j (mod s), and fa;bg 2 E(Fi)g. Then each of the
remaining edges clearly occurs in a triple in B4.
Therefore (Zv [S, B1[B2[B3[B4 = B0) is clearly a TS(v+s;?+m) containing T.
Case 2: Suppose v is odd. Checking the remaining conditions of Theorem 2.4, clearly
m(v ? 1) is even. Therefore x is clearly even unless s(? + m) is odd; but then v + s is
even and (?+m) is odd, contradicting v+s being (?+m)-admissible. So, condition (c) of
Theorem 2.4 is met.
By Theorem 2.4, there exists a set B3 of triples on the vertex set Zv which induces an
x = (m(v?1)?s(?+m))-regular subgraph whose complement on Zv has a 2-factorization
consistingofthes(?+m)=22-factorsinF = fF1;F2;:::Fs(?+m)=2g. SodeflneB4 =ffnj;a;bg
j 1 ? j ? s, i ? j (mod s), and fa;bg 2 E(Fi)g.
9
S
V
Figure 2.1: Using the 1-factor in Theorem 2.5 Case 1
V
S
Figure 2.2: Using the 2-factor (not necessarily connected) in Theorem 2.5 Case 2
10
Then (Zv [S, B1 [B2 [B3 [B4 = B0) is clearly a TS(v+s;?+m) containing T.
We now easily obtain the result of Hurd, Munson, and Sarvate [13] in the following
corollary.
Corollary 2.1. There exists an enclosing of every TS(v;?) in a TS(v + 1;? + m) if and
only if 1 ? m(v ?1)=(?+m) and v +1 is (?+m)-admissible.
Proof First, suppose that there exists an enclosing of a TS(v;?), (V;B1) in a TS(v +
1;?+m), (V [S;B0). Then S = fn1g and n1 has degree v(?+m). Each of the v(?+m)=2
triples containing n1 in B0 contains an edge in mKv. Therefore mv(v?1)=2 ? v(?+m)/2,
so 1 ? m(v ?1)=(?+m).
Next, suppose that there exists a TS(v;?), (V;B1), such that 1 ? m(v ?1)=(? + m),
and that (v +1) is (?+m)-admissible. Clearly s = 1 is (?+m)-admissible. Therefore, by
Theorem 2.5, there exists an enclosing TS(v +1;?+m), (V [S;B0) of (V;B1).
2.3 Enclosings when jSj+1 is (?+m)-admissible
In this section we investigate the enclosing of a TS(v;?) in a TS(v + s;? + m) when
jSj+1 is (?+m)-admissible. We essentially borrow a vertex from Zv and repeat the process
from Theorem 2.5.
Theorem 2.6. Let v, ?, m, and s be positive integers. Then every TS(v;?) can be enclosed
in a TS(v +s;?+m) if:
(a) s ? (m(v ?2)?m)=(?+m),
(b) both v +s and s+1 are (?+m)-admissible.
Proof Let T = (Zv;B1) be a TS(v;?); so v is ?-admissible. We add the s new vertices in
S = fn1;n2;:::;nsg and adjoin vertex 0 2 Zv to the set S creating S0 = fn1;n2;:::;ns;0g.
Let (S0;B2) be a TS(s + 1;? + m) (this exists by assumption (b)). The remaining edges
not yet occurring in triples are therefore the edges in mKv?1, the ? + m edges joining
each vertex in Zv?1 to each vertex in S, and the m edges joining 0 to each vertex in Zv?1.
11
Following the proof of Theorem 2.5, since v +s is (?+m)-admissible, it must be that the
number of remaining edges is divisible by 3:
m(v ?1)(v ?2)=2+(v ?1)s(?+m)+m(v ?1) ? 0 (mod 3), so
(v ?1)(m(v ?2)+2s(?+m)+2m) ? 0 (mod 3), and
(v ?1)(m(v ?2)?s(?+m)?m) ? 0 (mod 3):
Therefore, either
(v ?1) ? 0 (mod 3) or
m(v ?2)?s(?+m)?m ? 0 (mod 3):
In either case, it follows that 3 divides x(v?1), where x = (m(v?2)?s(?+m)?m). By
assumption (a), x ? 0. Therefore, with ? = m and ? = v ?1 in each of Theorems 2.2 and
2.3 it can be seen that condition (b) and condition (a) clearly hold in each theorem. We
now examine the cases where v is even and odd in turn.
Case 1: Suppose v is even. Then by (iii), ? must be even since v is ?-admissible. Since
v + s 6? s + 1 (mod 2), using condition (b), the only way (iii) can hold in both cases is if
? + m is even. So m is even. Let x = (m(v ? 2) ? s(? + m) ? m). Then x is even, and
m(v ?2) is even, so condition (c) of Theorem 2.4 holds (with ? = m and ? = v ?1). We
therefore obtain the desired enclosing by proceeding in the same manner as in the proof of
Case 2 of Theorem 2.5.
Case 2: Next, suppose v is odd. Let x = (m(v?2)?s(?+m)?m). 2 clearly divides
(v ? 1), so condition (c) of Theorem 2.3 is satisfled. Since v + s and s + 1 are (? + m)-
admissible, s(? + m) and (v + s?1)(? + m) are even; since v is ?-admissible, (v ?1)? is
even. So by (iii), (v + s ? 1)(? + m) ? (v ? 1)? = m(v ? 1) + s(? + m) ? x (mod 2) is
even. So condition (d) of Theorem 2.3 is met (with ? = m and ? = v ?1). We therefore
12
obtain the desired enclosing by proceeding in the same manner as in the proof of Case 1 of
Theorem 2.5.
SV
Figure 2.3: Idea of the construction of Theorem 2.6 Case 2
2.4 Enclosings when jSj+3 is (?+m)-admissible
In this section we investigate the enclosing of a TS(v, ?) where jSj+3 is (? + m)-
admissible.
Theorem 2.7. Let v;?;m, and s be positive integers. Then every TS(v;?) can be enclosed
in a TS(v +s;?+m) if:
(a) s ? (m(v ?4)?3m)=(?+m),
(b) both v +s and s+3 are (?+m)-admissible, and
(c) s ? 0 or 4 (mod 6) or s ? 7.
Proof Let T = (Zv;B1) be a TS(v;?); so v is ?-admissible. We add the s new vertices
in S = fn1;n2;:::;nsg and adjoin vertices 0, 1, 2 2 Zv to the set S creating the set S0 =
fn1;n2;:::;ns;0;1;2g.
13
If s ? 0 or 4 (mod 6) then s+3 ? 1 or 3 (mod 6). Let (S0;B02) be a TS (s+3;?+m)
that consists of (? + m) copies of TS(s + 3;1) each of which contains the triple f0, 1, 2g
(this exists by assumptions (b) and (c)), removing ? copies of the triple f0, 1, 2g from B02
we let this set of triples be B2. Then let (S0;B2) be a partial triples system on S0.
If s ? 7 we need to enclose ?K3 into (? + m)Ks+3 where K3 is ? copies of the triple
f0, 1, 2g. We let v0 = 3. By assumption (b), s+3 is (?+m)-admissible, and 3 is of course
m-admissible. If (?+m)v0s ? (?+m)s(s?1)=2 we can apply Theorem 2.3. Since v0 = 3,
we have
3 ? (s?1)=2, and
s ? 7:
By assumption (c), this bound holds. We then let (S0;B2) be the partial triple system given
by the above construction and Theorem 2.5 ignoring the triples of ?K3.
Since v + s is (? + m)-admissible, it must be that the number of remaining edges is
divisible by 3:
m(v ?3)(v ?4)=2+(?+m)(v ?3)s+m3(v ?3) ? 0 (mod 3), so
(v ?3)(m(v ?4)+(?+m)2s+6m) ? 0 (mod 3), and
(v ?3)(m(v ?4)?s(?+m)?3m) ? 0 (mod 3):
Therefore, either
(v ?3) ? 0 (mod 3) or
m(v ?4)?s(?+m)?3m ? 0 (mod 3):
In either case, it follows that 3 divides x(v ?3), where x = (m(v ?4)?(? + m)s?3m).
By assumption (a), x ? 0. Therefore, with ? = m and ? = v ?3 in each of Theorems 2.2
14
and 2.3 it can be seen that conditions (a) and (b) clearly hold in each theorem. We now
examine the cases where v is even and odd in turn, using the value of x in both cases.
Triple System of
u+3+m)K 3
Use Theorem 2.5
\   K( ??
Figure 2.4: Idea of the construction of Theorem 2.7
Case 1: Suppose v is even. Then by (iii), ? is even since v is ?-admissible. Since
v + s 6? s + 3 (mod 2), the only way condition (b) of Theorem 2.4 and (iii) can hold is if
?+m is even. So m is even, x = (m(v?4)?(?+m)s?3m) is even, and m(v?4) is even,
so condition (c) of Theorem 2.4 holds (with ? = m and ? = v?3). We therefore obtain the
desired enclosing by proceeding in the same manner as in the proof of Case 2 of Theorem
2.5.
Case 2: Next, suppose v is odd. Clearly 2 divides (v?3), so condition (c) of Theorem 2.3
is satisfled. Since v+s and s+3 are (?+m)-admissible, (?+m)(s+2) and (?+m)(v+s?1)
are even and thus, (?+m)s is even as well; since v is ?-admissible, ?(v?1) is even. So, by
(iii), (? + m)(v + s?1)??(v ?1) = m(v ?4) + (? + m)s + 3m ? x (mod 2) is even. So
condition (d) of Theorem 2.3 is met (with ? = m and ? = v ?3). We therefore obtain the
desired enclosing by proceeding in the same manner as in the proof of Case 1 of Theorem
2.5.
15
2.5 Other Enclosings
The preceding constructions have addressed the existence of enclosings for all values of
s and ?+m (restricted by the bounds on s), except when s ? 5 (mod 6) and (?+m) ? 1
or 5 (mod 6). We now address this case to give a comprehensive list of constructions for all
s and ?+m within the tolerance of our bounds.
Theorem 2.8. Let v;?;m, and s be positive integers with s ? 5 (mod 6). Let v be even and
(?+m) ? 1 or 5 (mod 6), m > 1. Then every TS(v;?) can be enclosed in a TS(v+s;?+m),
if:
(a) s ? (m?1)(v ?1)=(?+m?1) if (?+m) ? 1 (mod 6),
(b) s ? (m?1)(v ?3)=(?+m?1) if (?+m) ? 5 (mod 6), and
(c) v +s is (?+m)-admissible.
Proof Let T = (Zv;B1) be a TS(v;?); so v is ?-admissible. We add the s new vertices in
S = fn1;n2;:::;nsg.
Case 1: Let v be even and (?+m) ? 1 (mod 6). By Table 2.1, assumption (c) implies
that (v +s) ? 1 or 3 (mod 6). So let (Zv [S;B2) be a TS(v +s, 1). Since ?+m?1 ? 0
(mod 6), s ? 5 (mod 6) is (?+m?1)-admissible. Let (S;B3) be a TS(s;?+m?1) .
We now intend to apply Theorem 2.3 as in Theorem 2.5 since s ? (m?1)(v?1)=(?+
m?1) with x = ((m?1)(v?1)?(?+m?1)s) ? 0 (by assumption (a)), ? = m?1, and ? = v.
Condition (a) of Theorem 2.3 clearly holds since x ? 0. Since v +s is (?+m)-admissible,
the number of remaining edges must be divisible by 3:
(m?1)v(v ?1)=2+(?+m?1)vs ? 0 (mod 3), so
v((m?1)(v ?1)?(?+m?1)s ? 0 (mod 3);
and so 3 divides xv, satisfying condition (b) of Theorem 2.3. Condition (c) of Theorem 2.3
is clear as well since ? = v is even. ? must be even (by (iii)) and ? = m?1 must be even
16
so condition (d) of Theorem 2.3 is satisfled. We therefore obtain the desired enclosing by
proceeding in the same manner as in the proof of Case 1 of Theorem 2.5.
Case 2: Let v be even and (? + m) ? 5 (mod 6). Again, since (v + s) ? 1 or 3 (mod
6) we let (Zv [ S;B2) be a TS(v + s, 1). We adjoin vertex 0 2 Zv to the set S creating
S0 = fn1;n2;:::;ns;0g. Since s+ 1 ? 0 (mod 6) and (?+m?1) ? 4 (mod 6), let (S0;B3)
be a TS(s+1;?+m?1).
We now apply Theorem 2.4, as in Theorem 2.6, withx = (m?1)(v?3)?(?+m?1)s ? 0
(by assumption (b)), ? = m?1, and ? = v?1. Condition (a) of Theorem 2.4 clearly holds
since x ? 0. We now check the remaining conditions of Theorem 2.4. Since v + s is
(?+m)-admissible, the number of remaining edges must be divisible by 3:
(m?1)(v ?1)(v ?2)=2+(?+m?1)(v ?1)s+(m?1)(v ?1) ? 0 (mod 3), so
(v ?1)((m?1)(v ?3)?(?+m?1)s ? 0 (mod 3);
and so 3 divides x(v ? 1), satisfying condition (b) of Theorem 2.4. Since ? = m ? 1 and
(?+m?1) must be even, condition (c) of Theorem 2.4 is satisfled. We therefore obtain the
desired enclosing by proceeding in the same manner as in the proof of Case 1 of Theorem
2.6.
Theorem 2.9. Let v;?;m, and s be positive integers with s ? 5 (mod 6). Let v ? 2 or 4
(mod 6), (?+m) ? 1 or 5 (mod 6), and m = 1. Then every TS(v;?) can be enclosed in a
TS(v +s;?+1) if:
(a) s ? v +1, and
(b) v +s is (?+m)-admissible.
Proof Let T = (Zv;B1) be a TS(v;?); so v is ?-admissible. We add the s new vertices in
S = fn1;n2;:::;nsg.
Case 1: Let v ? 2 (mod 6). By Table 2.1, assumption (b) implies that ? ? 0 (mod 6).
(v+s) ? 1 (mod 6) and m = 1 so (?+m) ? 1 (mod 6). Let (Zv [S;B2) be a TS(v+s, 1).
17
The remaining edges not yet occurring in triples are therefore the edges in ?Ks and the ?
edges joining each vertex in Zv to each vertex in S. Since
?s(s?1)=2 ? ?vs=2, we have that
s ? v +1:
We can now apply Theorem 2.4, as in Case 2 of Theorem 2.5, and choose S to be Zv with
x = ?(s?1)??v ? 0 (by assumption (a)), ? = ?, and ? = s. Conditions (a) and (c) of
Theorem 2.4 are clear. Since v + s is (? + m)-admissible, the number of remaining edges
must be divisible by 3:
?s(s?1)=2+?vs ? 0 (mod 3), so
s(?(s?1)??v) ? 0 (mod 3);
and so 3 divides xs. Therefore, condition (b) is satisfled and we therefore obtain the desired
enclosing by proceeding in the same manner as in the proof of Case 2 of Theorem 2.5.
Case 2: Let v ? 4 (mod 6). By (iii), assumption (b) implies that ? is even. (v +s) ?
3 (mod 6), m = 1, and (?+m) ? 1 or 5 (mod 6). Let (Zv [S;B2) be a TS(v +s, 1). The
remaining edges not yet occurring in triples are therefore the edges in ?Ks and the ? edges
joining each vertex in Zv to each vertex in S. Since
?s(s?1)=2 ? ?vs=2, we have that
s ? v +1:
We therefore obtain the desired enclosing by proceeding in the same manner as Case 1 with
x = ?(s?1)??v, ? = ?, and ? = s.
18
2.6 Large Enclosings
Wehavelookedat enclosings involving1-factorizations and 2-factorizations in thegraph
of mKv. We now switch our construction, and apply Theorems 2.2 and 2.3 to the added
vertices in the graph of (?+m)Ks to give us enclosings involving values of s > v.
Theorem 2.10. Let v;?;m; and s be positive integers. Then every TS(v;?) can be enclosed
in a TS(v +s;?+m) if:
(a) s ? v +1;and
(b) v is m-admissible and v +s is (?+m)-admissible.
Proof Let T = (Zv;B1) be a TS(v;?); so v is ?-admissible. We add the s new vertices
in S = fn1;n1;:::;nsg to form an enclosing (Zv [S;B0) of T as follows. Let (Zv;B2) be a
TS(v;m) (this exists by assumption (b)). The remaining edges not yet occurring in triples
are therefore the edges in (? + m)Ks, and the (? + m) edges joining each vertex in Zv to
each vertex in S. Then there are (?+m)s(s?1)=2 + vs(?+m) remaining edges so, since
v +s is (?+m)-admissible, it must be the that the remaining edges is divisible by 3:
(?+m)s(s?1)=2+(?+m)vs ? 0 ( mod 3), so
(?+m)s(s?1)?(?+m)vs ? 0 ( mod 3), and
(?+m)s(s?v ?1) ? 0 ( mod 3),
and so 3 divides xs, where x = (? + m)(s?v ?1). We have just checked that condition
(b) in each of Theorems 2.2 and 2.3 holds, and condition (a) clearly holds by assumption
(a). We intend to apply Theorems 2.2 and 2.3, where s is even and odd in turn, with
x = (?+m)(s?v ?1), ? = ?+m, and ? = s in both cases.
Case 1: Suppose s is even. Condition (c) of Theorem 2.3 clearly holds, so it remains to
show that 2 divides x. If (?+m) is even then x is clearly even. If (?+m) is odd, condition
(iii) implies (v + s) is odd (by assumption (b)), and thus x = (? + m)(s?v ?1) is even.
19
So condition (d) of Theorem 2.3 is satisfled. We therefore obtain the desired enclosing by
proceeding in the same manner as in the proof of Case 1 of Theorem 2.5.
Case 2: Suppose s is odd. Checking the remaining conditions of Theorem 2.4, (? +
m)(s?1) is clearly even. Therefore x is even unless (?+m)v is odd; but, by (iii), if (?+m)v
is odd then (?+m)(s?1) is odd, contradicting s being odd. So, condition (c) of Theorem
2.4 is met. We then get the desired enclosing by proceeding in the same manner as in the
proof of case 2 of Theorem 2.5.
Theorem 2.11. Let v;?;m; and s be positive integers. Then every TS(v;?) can be enclosed
in a TS(v +s;?+m) if:
(a) 1 ? m(v ?1)=(?+m) and v +1 is (?+m)-admissible, and
(b) s ? v +3 and v +s is (?+m)-admissible.
Proof Let T = (Zv;B1) be a TS(v;?); so v is ?-admissible. We add the s new vertices in
S = fn1;n1;:::;nsg and adjoin vertex ns 2 S to the set Zv creating Z0v = f0;1;2;:::;v;nsg.
Let (Z0v;B2) be a TS(v+1;?+m) (this exists by assumption (a) and Corollary 2.5). Since
v + s is (? + m)-admissible, it must be the case that the number of remaining edges is
divisible by 3:
(?+m)(v +1)(s?1)+(?+m)(s?1)(s?2)=2 ? 0 (mod 3), so
(?+m)(s?1)(?(v ?1)+s?2) (mod 3), and
(?+m)(s?1)(s?v ?3) (mod 3)
and so 3 divides x(s?1) where x = (?+m)(s?v?3) ? 0. We intend to apply Theorems
2.2 and 2.3, when s is odd and even, respectively, with x = (?+m)(s?v?3), ? = ?+m,
and ? = s?1.
Case 1: Suppose s is odd, then s ? 1 is even. Condition (c) of Theorem 2.3 clearly
holds, so it remains to show that 2 divides x. If (? + m) is even the x is clearly even. If
(?+m) is odd, condition (iii) implies v+s?1 is even and thus s?v?3 is even. Therefore x
20
is even, satisfying condition (d) of Theorem 2.3. We therefore obtain the desired enclosing
by proceeding in the same manner as in the proof of Case 1 of Theorem 2.5 with the above
values for x, ?, and ?.
Case 2: Suppose s is even, then s ? 1 is odd. Clearly 2 divides ? ? 1. If (? + m) is
even, x is clearly even. If (? + m) is odd, then condition (iii) and assumption (b) imply
that v +s?1 must be even. Thus s?v ?3 is even and therefore x is even. So, condition
(c) of Theorem 2.4 holds. We therefore obtain the desired enclosing by proceeding in the
same manner as in the proof of Case 2 of Theorem 2.5.
Theorem 2.12. Let v;?;m, and s be positive integers with s ? 1 or 5 (mod 6). Then every
TS(v;?) can be enclosed in a TS(v +s;?+m) if:
(a) s ? v +1 and (?+m) ? 1 (mod 6) or (?+m) ? 5 (mod 6) and v ? 0, 1, 3, or, 4
(mod 6), or
(b) s ? v+3, 1 ? (m?1)(v?1)(?+m?1) and v+1 is (?+m)-admissible if (?+m) ?
5 (mod 6) and v ? 2 or 5 (mod 6), and
(c) v +s is (?+m)-admissible.
Proof Let T = (Zv;B1) be a TS(v;?); so v is ?-admissible. We add the s new vertices
in S = fn1;n1;:::;nsg. Let (Zv [ S;B2) be a TS(v + s;1) (this exists by Table 2.1 since
(?+m) ? 1 or 5 (mod 6), and assumption (c)). The necessary conditions of the following
cases are checked by following the proof of Theorem 2.8.
Case 1: If s ? v + 1 and (? + m) ? 1 (mod 6), or (? + m) ? 5 and v ? 0;1;3; or 4
(mod 6) then ?+m?1 ? 0 (mod 6) and v is (?+m?1)-admissible. We then proceed in
the same manner as Theorem 2.10 with x = (? + m?1)(s?v ?1), ? = ? + m?1, and
? = s.
Case 2: First, assume assumption (b). Then ?+m?1 ? 4 (mod 6). We adjoin vertex
ns 2 S to the set Zv creating Z0v = f0;1;2;:::;v;nsg. Let (Z0v;B2) be a TS(v+1;?+m?1)
(this exists by assumption (b) and Corollary 2.5). We then proceed in the same manner as
Theorem 2.10 with x = (?+m?1)(s?v?3) ? 0 (by assumption (b)), ? = ?+m?1, and
? = s?1.
21
2.7 Conclusion
The constructions presented here are exhaustive in the sense that for each possible
congruence of s or v (mod 6) and each possible congruence of (? + m) or m (mod 6), at
least one theorem can be applied to obtain an enclosing, as described in the tables below.
Of course, not all enclosings have been found, since each result places restrictions on s or
v, given the other parameters.
Notice that Theorem 2.2 contains a bound that one can view as being quadratic in
s, given all other parameters of our enclosings. As an example of how one would use the
results in the previous section, suppose that we attempt to enclose a TS(82;8) in a triple
system that is near the bounds of Theorem 2.2. In order to do so we will examine the case
when m = 1 and vary s. The necessary condition requires that
s ? 832 ?
p(832)81?4(82)81(9)
2(9) ? 10:13 or
s ? 832 +
p(832)81?4(82)81(9)
2(9) ? 72:87 .
It can be seen that the necessary condition creates a \gap" of values that is unusual in
these types of designs. This gap is created by he increasing need to use each edge with two
v vertices, or two s vertices, with two \mixed" edges (those having a v and s vertex). We
will see this phenomenon in the following example. We will use s = 73 for this example,
looking at a value bordering the necessary condition. If we simply use the theorems in this
chapter we can enclose a TS(82, 5) in a TS(155, 9) if s ? m(v?1)(?+m) (Theorem 2.5) giving us
s ? 1(81)9 = 9 which gets us very close to the flrst bound. Or, s ? 83 (Theorem 2.10) which
is not nearly as close as we would like. It is expected that the constructions in this chapter
could be used to greater efiect as the following suggests.
From Table 2.1, we see that it is possible for a TS(155;9) to exist. Then Let B1 consist
of the triples of a TS(82;8) then V is a 1K82 and S is a 9K73 with a 9K82;73 between the
two sets of vertices. We will attempt to use our flrst construction presented. Table 2.1
22
82
9K73
1K
Figure 2.5: Example bordering the bounds of Theorem 2.3
says that a TS(73;9) exists so let these triples make up the set B2. There are now 3321
edges in 1K82 which consists of 81 1-factors each of which contains 41 edges. Each 1-factor
uses 82 edges in 9K82;73. Using every edge in 1K82 in a triple with 2 vertices in V and one
in S leaves 53874 ? 82(81) = 47232 edges that need to be put in triples, but there is no
possibility of putting these edges into triples given the aforementioned partitions. So, this
construction has \failed" to enclose the TS(82;8) into a TS(155;9).
We will next attempt a construction by \switching" our construction by using a mod-
iflcation of Theorem 2.7 which would allow us to get closer to the necessary bound rather
than with the bound in Theorem 2.10. This idea was more commonly seen in the section
Large Enclosings, but is applicable in our point here. We will use the construction that
\borrows" 3 vertices. Of course, we will let B1 be the triples of a TS(82;8). Next, we will
create the set V0 by adjoining the vertices n1;n2;n3 2 S to V, and let the remaining vertices
of S be the set S0. By Table 2.1, a TS(85;1), (V [fn1;n2;n3g;B2), exists and let the 24
unused edges between n1;n2 and n3 form a set of 8 triples, B3. Then there are 35 edges in
each of the 621 1-factors that comprise the 21735 edges in 9K70 (the induced graph on S0).
We need 9(85) = 765 1-factors which requires 26775 edges in S0. Using all edges possible,
23
there are still 53874 ? 2(21735) = 10404 edges still to be put in triples which cannot be
done without \breaking up" some of the already formed triples since all edges not used in
triples are \mixed". That is, they connect V vertices with S vertices which will not allow
for triples to be formed without some connected edge (those already in triples). Essentially,
since a bipartite graph has no odd cycles, and what remains is a bipartite graph, we cannot
form a triple. So this construction has \failed" as well.
We use the term \failed" loosely and in the sense that each construction leaves some
edges not partitioned into triples. But, with a lot of well chosen triple deconstruction, we
could construct triples involving the remaining edges between the sets V and S and the
edges of the deconstructed triples to flnish the enclosing. With values close to the bounds
given by Theorem 2.3, the constructions would require nearly every edge in V and S to use
two edges between V and S.
We have seen the usefulness of the theorems provided by Fu and Rodger [8]. In the
majority of our constructions, we have dealt mainly with triples containing a symbol of S
and two symbols in V. Section 2.5 is the flrst instance where we have extensively used
\mixed" triples (Those having one symbol in V and two symbols in S and vice versa.).
It is easily seen that this type of construction relaxes the bounds given in the previous
four sections. It is the hopes of the authors that the  exibility of using \mixed" triples
will constitute a lowering of the restrictive bounds presented, creating a larger family of
enclosings.
24
s (mod 6) Restrictions on ?+m (mod 6) Theorem Construction
0 0, 2, 4 2.5, 2.6, 2.7
0 1, 3, 5 2.6, 2.7
1 0 2.5, 2.6, 2.7
1 2, 4 2.5, 2.7
1 1, 3, 5 2.5
2 0 2.5, 2.6, 2.7
2 1, 2, 4, 5 2.6
2 3 2.6, 2.7
3 0, 2, 4 2.5, 2.6, 2.7
3 1, 3, 5 2.5
4 0 2.5, 2.6, 2.7
4 1, 5 2.7
4 2, 4 2.5, 2.7
4 3 2.6, 2.7
5 0 2.5, 2.6, 2.7
5 1, 5 2.8, 2.9
5 2, 4 2.6
5 3 2.5
Table 2.2
25
v (mod 6) Restrictions on m (mod 6) Theorem Construction
0 0, 2, 4 2.10
0 1, 3, 5 2.11
1 0, 1, 2, 3, 4, 5 2.10
2 0 2.10
2 1, 2, 3, 4, 5 2.11
3 0, 1, 2, 3, 4, 5 2.10
4 0, 2, 4 2.10
4 1, 5 2.12
4 3 2.11
5 0, 3 2.10
5 1, 5 2.12
5 2, 4 2.11
Table 2.3
26
Chapter 3
Enclosings of 4-Cycle Systems
3.1 Preliminaries
We now investigate the enclosings of ?-fold 4-cycle systems. In this section we com-
pletely solve the enclosing problem for ?-fold 4-cycle systems when u ? 2 proving the
following theorem.
Figure 3.1: 4-cycle decomposition of K9
Theorem 3.1. Let u > 1. Every 4-cycle system of ?Kv can be enclosed in a 4-cycle system
of (?+m)Kv+u ifi
(a) (v +u?1)(?+m) ? 0 (mod 2), and
(b) u(u?1)(?+m)=2+mv(v ?1)=2+vu(?+m) ? 0 (mod 4).
Throughout, we will use standard graph theoretic terminology which, if not deflned
here, can be found in [17, 22]. If G and H are two graphs then let G [ H be the graph
27
with vertex set V(G [ H) = V(G) [ V(H) and edge set E(G [ H) = E(G) [ E(H). If
V(G) \ V(H) = ;, then let G _ H be the graph with V(G _ H) = V(G) [ V(H) and
E(G_H) = E(G)[E(H)[ffg;hg j g 2 V(G);h 2 V(H)g. If H is a subgraph of G, let
G?H be the subgraph of G containing precisely those edges of G which are not in H. Let
?K(X;Y) be the bipartite graph with vertex set X [Y on which each x 2 X is joined to
each y 2 Y with ? edges. Throughout this section let v = jVj, u = jUj, and w = jWj.
We begin by proving the necessity of conditions (a)-(c) in Theorem 3.1 which clearly
follows by the following lemma.
Lemma 3.1. Suppose there exists a 4-cycle system of ?Kv. Then conditions (a)-(c) of
Theorem 3.1 hold ifi in (?+m)Kv+u:
i) each vertex has even degree, and
ii) the number of edges is divisible by 4.
Proof
First, assume that conditions (a) and (b) hold. Then (?+m)(v+u?1), the degree of
each vertex in (?+m)Kv+u, is even, thus proving (i). By (b), u(u?1)(?+m)=2+mv(v?
1)=2 + vu(? + m) ? 0 (mod 4), adding in ?v(v ?1)=2, which is the number of edges in a
?Kv (which must be divisible by 4), we have: u(u?1)(? + m)=2 + mv(v ?1)=2 + vu(? +
m)+?v(v ?1) ? 0 (mod 4) which is the number of edges in (?+m)Kv+u, proving (ii).
Now assume that conditions (i) and (ii) hold. Then (?+m)(v+u?1), the degree of a
vertex in (?+m)Kv+u is even, proving (a) holds. (?+m)(v+u?1) = (?+m)(u)+m(v?
1) + ?(v ? 1) this implies that (? + m)(u) + m(v ? 1) is even, (because a 4-cycle system
of ?Kv is postulated to exist) ?(v ? 1) must be even, proving (b). The number of edges
of (? + m)Kv+u is (? + m)v(v ?1)=2 + (? + m)u(u?1)=2 + (? + m)uv which is divisible
by 4. Since there exists a 4-cycle system of ?Kv, ?v(v ? 1)=2 is also divisible by 4. So
(?+m)v(v?1)=2+(?+m)u(u?1)=2+(?+m)uv??v(v?1)=2 = u(u?1)(?+m)=2+
mv(v ?1)=2+vu(?+m) ? 0 (mod 4), giving us condition (b).
28
Table 3.1 [2] below summarizes these necessary as well as the su?cient conditions for
the existence of 4-cycle systems of lKw. An integer w is said to be l-admissible if conditions
(i) and (ii) of Lemma 3.2 are satisfled for some index l. This deflnition is made in the
context of the existence of 4-cycle systems, conditions (a)-(c) of Theorem 3.1 being obvious
necessary conditions for their existence. An interpretation of Table 3.1 is that there exists
a 4-cycle system (W;l) if and only if w is l-admissible.
l Restrictions on w
1 (mod 4) w ? 1 (mod 8)
2 (mod 4) w ? 0 or 1 (mod 4)
3 (mod 4) w ? 1 (mod 8)
0 (mod 4) w 6= 2 or 3
Table 3.1
Necessary and su?cient conditions for the existence of 4CS(w;l).
The following two results will be used extensively to partition the edges of Ku;v and
mKv into 4-cycles, respectively.
Theorem 3.2. [20] There exists a 4-cycle system of ?Kx;y if and only if
(1) x;y ? 2
(2) ?xy ? 0 (mod 4)
(3) ?x ? ?y ? 0 (mod 2).
The following table found in [9] will be useful in discussing our next lemma. Table 3.2
is a list of the leaves of maximum packings of ?Kv with 4-cycles. F is a 1-factor; Cn is a
cycle of length n; E6 is the set of graphs on n vertices with 6 edges in which each vertex
has even degree, D is a doubled edge; and F2 can be chosen to be the set of graphs on n
vertices in which all vertices have degree 1 except for either one vertex that has degree 5,
or two vertices that have degree 3, or the graph with vertex set f0;1;2;3;4;5g and edge
set ff0;1g;f0;2g;f0;3g;f1;4g;f1;5gg; in this dissertation we assume F2 is the latter two
whenever possible.
29
? (mod 4) / v (mod 8) 0 1 2 3 4 5 6 7
1 F ` F C3 F E6 F C5
2 ` ` E6;D if v > 3 E6;D if v > 3 ` ` E6;D E6;D
3 F ` F2 if v > 2 C5 if v > 3 F E6;D F2 C3
4 ` ` ` if v > 2 ` if v > 3 ` ` ` `
Table 3.2 Maximum Packings; Use E6 if simple leaves are required, and D otherwise.
The following lemma will be useful in the construction when the number of new vertices
is 2.
Lemma 3.2. If there exists a partial decomposition of ?Kv into t 4-cycles, then there exists
an equitable, partial decomposition of ?Kv into t 4-cycles.
Proof Let L(?;v) denote the number of edges in the leave of a maximum packing of ?Kv
with 4-cycles (see Table 3.2, and use D as the leave when available). Since all leaves can be
chosen to be equitable, in view of Table 3.2, we can assume that t < (?v(v?1)2 ?L(?;v))=4.
We will proceed by induction on the index ?. Bryant et al [5] proved the case when ? = 1.
Assume that the hypothesis is true for ? ? k?1. In most cases the result will immediately
follow by taking the union of two graphs with the same vertex set, namely (??z)Kv and
zKv, with z 2f1;2g, to form the graph ?Kv.
Case 1: Suppose t ? t? = ((??1)v(v?1)2 ?L(??1;v))=4. An equitable, partial 4-cycle
decomposition of (??1)Kv then exists by the induction hypothesis; this is also an equitable,
partial decomposition of ?Kv into 4-cycles.
Case 2: Suppose t? < t ? t?? = (?v(v?1)2 ? minz2f1;2gfL(??z;v) + L(z;v)g)=4. Let
(V;B1) and (V;B2) be maximum packings of (??z)Kv andzKv, respectively withz 2f1;2g.
Let G(B1) and G(B2) be the graphs induced by (V;B1) and (V;B2) respectively, naming
the vertices so that dG(B1)(i) ? dG(B1)(j) and dG(B2)(i) ? dG(B1)(j) for 0 ? i < j ? v ?1.
Let G be the union of G(B1) and G(B2). Then clearly each vertex in G has degree in
fdG(B1)(0)+dG(B2)(v ?1)+d j d 2 f0;2gg or fdG(B1)(0)+dG(B2)(v ?1) +d j d 2 f2;4gg.
In either case, it follows that (V;B1 [B2) is the desired equitable partial 4-cycle system.
30
Case 3: Now suppose that t?? < t < (?v(v?1)2 ?L(?;v))=4. This is nearly a maximum
packing of ?Kv. We use the same approach as in Case 2, starting with up to two maximum
packings (V;B1) of (? ? z)Kv and (V;B2) of zKv, except that we may need to align the
respective leaves to create more 4-cycles. It su?ces to consider one choice of z for each of
the possible values of ? and v. These are chosen so that the union of the leaves L1[L2 has
as many 4-cycles as possible. Exactly t?t?? of these 4-cycles are then added to B1[B2 to
obtain the desired equitable 4-cycle system; the following argument checks this is possible.
Using Table 3.2, we consider each case in turn.
Subcase 1: Suppose flrst that the leaves of the two maximum packings are both 1-
factors, L1 and L2. Let the leave L1 of B1 have edge set ff2x;2x+2g;f2x+1;2x+3gj x 2
f0;1;2;:::;v?1gg and the leave L2 of B2 have edge set ff0;1g;f2;3g;:::;fv?2;v?1gg.
The additional 4-cycles are those in B3 = f(y;y + 1;y + 3;y + 2) j 0 ? y < t?t??g. Then
(V;B1 [B2 [B3) produces the required equitable partial 4-cycle system.
Subcase 2: Let the leaves of the two maximum packings be C5?s with L1 = (0;1;2;3;4)
and L2 = (0;2;5;3;6). These edges can be taken as the 2 cycles (0;2;3;4) and (0;1;2;5;3;6)
adding the flrst to B1 [B2 to produce the required equitable partial 4-cycle system with
leave E6 (or simply use E6 in Table 3.2).
Subcase 3: Let the leaves of the two maximum packings be a C5 with L1 = (0;1;2;3;4)
and a C3 with L2 = (1;3;4). Add the 4-cycle (0;1;3;4) to B1 [B2 to obtain the required
equitable partial 4-cycle system (or, we can simply think of removing a 4-cycle from a
4-cycle system).
The subcases take into account all relevant combinations of (??z)Kv and zKv to get
the desired partial equitable 4-cycle decomposition of ?Kv.
3.2 Enclosings when u ? 3
In this section we provide our flrst su?cient conditions for the existence of an enclosing
of a 4-cycle system of ?Kv, proving that Theorem 3.1 is true when u ? 3.
31
Proposition 3.1. Let v;?;m, and u be positive integers with v ? 4, u ? 3 and ? ?
1 (mod 4). Then every 4CS(v;?) can be enclosed in a 4CS(v + u;? + m), if v + u is
(?+m)-admissible.
Proof We will proceed case by case based on the congruence of m (mod 4) and the possible
values of u. We can assume V =Zv
Let C = (Zv;C1) be a 4CS(v;?). Since v is ?-admissible, by Table 3.1 we see that
jZvj = v ? 1 (mod 8). Let U = fn1;n2;:::;nug with U \Zv = ; and form an enclosing
4CS(Zv [U;C0) of C as follows.
Case 1: Suppose m ? 1 (mod 4). Then (?+m) ? 2 (mod 4). Therefore, since v+u is
(?+m)-admissible, (?+m) ? 1+1 = 2 (mod 4) and, since v ? 1 (mod 8), Table 3.1 implies
that u ? 0 or 3 (mod 4). Since ? ? m (mod 4), there exists a 4CS(v;m), say (Zv;C2).
(i) If u ? 0 (mod 4), then u is (? + m)-admissible so there exists a 4CS(u;? + m),
say (U;C3); this exists by Table 3.1 since u ? 0 (mod 4). This leaves the edges of (? +
m)K(Zv;U) remaining. Clearly, the degree of each vertex in (?+m)K(Zv;U) is even and,
as u+v is (?+m)-admissible, the number of edges remaining is divisible by 4. Therefore,
by Theorem 3.2, the remaining edges can be decomposed into 4-cycles. Let (Zv [U;C4) be
a 4CS of (?+m)K(Zv;U).
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
(ii) If u ? 3 (mod 4), adjoin vertex 0 2Zv to the set U creating U0 = fn1;n2;:::;nu;0g.
Let (U [f0g;C3) be a 4CS(u+1;?+m) (this exists by Table 3.1). This leaves the edges of
(?+m)K(Zvnf0g;U) remaining. Clearly, the degree of each vertex in (?+m)K(Zvnf0g;U)
is even and, as u + v is (? + m)-admissible, the number of edges remaining is divisible by
4. Therefore, by Theorem 3.2, the remaining edges can be decomposed into 4-cycles. Let
(Zv nf0g[U;C4) be a 4CS of (?+m)K(Zv nf0g);U).
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
Case 2: m ? 2 (mod 4). Then (? + m) ? 3 (mod 4). Therefore, by Table 3.1, u ? 0
(mod 8). Since m ? 2 (mod 4), and v ? 1 (mod 8) there exists an m-fold 4CS(v;m), say
(Zv;C2). By adjoining vertex 0 2Zv to the set U creating U0 = fn1;n2;:::;nu;0g, there also
32
exists a 4CS(u+1;?+m), (U0;C3), (see Table 3.1). The remaining edges are those edges in
(?+m)K(Zv;U). By Theorem 3.2, there exists a 4CS (Zvnf0g[U;C4) of (?+m)K(Zv;U).
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
Case 3: m ? 3 (mod 4). Then (? + m) ? 0 (mod 4). Therefore, by Table 3.1, u 2 N,
and there exists a 4CS(v;m), say (Zv;C2).
(i) Let u be even. u is (?+m)-admissible so there exists a 4CS(u;?+m), say (U;C3);
this exists by Table 3.1. This leaves the edges of K(V;U) remaining. Clearly, the degree
of each vertex is even and, as u + v is (? + m)-admissible, the number of edges remaining
is divisible by 4. Therefore, by Theorem 3.2, the remaining edges can be decomposed into
4-cycles. Let (Zv [U;C4) be a 4CS of (?+m)K(V;U).
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
(ii) Let u be odd. Adjoin vertex 0 2Zv to the set U creating U0 = fn1;n2;:::;nu;0g. Let
(U0;C3) be a 4CS(u+1;?+m) (see Table 3.1). This leaves the edges of (?+m)K(Zvnf0g;U)
remaining. Clearly, the degree of each vertex in (? + m)K(Zv nf0g;U) is even, u + v is
(? + m)-admissible, and the number of edges remaining is divisible by 4. Therefore, by
Theorem 3.2, the remaining edges can be decomposed into 4-cycles. Let (Zv nf0g[U;C4)
be a 4CS of (?+m)K(Zv nf0g;U).
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
Case 4: m ? 0 (mod 4). Then (? + m) ? 1 (mod 4). Therefore, by Table 3.1,
u ? 0 (mod 8), and there exists a 4CS(v;m), say (Zv;C2). Adjoin vertex 0 2 Zv to the
set U creating U0 = fn1;n2;:::;nu;0g. Let (U0;C3) be a 4CS(u + 1;? + m) (see Table
3.1). This leaves the edges of (?+m)K(Zv nf0g;U) remaining. Clearly, the degree of each
vertex in (?+m)K(Zv nf0g;U) is even and, as u+v is (?+m)-admissible, the number of
edges remaining is divisible by 4. Therefore, by Theorem 3.2, the remaining edges can be
decomposed into 4-cycles. Let (Zv nf0g[U;C4) be a 4CS of (?+m)K(Zv nf0g;U).
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
33
We will refer to the proof of Proposition 3.1 often when the constructions are the same,
while still keeping track of the changing parameters of v;u; and m.
Proposition 3.2. Let v;?;m, and u be positive integers with v ? 4, u ? 3, and ? ?
2 (mod 4). Then every 4CS(v;?) can be enclosed in a 4CS(v + u;? + m), if v + u is
(?+m)-admissible.
Proof We will proceed case by case based on the congruence of m (mod 4) and the possible
values of u. Again, we assume V =Zv.
Let C = (Zv;C1) be a 4CS(v;?). Since v is ?-admissible, by Table 3.1 we see that
jZvj = v ?0, 1, 4, or 5 (mod 8). Let U = fn1;n2;:::;nug with U \Zv = ; and form an
enclosing 4CS(v +u;C0) of C as follows.
Case 1: Suppose m ? 1 (mod 4). Then (? + m) ? 3 (mod 4). And, for each value of
v, u ? 1, 0, 5, or 4 (mod 8), respectively.
Since, in all cases, u + v is 1-admissible, let (Zv [ U;C2) be a 4CS(v + u;1). The
remaining edges of (?+m)Ku can be decomposed into a 4CS(u;?+m?1), (U;C3). This
exists by Table 3.1, since u ? 0 or 1 (mod 4), exactly one edge between each pair of vertices
in U has been used in C2. Let (V;C4) be a 4CS(v;m ? 1) of (m ? 1)Kv under the same
reasoning. Clearly, the degree of each vertex in (?+m?1)K(V;U) must be even and the
number of edges divisible by 4. Therefore, by Theorem 3.2, the remaining edges can be
decomposed into 4-cycles. Let (Zv [U;C5) be a 4CS of (?+m?1)K(V;U).
Then (Zv [U, C1 [C2 [C3 [C4 [C5 = C0) is clearly a 4CS(v +u;?+m) containing
C.
Case 2: Suppose m ? 2 (mod 4). Then (? + m) ? 0 (mod 4). First, suppose u ? 4.
In each case, v is m-admissible. Let (V;C2) be a 4CS(v;m) of mKv. And, for u ? 4, let
(U;C3) be a 4CS(u;?+m) of (?+m)Ku. These exist by Table 3.1. As (?+m) ? 0 (mod
4), Theorem 3.2 applies to K(V;U). Let (Zv [U;C4) be a 4CS of (?+m)K(V;U).
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
If u = 3, adjoin vertex 0 2Zv to the set U creating U0 = fn1;n2;n3;0g. Let (U0;C3)
be a 4CS(u + 1 = 4;? + m). Clearly, the degree of each vertex in (? + m)K(Zv nf0g;U)
34
is even and, as u + v is (? + m)-admissible, the number of edges remaining is divisible by
4. Therefore, by Theorem 3.2, the remaining edges can be decomposed into 4-cycles. Let
(Zv nf0g[U;C4) be a 4CS of (?+m)K(Zv nf0g;U).
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
Case 3: Suppose m ? 3 (mod 4). Then (?+m) ? 1 (mod 4). And for u ? 0, 1, 4, or
5 (mod 8), u ? 1, 0, 5, or 4 (mod 8), respectively. Let (V [U;C5) be a 4CS(u+v;1) (this
exists by Table 3.1). We then proceed in the same manner as Case 2.
Case 4: Suppose m ? 0 (mod 4). Then (?+m) ? 2 (mod 4).
If v ? 0 or 4 (mod 8), then u ? 0, 1, 4, or 5 (mod 8) (not respectively). In all cases, v
is m-admissible and u is (? + m)-admissible. Let (V;C2) be a 4CS(v;m) and (U;C3) be a
4CS(u;?+m). And, by Theorem 3.2, let (V [U;C4) be a 4CS of (?+m)K(V;U).
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
If v ? 1 or 5 (mod 8), then u ? 0, 3, 4, or 7 (mod 8) (not respectively). Let (V [U;C3)
be a 4CS(v +u;2) (this exists by Table 3.1). Then, as in Case 2, there exists an enclosing
(Zv [U;C4) of (?+m?2)Kv+u.
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
We will continue in much the same fashion as Proposition 3.2 using the same construc-
tions found in Proposition 3.1 with ? ? 3 (mod 4)
Proposition 3.3. Let v;?;m, and u be positive integers with v ? 4, u ? 3, and ? ?
3 (mod 4). Then every 4CS(v;?) can be enclosed in a 4CS(v + u;? + m), if v + u is
(?+m)-admissible.
Proof We will proceed case by case based on the congruence of m (mod 4) and the possible
values of u. Again, we assume V =Zv.
Let C = (Zv;C1) be a 4CS(v;?). Since v is ?-admissible, by Table 3.1 we see that
jZvj = v ? 1 (mod 8). Let U = fn1;n2;:::;nug with U \Zv = ; and form an enclosing
4CS(v +u;C0) of C as follows.
35
Case 1: Suppose m ? 1 (mod 4). Then (?+m) ? 0 (mod 4).
(i) Let u be even. By Table 3.1 there exists a 4CS(v;m), say (Zv;C2). Since u ? 4
(being even), there exists a 4CS(u;?+m), (U;C3), and a 4CS(v+u;C4) of (?+m)K(V;U).
Therefore, we get an enclosing in a similar fashion as in Proposition 3.1 Case 1 (i).
(ii) Let u be odd. Then there exists a 4CS(v;m), say (Zv;C2). Adjoin vertex 0 2Zv
to the set U creating U0 = fn1;n2;:::;nu;0g. We then continue to construct our enclosing
just as in Proposition 3.1 Case 1 (ii).
Case 2: Suppose m ? 0 or 2 (mod 4). Then (? + m) ? 1 or 3 (mod 4), respectively,
and it must be that u ? 0 (mod 8) (by Table 3.1). So there exists a 4CS(u+1;?+m), say
(U0;C3), and let (Zv nf0g[U;C4) be a 4CS of (?+m)K(Zv nf0g;U). We then construct
our enclosing just as in Proposition 3.1 Case 1 (ii).
Case 3: Suppose m ? 3 (mod 4). Then (? + m) ? 2 (mod 4), and it must be that
u ? 0 or 3 (mod 4).
(i) If u ? 0 (mod 4), then we proceed as in Proposition 3.1 Case 1 (i) with a 4CS(v;m),
say (Zv;C2), a 4CS(u;? + m), say (U;C3), and flnally, (Zv [ U;C4) being a 4CS of (? +
m)K(V;U) giving us our desired enclosing.
(ii) If u ? 3 (mod 4), then we proceed as in Proposition 3.1 Case 1 (ii) by adjoining
vertex 0 2 Zv to the set U creating U0 = fn1;n2;:::;nu;0g. Let (U0;C3) be a 4CS(u +
1;? + m) (see Table 3.1). This leaves the edges of (? + m)K(Zv nf0g;U) remaining. Let
(Zv n f0g [ U;C4) be a 4CS of (? + m)K(Zv n f0g;U). Then it is clear that (Zv [ U,
C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
Proposition 3.4. Let v;?;m, and u be positive integers with v ? 4, u ? 3, and ? ?
0 (mod 4). Then every 4CS(v;?) can be enclosed in a 4CS(v + u;? + m), if v + u is
(?+m)-admissible.
Proof We will proceed case by case based on the congruence of m (mod 4) and the possible
values of u. Again, we assume V =Zv.
36
Let C = (Zv;C1) be a 4CS(v;?). Since v is ?-admissible, by Table 3.1 we see that
jZvj = v can take on all values ? 4. Let U = fn1;n2;:::;nug with U \Zv = ; and form an
enclosing 4CS(v +u;C0) of C as follows.
Case 1: Suppose m ? 1 (mod 4). Then (? + m) ? 1 (mod 4). And, for each value of
v ?0, 1, 2, 3, 4, 5, 6, or 7 (mod 8), u ? 1, 0, 7, 6, 5, 4, 3, or 2 (mod 8), respectively. Let
(U [V;C5) be a 4CS(v +u;1). Then let (V;C2) be a 4CS(v;m?1), if there are any edges
left and, if u ? 4, then let (U;C3) be a 4CS(u;? + m?1) (these exist by Table 3.1). By
Theorem 3.2, there exists a 4CS of (?+m?1)K(U;V), say (V [U;C4).
If u = 3, then we proceed as in Proposition 3.2 Case 2. Adjoin vertex 0 2 Zv to the
set U creating U0 = fn1;n2;n3;0g. Let (U0;C3) be a 4CS(u + 1 = 4;? + m?1). Clearly,
the degree of each vertex in (? + m?1)K(Zv nf0g;U) is even and, as u + v is (? + m)-
admissible, the number of edges remaining is divisible by 4. Therefore, by Theorem 3.2,
the remaining edges can be decomposed into 4-cycles. Let (Zv nf0g[U;C5) be a 4CS of
(?+m?1)K(Zv nf0g;U).
Then (Zv [U, C1 [C2 [C3 [C4 [C5 = C0) is clearly a 4CS(v +u;?+m) containing
C.
Case 2: Suppose m ? 2 (mod 4). Then (? + m) ? 2 (mod 4). And, for each value of
v ?0 (mod 4), u ? 0, 1, 4, or 5(mod 8). If v ?1 (mod 4), u ? 0, 3, 4, or 7(mod 8). If v ?2
(mod 4), u ? 2, 3, 6, or 7(mod 8). And, if v ?3 (mod 4), u ? 1, 2, 5, or 6(mod 8).
In all cases except when u = 3 we can construct our enclosing in the following way.
Let (U [V;C5) be a 4CS(v + u;2). Then let (V;C2) be a 4CS(v;m?2), if there are any
edges left, and (U;C3) be a 4CS(u;?+m?2) (these exist by Table 3.1). By Theorem 3.2,
there exists a 4CS of (?+m?2)K(U;V), which we denote by (V [U;C4).
If u = 3, we proceed as in Case 1. Adjoin vertex 0 2 Zv to the set U creating
U0 = fn1;n2;n3;0g. Let (U0;C3) be a 4CS(u+1 = 4;?+m?2). Clearly, the degree of each
vertex in (?+m?2)K(Zv nf0g;U) is even and, as u+v is (?+m)-admissible, the number
of edges remaining is divisible by 4. Therefore, by Theorem 3.2, the remaining edges can
be decomposed into 4-cycles. Let (Zv nf0g[U;C5) be a 4CS of (?+m?2)K(Zv nf0g;U).
37
In any case, (Zv [ U, C1 [ C2 [ C3 [ C4 [ C5 = C0) is clearly a 4CS(v + u;? + m)
containing C.
Case 3: Suppose m ?3 (mod 4). Then (? + m) ? 3 (mod 4). And, for each value of
v ?0, 1, 2, 3, 4, 5, 6, or 7 (mod 8), u ? 1, 0, 7, 6, 5, 4, 3, or 2 (mod 8), respectively. Let
(U [V;C5) be a 4CS(v +u;3). Then let (V;C2) be a 4CS(v;m?3), if there are any edges
left, and (U;C3) be a 4CS(u;?+m?3) (these exist by Table 3.1). By Theorem 3.2, there
exists a 4CS of (?+m?3)K(U;V), which we denote by (V [U;C4).
If u = 3, we have to proceed as in Case 1. Adjoin vertex 0 2Zv to the set U creating
U0 = fn1;n2;n3;0g. Let (U0;C3) be a 4CS(u+1 = 4;?+m?3). Clearly, the degree of each
vertex in (?+m?3)K(Zv nf0g;U) is even and, as u+v is (?+m)-admissible, the number
of edges remaining is divisible by 4. Therefore, by Theorem 3.2, the remaining edges can
be decomposed into 4-cycles. Let (Zv nf0g[U;C5) be a 4CS of (?+m?3)K(Zv nf0g;U).
In any case, (Zv [ U, C1 [ C2 [ C3 [ C4 [ C5 = C0) is clearly a 4CS(v + u;? + m)
containing C.
Case 4: Suppose m ?0 (mod 4). Then (? + m) ? 0 (mod 4). So u is unrestricted by
the necessary conditions.
Then let (V;C2) be a 4CS(v;m), and, if u ? 4, let (U;C3) be a 4CS(u;? + m). By
Theorem 3.2, there exists a 4CS of (?+m)K(U;V), which we denote by(V [U;C4).
If u = 3, we proceed in a similar manner as in Case 2. Let (V;C2) be a 4CS(v;m).
We then adjoin vertex 0 2 Zv to the set U creating U0 = fn1;n2;n3;0g. Let (U0;C3) be
a 4CS(u + 1 = 4;? + m). By Theorem 3.2, the remaining edges can be decomposed into
4-cycles. Let (Zv nf0g[U;C4) be a 4CS of (?+m)K(Zv nf0g;U).
In any case, (Zv [U, C1[C2[C3[C4 = C0) is clearly a 4CS(v+u;?+m) containing
C.
3.3 Enclosings when u = 2
In this section we prove that Theorem 3.1 is true in the case where u = 2.
38
Proposition 3.5. Let v;?;m, and u be positive integers with v ? 4 and u = 2. Then every
4CS(v;?) can be enclosed in a 4CS(v +u;?+m), if v +u is (?+m)-admissible.
Proof Let C = (Zv;C1) be a 4CS(v;?). Since v is ?-admissible, by Table 3.1 we see that
jZvj = v ? 7 (mod 8) when (?+m) ? 1 or 3 (mod 4). v ? 2, 3, 6, or 7 if (?+m) ? 2 (mod
4). Finally, v can take on all values ? 4 if (? + m) ? 0 (mod 4). Let U = fuH;uTg with
U \Zv = ; and form an enclosing 4CS(v +u;C0) of C as follows.
Case 1: Suppose (?+m) ? 1 or 3 (mod 4). Since jUj = 2 it must be that v ? 7 (mod
8). Thus ? ? 0 (mod 4) and m ? 1 or 3 (mod 4). Let (V;C2) be an equitable, partial
4CS(v;m) containing mv(v ? 1)=2 ? (? + m) edges. This exists by Lemma 3.1. Let H
be the complement of (V;C2). H is clearly an even graph though possibly not connected.
Apply an orientation to each edge in each component to have a directed Eulerian circuit.
For each directed edge, take the following edges to create a 4-cycle: the directed edge, the
edge connected to the head vertex and uH, the edge connected to the tail vertex and uT,
and the edge between uH and uT. Let (U [V;C3) be 4CS of the aforementioned edges.
The remaining edges of (? + m)K(Zv;U) consist of those between Zv and U. Let G?
be the graph on Zv [U that is the complement of the edges in C1;C2; and C3. jE(G?)j =
2(? + m)v ?2(? + m) = 2(? + m)(v ?1). Thus, 4 divides jE(G?)j. uH and uT each have
degree (? + m)(v ? 1) which is even. And, each vertex in Zv has degree either 2(? + m)
or 2(? + m)?d where d is the degree of the vertex in H. As H was an even graph, these
vertices have even degree. Therefore, Theorem 3.2 applies. Let (Zv [ U;C4) be a 4CS of
(?+m)K(Zv;U)?H.
Then (Zv [U, C1 [C2 [C3 [C4 = C0) is clearly a 4CS(v +u;?+m) containing C.
Case 2: Suppose (? + m) ? 2 (mod 4). Since jUj = 2, it must be that v ? 2, 3,
6, or 7 (mod 8). Thus ? ? 0 (mod 4). We then proceed as in Case 1 taking note that
2(?+m)(v ?1) is divisible by 4, and the degrees of G? for each vertex is divisible by 2.
Case 3: Suppose (? + m) ? 0 (mod 4). v can therefore take on all values ? 4. When
v ? 2, 3, 6, or 7 (mod 8), ? ? 0 (mod 4) and m ? 0 (mod 4). If v ? 0, 4, or 5 (mod 8),
? ? 0 or 2 (mod 4); therefore, m ? 0 or 2 (mod 4), respectively. If v ? 1 (mod 8), ? ? 0,
39
1, 2, or 3 (mod 4). In any case, we proceed as in Case 1 noting that 4 divides jE(G?)j, and
2 divides the degrees of G?.
T
V
H
Figure 3.2: Connecting the Euler Tour (2 4-cycles constructed as an example)
3.4 Conclusion
We have provided constructions for all possible enclosings for u ? 2, providing the
su?ciency of Theorem 3.1 (Through Propositions 3.1-3.5). The case when u = 1 looks
to be particularly di?cult. Since 3 vertices must be in V, a decomposition of mKV into
2-paths (denoted P2) and 4-cycles must be obtained. This concept is not di?cult on its
own, but the di?culty arises, in that, the end of each P2 must be connected to the u vertex,
requiring each v vertex to be at the end of (? + m) P2?s while the remaining edges would
still need to be decomposable into 4-cycles. Thus we need an equalized P2 with a 4-cycle
decomposition where the ends of each P2 are evenly distributed among the v vertices. The
40
flgure below illustrates this problem. Work will be continued on this problem in order to
completely solve the enclosings of 4-cycle systems.
2
V
u
4?cycle
P ?s need to be equalized
Figure 3.3: Constructing 4-cycles from P2?s
41
Chapter 4
Conclusions
It is disconcerting to the author that, despite much work, neither case has been com-
pletely solved. Due to the complexity of the quadratic necessary bounds found by Hurd et
al [13], the enclosings of ?-fold Triples Systems is incomplete. It is worthy to note that the
constructions presented in Chapter 2 are fairly comprehensive where the parameters are
concerned. And, it is the belief of the author that the bounds on the remaining enclosings
will be di?cult to pare down. The author believes that a modiflcation of the constructions
presented will flll the remaining \holes". The di?culty arises in the scale on which this must
be done, ranging over four parameters while manipulating multiple construction techniques
will not be a simple endeavor.
In the case of the enclosings of the ?-fold 4-cycle systems, the only situation left unad-
dressed is when u = 1. A new approach may be necessary in this case, but it is the hope of
the author that this will have a constructive proof similar to those presented in Chapter 3.
These enclosings naturally lead to the question of enclosing larger ?-fold cycle systems
(k-cycle systems with k ? 5). In particular, embeddings for partial cycle systems have
been shown to exist [11, 16], and the author believes that at least the generalization of
enclosing ?-fold even-cycle systems can be proved in a similar fashion as the enclosings of
?-fold 4-cycle systems presented in Chapter 3.
Another natural question is: Can a non-proper subsystem be enclosed in a larger
(? + m)-fold k-cycle system? That is, for what values of ?;v;u; and m can the edges of
(?+m)Kv+u with those in a particular copy of ?Kv removed be partitioned into 4-cycles.
In other words, does there exist a k-cycle system of (? + m)Kv+u n ?Kv? Notice that if
there exists a 4-cycle system of ?Kv, then this question is addressed in this dissertation.
This leads to the following conjecture:
42
Conjecture 4.1. Let u ? 1. There exists a 4-cycle system of (?+m)Kv+u n?Kv ifi
(a) (v +u?1)(?+m) ? 0 (mod 2), and
(b) u(u?1)(?+m)=2+mv(v ?1)=2+vu(?+m) ? 0 (mod 4).
(c) u(?+m)+m(v ?1) ? 0 (mod 2)
Proof (of Necessary Conditions)
Conditions (a) and (b) follow from Theorem 3.1. The graph contains vertices of degree
u(?+m)+m(v?1). Since each degree must be even, the necessity of condition (c) follows.
The author believes that many of the constructions presented can be reused for the
question at hand and that it is mostly an exercise in narrowing down the admissible pa-
rameters.
43
Bibliography
[1] L. D. Andersen, A. J. W. Hilton, and E. Mendelsohn, Embedding partial Steiner triple
systems. Proc. London Math. Soc. 41. (1980) 557-576.
[2] E.J. Billington, H. Fu, C.A. Rodger, Packing Complete Multipartite Graphs with 4-
cycles, J Combin Designs, 9 (2001), 107-127.
[3] D. Bryant, D. G. Hofiman, C. A. Rodger, 5-Cycle Systems with Holes Full, Designs,
Codes and Cryptography 8 (1996), 103-108.
[4] D. Bryant, D. Horsely, A proof of Lindner?s conjecture on embeddings of partial Steiner
triple systems, preprint.
[5] D. Bryant, D. Horsely, B. Maenhaut, Decompositions into 2-regular subgraphs and
equitable partial cycle decompositions, Journal of Combinatorial Theory Series B 93
(2005), 67-72.
[6] C. J. Colbourn, R. C. Hamm, A. Rosa, Embedding, immersing, and enclosing. Pro-
ceedings of the sixteenth Southeastern international conference on combinatorics, graph
theory and computing, (Boca Raton, Fla., 1985). Congr. Numer. 47 (1985), 229-236.
[7] J. Doyen, R. M. Wilson, Embeddings of Steiner triple systems Discrete Math 5 (1973),
229-239.
[8] H. L. Fu, and C. A. Rodger, Group divisible designs with two associate classes: n=2
or m=2, J. of Combin. Theory, Series A 83 (1998), 94-117.
[9] H. L. Fu, and C. A. Rodger, 4-Cycle Group-divisible designs with two associate classes,
Combinatorics, Probability and Computing 10 (2001), 317-343.
[10] Jane Hahn, \LATEX For Everyone," Personal TeX Inc., 12 Madrona Street, Mill Valley,
California.
[11] P. Horak, C. C. Lindner, A small embedding for partial even-cycle systems, Journal of
Combinatorial Designs 7 (1999), 205-215.
[12] J.D. Horton, C.C. Lindner, C. A. Rodger, A small embedding for partial 4-cycle sys-
tems. JCMCC 5 (1989), 23-26.
[13] S. P. Hurd, P. Munson, D. G. Sarvate, Minimal enclosings of triple systems I: adding
one point, Ars Combin., 68 (2003), 145-159.
44
[14] S. P. Hurd, D. G. Sarvate, Minimal enclosings of triple systems II: increasing the index
by 1, Ars Combin., 68 (2003), 263-282.
[15] C. C. Lindner, A Partial Steiner Triple System of Order n Can Be Embedded in a
Steiner Triple System of Order 6n + 3. J. Comb. Theory, Ser. A 18(3): (1975)
349-351.
[16] C. C. Lindner, C. A. Rodger, A partial m = (2k + 1)-cycle system of order n can be
embedded in an m-cycle system of order (2n+1)m, Discrete Mathematics 117 (1993),
151-159.
[17] C. C. Lindner, and C. A. Rodger, Design Theory, CRC Press, Boca Raton, 1997.
[18] N. A. Newman, C. A. Rodger, Enclosings of ?-fold triple systems, Utilitas Math, (to
be published).
[19] J. Schonheim, A. Bialistocki, Packing and covering the complete graph with 4-cycles,
Can. Math. Bull. 18 (1975), 703-708.
[20] D. Sotteau, Decompositions of Km;n(K?m;n) into cycles of length 2k, J. Combin. Theory
Ser. B, 30 (1981), 75-81.
[21] C. Treash, The completion of flnite incomplete Steiner triple systems with applications
to loop theory, J. Combin. Theory Ser. A 10 (1971), 259265.
[22] D. B. West, Introduction to Graph Theory, Prentice Hall 2001.
45