Hamiltonian Decompositions of Complete Multipartite Graphs with Speci ed
Leaves
by
Laura McCauley
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial ful?llment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
May 9, 2011
Keywords: hamilton cycle, decomposition, 2-factor, complete multipartite
Copyright 2011 by Laura McCauley
Approved by
Chris Rodger, Chair, C. Harry Knowles Professor for Research in Mathematical Instruction
Dean Ho?man, Professor of Mathematics and Statistics
Peter D. Johnson Jr., Professor of Mathematics and Statistics
Abstract
For any 2-regular spanning subgraph G and H of the complete multipartite graph K
with p parts each of size m, conditions are found which guarantee the existence of a 2-
factorization of K or of K ?I (for some 1-factor I) in which
1. the ?rst and second 2-factors are isomorphic to G and H respectively, and
2. each other 2-factor is a hamilton cycle.
These conditions are necessary and su?cient when m is odd, and solve the problem when m
is even providing that m and p are each at least 6.
ii
Acknowledgments
To my wonderful son, Quinlan Porter?eld, my ?ancee, Jason Porter?eld, my mother,
Bonnie McCauley, my father, Brian McCauley, and my siblings and their families, for their
love, support, and patience. Also, the support, patience, and guidance of my advisor, Chris
Rodger, and professors Dean Ho?man and Pete Johnson were pivotal.
iii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 The Case when mp is Odd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 The Case when p is Even . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1 A Number Theoretic Result . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 The Case when p is Even . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Another Number Theoretic Result . . . . . . . . . . . . . . . . . . . . . . . . . 17
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
iv
List of Figures
1.1 Referring to Lemma 1.2 with F? = C4 ?C5 and x = 1 . . . . . . . . . . . . . . . 3
2.1 K(m,p), using di?erences of 1 and 5 to produce a C3?C3?C3?C6 and a hamilton
cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1 K(3,3) represented as a K9 with edges of di?erence 3 removed . . . . . . . . . . 12
v
Chapter 1
Introduction
1.1 History
One of the challenging problems over the past 30 years has been the Oberwolfach
problem and its natural generalizations. The original problem requires one to ?nd a 2-
factorization of Kn in which all the cycles have the same length; this problem was solved
over a decade ago [2, 8]. A much studied generalization of this problem is to simply require
that each of the 2-factors be isomorphic to each other. To solve this would be an amazing
feat, as so many possible 2-factors exist. Some progress has been made, including a com-
plete solution when n ? 17 [1], and in many cases where each 2-factor contains just two
cycle lengths (see [5] for a survey of results).
Another direction in which research has developed is to allow a small number of the
2-factors to be anything, but then stipulate that the remaining 2-factors be hamilton cycles.
Extending a result of Buchanan [6], in 2004 Bryant [4] found necessary and su?cient condi-
tions for the existence of 2-factorizations of Kn and of Kn?I, where Kn?I is the complete
graph on n vertices with a 1-factor I removed, in which the cycle lengths in up to three
of the 2-factors are freely speci?ed, and all remaining 2-factors are hamilton cycles. Inde-
pendently, Rodger [10] used a similar observation to settle the existence of 2-factorizations
of all complete multipartite graphs, and of all complete multipartite graphs with a 1-factor
removed, in which one 2-factor is freely speci?ed and the rest of the 2-factors are hamilton
cycles. One can think of this as the existence of a hamilton decomposition of the graph
formed from K(m,p) (the complete multipartite graph with m vertices in each of p parts)
or from K(m,p) ? I by removing any 2-factor. Thought of in this way, the result has a
relative in the world of matchings, where Plantholt [9] showed that the removal of any set
1
of x edges from K2x+1 results in a graph whose edges can be partioned into 2x matchings
(2x + 1 matchings are needed if fewer edges are removed).
In this paper, we extend the result of Rodger, ?nding necessary and su?cient conditions
for the existence of a hamilton decomposition of the graph K(m,p) by removing the edges of
any two 2-factors. More formally, for any two 2-regular graphs G and H of order mp, when
m is odd we ?nd necessary and su?cient conditions for the existence of a 2-factorization,
{F1,F2,...,F?m(p?1)?/2}, of K(m,p) such that G ?= F1,H ?= F2, and Fi is a hamilton cycle for
3 ? i ? ?m(p?1)?/2.
1.2 Preliminary Results
Before we can get to the results, some notation, lemmas, and theorems must be intro-
duced. In this paper we use Zn to denote the vertex set of a graph on n vertices. This allows
us to de?ne the di?erence of the edge {i,j} to be d(i,j) = min{j ? i,n ? (j ? i)} where
i < j; thus n/2 ? d(i,j) > 0. Let ?d1,d2,...,dx?n be the subgraph induced by the edges with
di?erences in {d1,d2,...,dx}. Bermond et al [[3]] proved the following useful result that shows
when the edges of two di?erences can be used to form two edge-disjoint hamilton cycles. If
A is a set of positive integers, let gcd(A) denote the greatest common divisor of the elements
of A. A hamilton cycle decomposition of the graph G is a 2-factorization of G, each 2-factor
in which is a hamilton cycle.
Theorem 1.1. [3] Let s,t, n be positive integers with s < t < n/2. If gcd({s,t,n}) = 1
then the graph ?s,t?n has a hamilton cycle decomposition.
The next lemma was proven separately by both Bryant and Rodger. It provides a key
method used to prove our results.
Lemma 1.2. [4, 10] Let n ? 5 and let F? be any 2-regular graph of order n. If gcd({x,n}) = 1
then the subgraph ?x,2x?n of Kn has a 2-factorization {F,H} such that H is a hamilton
cycle and F? ?= F. (See Figure 1.1)
2
Figure 1.1: Referring to Lemma 1.2 with F? = C4 ?C5 and x = 1
Now, we will introduce some speci?c results that will be used to clear up some of the
cases we will encounter. Presented ?rst is the result from Bryant?s paper previously alluded
to; one might also see the related results in [1, 7].
Theorem 1.3. [4] Let n ? 7 be odd and let F?1,F?2, and F?3 be any three 2-regular graphs
of order n. Then there exists a 2-factorization {F1,F2,...,F(n?1)/2} of Kn in which F1 ?= F?1,
F2 ?= F?2, F3 ?= F?3, and Fi is a hamilton cycle for 4 ? i ? (n ? 1)/2, except that when
(n,F?1,F?2,F?3) ? {(7,C3?C4,C3?C4,C7),(9,C3?C3?C3,C3?C3?C3,C3?C3?C3),(9,C3?
C3?C3,C3?C3?C3,C3?C6),(9,C3?C3?C3,C3?C3?C3,C4?C5)} no such two factorization
exists.
Next we present Rodger?s result.
Theorem 1.4. [10] Let p ? 3 and m ? 1. Let H be any 2-factor in K(m,p). There exists
a partition of the edge set of K(m,p), one set in which induces a graph isomorphic to H, if
m(p?1) is odd then one set induces a 1-factor, and each other set induces a hamilton cycle.
The rest of the dissertation is organized as follows:
3
Chapter 2
The Case when mp is Odd
In this chapter we settle the existence of the speci?ed 2-factorization when mp is odd.
The proof relies heavily on Theorem 1.1, but in the case where (m,p) = (5,3) several small
cases must be considered in another way; this is accomplished by using a neat switching
method.
Theorem 2.1. Let m be odd. Let G and H be any two 2-regular graphs of order mp. There
exists a 2-factorization {F1,F2,...,F?m(p?1)?/2} of K(m,p) such that F1 ?= G, F2 ?= H, Fi is
a hamilton cycle for 3 ? i ? ?m(p?1)?/2, if and only if
1. p is odd, and
2. (m,p,G,H) /? {(1,7,C3?C4,C3?C4),(3,3,C3?C3?C3,C3?C3?C3),(3,3,C3?C3?
C3,C3 ?C6),(3,3,C3 ?C3 ?C3,C4 ?C5)}.
Proof. If K(m,p) is to have a 2-factorization, all vertices must have even degree, so m(p?1)
must be even, so the ?rst condition is necessary since we are assuming that m is odd. Once
one observes that the edges removed from K9 to form K(3,3) can be thought of as the edges
in C3 ?C3 ?C3, Theorem 1.3 clearly proves the four cases described in the second condition
cannot be obtained. So we now turn to a proof of the su?ciency.
Since K(m,p) is an m(p?1)-regular graph, and since it is assumed to contain at least
two 2-factors, we know that m(p ? 1) ? 4. So, since we also know that p is odd, clearly
p ? 3.
Notice that if we let the jth part of K(m,p) be {ip+j | i ? Zm} for j ? Zp then the edges
of K(m,p) are the same as the edges of the complete graph Kmp with edges of di?erence
ip, 1 ? i ? ?m/2? removed. Therefore we will partition the edges of K(m,p) by their
4
di?erences, namely by the di?erences in the di?erence set D = {1,2,...,?(mp)/2?}\{ip |
1 ? i ? ?m/2?}. We now consider several cases in turn.
Case 1: Suppose mp ? 21. Then {1,2,4,8} ? D. By Lemma 1.2, ?1,2?mp and ?4,8?mp
each have a 2-factorization consisting of any 2-factor and a hamilton cycle; so we can choose
the two 2-factors to be isomorphic to G and H respectively. It remains to partition the
remaining edges into sets that induce hamilton cycles. We consider 4 subcases in turn.
Case 1(a): Suppose that p ? 9. By pairing all except possibly the last of the di?erences
in D\{1,2,4,8} = D? in increasing order (that is, form pairs {3,5},{6,7},...) we produce
pairs of the form either {d,d + 1} or {d,d + 2}, for some d ? D?.
Since gcd({mp,(d+1)?d}) = gcd({mp,1}) = 1, it follows that gcd({d,d+1,mp}) = 1.
Also, since mp is odd, gcd({mp,(d + 2)?d}) = gcd({mp,2}) = 1 means that gcd({mp,d +
2,d}) = 1. Also, if |D| is odd, then the last di?erence, (mp? 1)/2, is not paired, but since
gcd({mp,(mp ? 1)/2}) = 1, the edges with di?erence (mp ? 1)/2 form a hamilton cycle.
Therefore, by Theorem 1.1, there exists a hamilton cycle decomposition of the subgraph
induced by the remaining edges.
Case 1(b): Suppose that p = 7. If m = 3 then the result follows from Theorem
1.3, since we can choose each component in F?3 to be a 3-cycle, then remove these edges
to form the independent vertices in the parts of K(3,7). In all other cases (so mp > 21),
?rst form the pairs {3,5},{6,10}, and {9,11} in turn (these exist since mp > 21). Notice
that: gcd(3,5,mp) divides gcd(5 ? 3,mp) = 1 since mp is odd; the gcd(6,10,mp) divides
gcd(10 ? 6,mp) = 1 since mp is odd; and, similarly, gcd(9,11,mp) = 1. All other pairs are
of the form {d,d + 1} or {d,d + 2}. Therefore we can apply Theorem 1.1 to each pair in
turn to form sets of edges that induce hamilton cycles.
Case 1(c): Suppose that p = 5. If mp ? 35 then apply Theorem 1.1 to each of the
pairs {3,7},{6,14},{12,13}, and {9,11} in turn. Pair the remaining di?erences in order
and proceed as in Case 1a.
5
If mp < 35 then mp = 25. Apply Theorem 1.1 to each of the pairs {3,6},{7,9}, and
{11,12} in turn.
Case 1(d): Suppose that p = 3. Pair the remaining di?erences in order and proceed
as in Case 1a.
Case 2: Suppose mp ? 20 and (m,p) ?= (5,3). If m = 1 then K(1,p) is just the
complete graph Kp, so the result follows from Theorem 1.3. If m = 3 then p ? {3,5} so the
result also follows from Theorem 1.3, since when m = 3, the edges one removes from Kmp
to form K(m,p) induce the 2-factor consisting of p 3-cycles; consider this to be the third
speci?ed 2-factor.
Case 3: Suppose (m,p) = (5,3). This case takes substantial e?ort to settle. It is
too small to be able to apply Lemma 1.2 twice and be left with a di?erence that induces
a hamilton cycle. The set of available di?erences is {1,2,4,5,7}, and Lemma 1.2 could be
applied to the graphs ?1,2?15 and ?4,8?15 (since di?erence 7 is the same as di?erence 8), but
that leaves di?erence 5 that induces ?ve 3-cycles. So we do apply Lemma 1.2 to ?4,8?15
to obtain F1, then obtain F2 from ?1,2,5?15 in such a way that the edges left over form
two hamilton cycles. We consider the various possible cycle lengths, c1,c2,...,cx of the x
components of F2 in turn, written as l = (c1,c2,...,cx).
We begin with the cases in which all the cycle lengths in F2 are divisible by 3. To
construct the required cycles, we always include the hamilton cycle ?2?15, then swap edges
in ?1?15 with edges in ?5?15 to fuse components in ?5?15. In each case, we begin with l, then
describe how to form F2.
(3,3,3,3,3) : ?1?15 and ?2?15 are hamilton cycles, and di?erence 5 induces F2.
(3,3,3,6): Swap edges {0,1} and {5,6} in ?1?15 with edges {0,5} and {1,6} in ?5?15 to
produce the hamilton cycle (0,5,4,3,2,1,6,7,...,14) and the graph consisting of the
cycles (0,1,11,6,5,10),(2,7,12),(3,8,13), and (4,9,14) respectively. The next few cases
proceed similarly, so we simply present the edges to be swapped. (Refer to Figure 2.1.)
6
(3,3,9): Swap edges {0,1},{5,6},{6,7}, and {11,12} in ?1?15 with edges
{0,5},{1,6},{6,11}, and {7,12} in ?5?15 (so just switch two more edges from the (3,3,3,6)
case).
(3,12): Swap edges {0,1},{2,3},{5,6},{6,7},{7,8}, and {11,12} in ?1?15 with edges
{0,5},{1,6},{2,7},{3,8}, {6,11}, and {7,12} in ?5?15 (so just switch two more edges from
the (3,3,9) case).
(3,6,6): Swap edges {0,1},{5,6},{7,8}, and {12,13} in ?1?15 with edges
{0,5},{1,6},{7,12}, and {8,13} in ?5?15 (so just switch two more edges from the (3,3,3,6)
case).
(6,9): Swap edges {0,1},{3,4},{5,6},{6,7},{8,9}, and {11,12} in ?1?15 with edges
{0,5},{1,6},{3,8},{4,9},{6,11}, and {7,12} in ?5?15 (so just switch two more edges from
the (3,3,9) case).
Figure 2.1: K(m,p), using di?erences of 1 and 5 to produce a C3 ? C3 ? C3 ? C6 and a
hamilton cycle
All but one of the remaining cases are obtained by producing F2 using Lemma 1.2, then
switching edges between the resulting hamilton cycle and ?5?15 to obtain 2 hamilton cycles.
7
Since it is more complicated to describe, we simply provide the resulting decompositions of
?1,2,5?15.
(3,4,4,4): (0,1,14,13),(2,3,5,4),(6,7,8),(9,10,12,11),
(0,5,10,8,3,13,12,7,2,1,11,6,4,9,14),
(0,2,12,14,4,3,1,6,5,7,9,8,13,11,10).
(3,3,4,5) : (4,5,6),(11,12,13),(7,8,10,9),(0,2,3,1,14),
(0,10,12,2,7,5,3,8,6,1,11,9,4,14,13),
(0,5,10,11,6,7,12,14,9,8,13,3,4,2,1).
(5,5,5): (0,2,3,1,14),(4,6,8,7,5),(9,10,12,13,11),
(0,5,10,11,6,1,2,12,7,9,14,4,3,8,13),
(0,10,8,9,4,2,7,6,5,3,13,14,12,11,1).
(4,5,6): (10,11,13,12),(5,6,8,9,7),(0,2,4,3,1,14),
(0,1,11,9,4,6,7,2,12,14,13,3,8,10,5),
(0,10,9,14,4,5,3,2,1,6,11,12,7,8,13).
(4,4,7): (6,8,9,7),(10,12,13,11),(0,2,4,5,3,1,14)
(0,5,7,2,12,14,4,6,1,11,9,10,8,3,13),
(0,10,5,6,11,12,7,8,13,14,9,4,3,2,1).
(3,5,7): (11,12,13),(6,7,9,10,8),(0,2,4,5,3,1,14),
(0,5,7,2,1,6,11,10,12,14,4,9,8,3,13),
(0,10,5,6,4,3,2,12,7,8,13,14,9,11,1).
(3,4,8): (0,5,10),(1,2,7,6),(3,4,14,9,11,12,13,8),
(0,1,3,2,4,5,6,11,10,9,8,7,12,14,13),
(0,2,12,10,8,6,4,9,7,5,3,13,11,1,14).
(5,10): (0,2,4,6,8,7,5,3,1,14),(9,11,13,12,10),
(0,5,4,14,9,8,13,3,2,12,7,6,1,11,10),
(0,1,2,7,9,4,3,8,10,5,6,11,12,14,13).
8
(4,11): (0,2,4,6,8,9,7,5,3,1,14),(10,12,13,11),
(0,5,4,14,12,2,7,6,1,11,9,10,8,3,13),
(0,1,2,3,4,9,14,13,8,7,12,11,6,5,10).
9
Chapter 3
The Case when p is Even
3.1 A Number Theoretic Result
We begin this chapter with a general number theoretic result that will be used exten-
sively in Section 3.2. The rest of this chapter deals with the case where p is even.
Lemma 3.1. Let m,p ? Z+ with p ?= 1. Then there exists an f ? Z such that gcd(f,mp) =
1, f ? ?1(mod p), and 0 < f < mp.
Proof. De?ne Q = {q | q prime, q divides m, q does not divide p}. For each q ? Q, choose
1 ? aq ? q ?1. By the Chinese Remainder Theorem, there exists a unique f ? Z satisfying
1. f ? ?1(mod p) and
2. f ? aq(mod q) for each q ? Q
with 0 ? f < pD, where D is the product of all the elements of Q. Obviously, f ?= 0 since
p ? 2. Also, mp ? pD since D is a product of primes dividing m, so D divides m. Since
there are q?1 for each aq, there are ?(D) such f in each of the ranges tpD < f < (t+1)pD
for each 0 ? t < mp .
Corollary 3.2. In Lemma 3.1, there are ?(D)mD such f?s, where D is the product of all primes
which divide m but do not divide p, and ? is the Euler ?-function.
Proof. Referring to the proof of Lemma 3.1, each aq can be chosen in q ? 1 ways, so the
family of aq?s can be chosen in a total of ?q?Q(q ? 1) = ?(D) ways. This gives ?(D) f?s
(mod pD), and the interval from 0 to mp contains mD copies of the integers (mod pD).
Corollary 3.3. For p even, p ? 6,m ? 5, ?(D)mD ? 4.
10
Proof. Let us consider the possible value of ?(D)mD being 1, 2, or 3 in turn. First notice that,
by de?nition, 2 /? Q since p is even. Also, notice that ?(D) = 1 if and only if Q = {2}, by
de?nition of Q.
1. ?(D)mD = 1 if and only if both ?(D) and mD are 1. But we just showed that ?(D) ?= 1.
2. ?(D)mD = 2 if and only if ?(D) = 2 and mD = 1 or ?(D) = 1 and mD = 2. The second
option is not possible since ?(D) ?= 1. If ?(D) = 2 then either Q = {2,3} or Q = {3}.
Since 2 /? Q, Q = {3}. Therefore D = 3. This implies that m is also 3 since mD = 1.
This contradicts the assumption that m ? 6.
3. ?(D)mD = 3 if and only if ?(D) = 3 and mD = 1 or ?(D) = 1 and mD = 3. The second
option is not possible since ?(D) ?= 1. Also, since ?(D) = ?q?Q(q ? 1), where each q
is strictly prime, ?(D) ?= 3.
Thus, ?(D)mD ? 4.
3.2 The Case when p is Even
We now use Lemma 3.1 and Theorem 1.1 to settle the case when p is even, and m is
odd or even. When m is odd we will have the half-di?erence (1-factor), I.
Theorem 3.4. Let p be even, p ? 6,m ? 5, and suppose that G and H are any two 2-factors
of K(m,p). Then there exists a 2-factorization S = {F1,F2,...,F?m(p?1)/2?} of K(m,p) when
m is even and a 2-factorization of K(m,p) ? I when m is odd, such that F1 ?= G,F2 ?= H,
and Fi is a hamilton cycle for 3 ? i ? ?m(p?1)/2?.
Proof. Notice that if we let the jth part of K(m,p) be the vertex set {ip + j | i ? Zm} for
j ? Zp then K(m,p) is isomorphic to the subgraph of Kmp formed by removing the edges
of di?erence ip, 1 ? i ? ?m/2?. Therefore we will partition the edges of K(m,p) by their
di?erences in Kmp, namely by the di?erences in the di?erence set D = {1,2,...,mp/2}\{ip |
1 ? i ? ?m/2?}. (Refer to Figure 3.1.)
11
Figure 3.1: K(3,3) represented as a K9 with edges of di?erence 3 removed
We de?ne
[f] =
?
??
??
f if f < mp/2, and
mp?f if f > mp/2
so ?f?mp = ?[f]?mp. This special di?erence f will be chosen from D such that
1. f ? ?1(mod p),
2. gcd(f,mp) = 1,
3. 0 < f < mp, and
4. f /? {mp/2?1,mp?1}.
Since property 4 excludes two possible values of f described in Lemma 3.1, by Corollary 3.3
there are at least two choices for f. In most cases, just one value is used, but in Case 2,
both will be needed.
By Lemma 1.2, ?1,2?mp and ?f,2f?mp each have a 2-factorization consisting of any 2-
factor and a hamilton cycle; so we can choose the two 2-factors to be isomorphic to G and
H respectively. It remains to partition the remaining edges (di?erences) into sets that will
induce hamilton cycles by applying Theorem 1.1. If m is odd the half di?erence, mp/2, will
induce the 1-factor, I. We now consider several cases in turn.
Case 1: Suppose that p ? 0,1, or 3 (mod 4) or m ? 0,1, or 2 (mod 4). De?ne
D? = D\{1,2,f,2f,mp/2}. So either
12
i: |D?| is even or
ii: |D?| is odd and mp/2?1 is odd.
In the latter case, ?mp/2?1?mp induces a hamilton cycle which will be placed in S; so, in
this case, further modify D? by removing the di?erence mp/2 ? 1. So in both cases, |D?| is
even. If there are an odd number of di?erences in D? that are less than f or [f], then modify
D? to form D?? as follows.
Case 1(a): If 3 does not divide m or if 3 does not divide f ? 1 then remove the pair
{d,d + 3} from D? where
i: d = f ?1 if f < mp/2
ii: d = [f]?2 if f > mp/2.
Case 1(b): If 3 divides m and 3 divides f ?1 then remove the pair {d,d+9} from D?
where
i: d = f ?3 if f < mp/2
ii: d = [f]?4 if f > mp/2.
Consider this new set D?? (possibly D? = D??). Now pair the di?erences in D?? in
increasing order. We now show that Theorem 1.1 can be applied to each of the de?ned pairs.
That is, we will show that for each pair ? = {z1,z2}, gcd(z1,z2,mp) = 1.
We consider each of the possible pairs ? of di?erences in turn.
1. Suppose ? = ?d,d + 1? for some d ? D??. Then gcd(d,d+1,mp) divides gcd((d+1)?
(d),mp) = gcd(1,mp) = 1.
2. Suppose ? = ?d,d + 2? for some d ? D??. Notice that such a pair only occurs when
d+1 is a multiple of p, is 2f, is 2[f], or is [2[f]]. So, in each case, d and d+2 are both
odd. Thus, gcd(d,d+2,mp) divides gcd((d+2)?(d),mp) = gcd(2,mp) ? {1,2}. So,
since d is odd, gcd(d,d + 2,mp) = 1.
13
3. Suppose ? = ?d,d + 3?. Such pairs only occur in case 1(a). So, we consider the
situations in turn.
? 1(a)i: In this case d = f ?1, so we need to consider gcd(f ?1,f + 2,mp) which
divides gcd((f +2)?(f ?1),mp) = gcd(3,mp) ? {1,3}. Recall that in this case
3 does not divide m or 3 does not divide f ?1. If 3 does not divide f ?1 then the
gcd(f ? 1,f + 2,mp) = 1. Otherwise, 3 does not divide m and 3 divides f ? 1;
so 3 does not divide p since f ? ?1( mod p). Thus, 3 does not divide mp. So,
gcd(f ?1,f + 2,mp) = gcd(3,mp) = 1.
? 1(a)ii: Here we have that d = [f] ? 2. We must consider gcd([f] ? 2,[f] +
1,mp) which divides gcd(([f] + 1)? ([f]? 2)),mp) = gcd(3,mp) ? {1,3}. Since
[f] ? 2 ? ?1( mod p), 3 cannot divide both [f] ? 2 and p, so the only way for
gcd([f] ? 2,[f] + 1,mp) = 3 is if 3 divides both [f] ? 2 and m. But [f] ? 2 =
mp ? f ? 2 ? mp ? (f ? 1(mod3) so then 3 would divide f ? 1, contradicting
the assumption that either 3 does not divide m or 3 does not divide f ?1. Thus,
gcd([f]?2,[f] + 1,mp) = gcd(3h,mp) = 1.
4. Suppose ? = ?d,d + 9?. Such pairs only occur in case 1(b). So, we consider the cases
in turn.
? 1(b)i: In this case d = f ?3, so we need to consider gcd(f ?3,f + 6,mp) which
divides gcd((f + 6) ? (f ? 3),mp) = gcd(9,mp) ? {1,3,9}. Recall that in this
case 3 divides m, 3 divides f ? 1, and f ? ?1( mod p). So 3 does not divide
f ?3. Thus, gcd(f ?3,f + 6,mp) = gcd(9,mp) = 1.
? 1(b)ii: Here we have that d = [f]?4. So we must consider gcd([f]?4,[f]+5,mp)
which divides gcd(([f] + 5)?([f]?4),mp) = gcd(9,mp) ? {1,3,9}. Notice that
[f]?4 = mp?f ?4 = mp?(f ?1)?5. In this case, 3 divides m and 3 divides
(f ?1); so if 3 divides ([f]?4) then 3 divides ?5, a contradiction. Thus 3 does
not divide [f]?4, so the gcd([f]?4,[f] + 5,mp) = 1.
14
Case 2: If p ? 2(mod4) and m ? 3(mod4), then mp/2 ? 1 is even. Thus ?mp/2 ? 1?mp is
not a hamilton cycle. Consider a di?erence, g, de?ned in the same way as f. That is, by
Lemma 3.1 there exists a g ? Zmp with g ? ?1(modp),gcd(g,mp) = 1,g ?= mp ? 1, and
g ?= f. Then ?g?mp is a hamilton cycle. Remove this di?erence as well from D; so in this
case de?ne our new di?erence set D? = D\{1,2,f,2f,mp/2,g}. In the following situations
we will modify D? to form D?? as follows.
? (a):
{ i: If [f] = g + 2, then remove {3,g + 3} from D?.
{ ii: If [g] = f + 2, then remove the pair {3,f + 3} from D?.
? (b): If 2f = g ?1, then remove the pair {g ?2,g + 2} from D?.
Consider this new set D??. Di?erences in D?? are now paired in increasing order and The-
orem 1.1 applied to each pair. We now show that for each possible pair ? = {z1,z2},
gcd(z1,z2,mp) = 1.
1. Suppose ? = ?d,d + 1? for some d ? D??. Then gcd(d,d+1,mp) divides gcd((d+1)?
(d),mp) = gcd(1,mp) = 1.
2. Suppose ? = ?d,d + 2? for some d ? D??. Notice that such a pair only occurs when
d + 1 is a multiple of p, is 2f, is 2[f], or is [2[f]]. In each situation, d and d + 2 are
both odd. Thus, gcd(d,d+2,mp) divides gcd((d+2)?(d),mp) = gcd(2,mp) ? {1,2}.
So, since d is odd, gcd(d,d + 2,mp) = 1.
3. Suppose ? = ?3,d + 3?. Such pairs occur in case 2(a). So, we consider the situations
in turn.
? (Case 2i): In this case d = g, so we need to consider gcd(3,g + 3,mp) which
divides gcd((g + 3)?3,mp) = gcd(g,mp). By de?nition of g, gcd(g,mp) = 1.
15
? (Case 2ii): In this case d = f, so we need to consider gcd(3,f + 3,mp) which
divides gcd((f + 3)?3,mp) = gcd(f,mp). By de?nition of f, gcd(f,mp) = 1.
4. Suppose ? = ?g ? 2,g + 2?. This pair occurs in case 2(b). We need to consider
gcd(g?2,g +2,mp) which divides gcd((g +2)?(g?2),mp) = gcd(4,mp) ? {1,2,4}.
Notice that in this case g ? 2 is odd since g is odd, thus gcd(g ? 2,g + 2,mp) is odd.
So, gcd(g ?2,g + 2,mp) = 1.
Thus every pair of di?erences induces two hamilton cycles to be placed into S. In some cases,
the di?erence mp/2?1 or g is used alone to form a hamilton cycle. The sets?1,2?mp,?f,2f?mp
induce G and H and two hamilton cycles in S. If the half-di?erence, mp/2, is present in
D, it induces the 1-factor, I. So the required 2-factorization has been constructed in all
cases.
16
Chapter 4
Another Number Theoretic Result
In this section a result is obtained that was, early in the research, thought to be pivotal.
However, it was concluded that a simpler approach could be used. By adopting a di?erent
approach in the proof of Theorem 3.4, it turns out that Lemma 4.1 was not needed. Never-
theless it is a result that may be of some consequence in future endeavors. For example, it
could be a useful tool in attacking results that would generalize Theorem 3.4.
Lemma 4.1. Let m ? 5. If m,p ? Z+ and p even, then there exists an f ? Z such that
gcd(f,mp) = 1, f ? p?1(mod 2p), and 0 ? f < mp.
Proof. Let m, p ? Z+ and let p be even. Let Q = {qi | qi is prime, qi divides m, and qi
does not divide p}. Notice that the gcd(qi,2p) = 1 for each qi ? Q since p is even. By
the Chinese Remainder Theorem, there exists a unique solution modulo 2p?qi?Q qi to the
system of congruences:
1. f ? p?1(mod 2p)
2. f ? 1 or 2(mod qi) for each qi ? Q.
Notice that 0 ? f < 2p?qi?Q qi. (*) We ?rst check that gcd(f,mp) = 1. Let r ? Z be
a prime such that r divides f and r divides mp. We consider two cases in turn.
Case 1: r divides f and r divides p
By (1), f = 2px + p?1 for some x ? Z. Then, r divides 2px, r divides p, and r divides f,
so r divides ?1. This implies that r = 1, so gcd(f,mp) = 1.
Case 2: r divides f, r divides m, but r does not divide p
We can assume that r = qi for some qi ? Q. By (2), f = ry + 1 or f = rz + 2 for y,z ? Z.
17
If f = ry + 1, then r divides 1, so gcd(f,mp) = 1. If f = rz + 2, then r divides 2, which
implies that r divides 1 since qi ?= 2, so gcd(f,mp) = 1.
Now that we have an f such that gcd(f,mp) = 1 and f ? p ? 1(mod 2p), and clearly,
by (1) and (2), 0 < f < 2mp, it just remains to show that f can be chosen so that f < mp.
We consider two cases in turn.
Case 1: Suppose m is not square free; say q21 divides m. Then, by (*) f < 2p?qi?Q qi ?
2pm?q1 ? mp. So, f < mp as required.
Case 2: If m is square free, m ? 5, and gcd(m,p) = 1, then 2p?qi = 2mp. An obvious
problem since we need f < mp, not just f < 2mp.
We know that f = 2px+p?1 for some x ? Z, and gcd(f,p) = 1. We need gcd(f,m) = 1.
Since 0 ? f < 2mp, we have 0 ? x ? m?1. These m values for x form a complete residue
class modulo m. Then, since gcd(m,2p) = 1, the resulting m values of f are a complete
residue class modulo m. Notice, because m is odd, there are m + 1/2 possible values between
0 and mp, and m?1/2 values between mp and 2mp. Thus, we have slighly more candidates
for f?s in the desired range, [0,mp). We need to show that one of these values satis?es
gcd(f,mp) = 1.
De?ne two functions, g,h : Z ? Z+, where g(x) = gcd(x,m) and h(x) = gcd(2px +
p?1,m) = gcd(f,m).
We will now show that for some ?xed y ? Z, h(x + y) = g(x) for all x ? Zm.
Since gcd(2p,m) = 1, we can ?nd an integer t satisfying 2pt ? 1(mod m). Let y = t(1?p).
Then:
h(x+y) = gcd(2p(x+y)+p?1,m) = gcd(2px+2py +p?1,m) = gcd(2px+2pt(1?p)+
p?1,m) = gcd(2px + 1?p + p?1,m) = gcd(2px,m) = gcd(x,m) = g(x).
Since g(?1) = g(1) = g((m ? 1)/2) = g((m + 1)/2) ? 1, it follows that if we evaluate h at
each of the values, ?1 + y(mod m), 1 + y(mod m),
18
(m ? 1)/2 + y(mod m), and (m + 1)/2 + y(mod m), we get 1 in each case; and clearly at
least one of these four values, say xk, must be at most (m?1)/2. So, let f = 2pxk +p?1 ?
2p((m?1)/2) + p?1 < mp.
19
Chapter 5
Conclusion
This dissertation shows the existence of the cases where mp is odd and is settled in
Theorem 2.1. However, there are many smaller cases where p is even that need to be
considered, namely, when either p ? 5 or m ? 4. The method used when settling the
existence problem when mp is small and odd may be able to be adapted for these unsettled
cases. Because we are looking for two 2-factors, the degree of each vertex must be at least
4, thus m(p?1) ? 4. So to obtain a complete solution to this problem it su?ces to consider
the following cases:
1. m = 2 and p ? 3
2. m = 3, p ? 4, and p is even
3. m = 4 and p ? 2
4. p = 2 and m ? 5
5. p = 3, m ? 6, and m is even
6. p = 4 and m ? 5
7. p = 5, m ? 6, and m is even.
20
Bibliography
[1] Adams, P., Bryant, D.: Two-factorisations of complete graphs of orders ?fteen and
seventeen, Australas. J. Combin. 35, 113-118 (2006) .
[2] Alspach, B., Schellenberg, P., Stinson, D., Wagner, D.: The Oberwolfach problem and
factors of uniform odd length cycles, J. Combin. Theory, Ser A 52, 20-43 (1989).
[3] Bermond, J., Favaron, O., Maheo, M.: Hamilton decomposition of Cayley graphs of
degree 4, J. Combin. Theory, Ser. B 46, 142-153 (1989).
[4] Bryant,D.: Hamilton cycle rich 2-factorizations of complete graphs, J. Combin. Des. 12,
147-155 (2004).
[5] Bryant, D., Rodger, C. A.: Cycle decompositions, CRC Handbook of Combinatorial
Designs, (Colbourn, C. J., Dinitz, J. H., eds), 2nd edition, CRC Press, 2007.
[6] Buchanan, H. III: Ph.D. Dissertation, University of West Virginia, 1996.
[7] Franek, F., Rosa, A.: Two-factorizations of small complete graphs, J. Statist. Plann.
Inference 86, 435-442 (2000).
[8] Ho?man, D. G., Schellenberg, P.:The existence of a Ck-factorization of K2n?F, Discrete
Math. 97, 243-250 (1991).
[9] Plantholt, M.: The chromatic index of graphs with a spanning star, J. Graph Theory
5, 45-53 (1981).
[10] Rodger, C. A.: Hamilton decomposable graphs with speci?ed leaves, Graphs Combin.
20, 541-543 (2004).
21