Hamilton Decompositions of Graphs with Primitive Complements
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.
Sibel Ozkan
Certiflcate of Approval:
Charles C. Lindner
Distinguished University Professor
Mathematics and Statistics
Chris A. Rodger, Chair
Scharnagel Professor of Math Sciences
Mathematics and Statistics
Peter D. Johnson, Jr.
Professor
Mathematics and Statistics
George T. Flowers
Interim Dean
Graduate School
Hamilton Decompositions of Graphs with Primitive Complements
Sibel Ozkan
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 10, 2007
Hamilton Decompositions of Graphs with Primitive Complements
Sibel Ozkan
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
Sibel ?Ozkan, daughter of Salih and R?ukiye ?Ozkan, was born on October 4, 1978 in
Alanya, Turkey. She has one older brother ?Onder. She graduated from Anatolian Teacher
Training High School, Edirne, Turkey in 1996. She then attended Bo?gazi?ci University in
Istanbul as Vehbi Ko?c Foundation Scholar, and received her Bachelor of Science in Mathe-
matics in January, 2003. She enrolled in Graduate School at Auburn University, in August
2003.
iv
Dissertation Abstract
Hamilton Decompositions of Graphs with Primitive Complements
Sibel Ozkan
Doctor of Philosophy, May 10, 2007
(B.S., Bogazici University, 2003)
53 Typed Pages
Directed by Chris A. Rodger
A k-factor of a graph G is a k-regular spanning subgraph of G. A Hamilton cycle is
a connected 2-factor. A graph G is said to be primitive if it contains no proper factors.
A Hamilton decomposition of a graph G is a partition of the edges of G into sets, each
of which induces a Hamilton cycle. In this dissertation, by using a graph homomorphism
technique called amalgamation, we flnd necessary and su?cient conditions for the existence
of a 2x-regular graph G on n vertices which:
1. has a Hamilton decomposition, and
2. has a complement in Kn that is primitive.
This extends the conditions studied by Hofiman, Rodger and Rosa [7] who considered
maximalsetsofHamiltoncyclesand2-factors. Italsoshedslightonconstructionapproaches
to the Hamilton-Waterloo problem.
We also give su?cient conditions, by using amalgamation technique, for the existence
of 2x-regular graph G on mp vertices which:
1. has a Hamilton decomposition, and
v
2. has a complement in Kpm that is primitive.
vi
Acknowledgments
First, I would like to thank Dr. Chris A. Rodger for being a great mentor to follow. I
would also like to thank my committee members Dr. Curt Lindner and Dr. Peter Johnson
and the rest of the faculty for making my Auburn years worthwhile and memorable. Your
ideas, advice, and support were the main ingredients of my Ph.D. study. Next, I would like
to thank my friends for making me feel home in Auburn.
I wish to thank Dr. Haluk Oral for his encouragement and support to start a graduate
study. Finally, I would like to thank my family -R?ukiye, Salih, and ?Onder ?Ozkan- for their
love and support, not only during my overseas education but also throughout my life.
vii
Style manual or journal used Journal of Approximation Theory (together with the style
known as \auphd"). 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 auphd.sty.
viii
Table of Contents
List of Figures x
1 Introduction 1
1.1 Deflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Primitive graphs 6
3 Amalgamations and preliminary results 9
4 Hamilton decompositions of graphs with primitive complements 14
5 Hamilton decompositions with primitive complements in Kpm 21
6 Conclusion 40
Bibliography 42
ix
List of Figures
1.1 K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 K24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 A 2-factor in a given graph G . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 A Hamilton decomposition of K7 . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1 The only graph in G(16;3) . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 One graph in G(42;5): Cd does not need to be connected . . . . . . . . . . 8
3.1 An amalgamation of K5 in which vertices have been partitioned into three
parts: circle, square, and triangle . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 An amalgamation of all graphs in G(42;5) in which vertices of the same
component are amalgamated together . . . . . . . . . . . . . . . . . . . . . 11
4.1 A = K(n;d) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 A(fi) after we removed the edges of the primitive graph . . . . . . . . . . . 16
4.3 First step in recoloring: recolor 2 edges between ai and ad with k, for 1 ?
k ? ?, and 1 ? i ? d?1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.1 A graph with degree sequence (5;5;1;1;1;1) . . . . . . . . . . . . . . . . . . 28
x
Chapter 1
Introduction
1.1 Deflnitions
Let?s start with giving some deflnitions. A complete graph on n vertices, denoted by
Kn, is a simple graph in which there is an edge between every pair of its vertices. A complete
multipartite graph Kpm is the graph with p parts, each of size m, in which there is an edge
between any pair of its vertices if and only if they are in difierent parts.
Figure 1.1: K5 Figure 1.2: K24
A k-factor of a graph G is a spanning k-regular subgraph of G. In other words, it is
a subgraph of G which uses all the vertices of G, and the degree of each of its vertices is
k. G is said to be primitive if it contains no k-factors with 1 ? k < ? (? is the maximum
degree of G). A Hamilton cycle in a graph G is a spanning cycle in G. So, we can consider
Hamilton cycles as connected 2-factors.
A graph which has a Hamilton cycle is called Hamiltonian, and a Hamilton decom-
position of a graph G is a partition of the edges of G into sets, each of which induces a
Hamilton cycle. A set S of Hamilton cycles in G is said to be maximal if G?E(S) contains
1
Figure 1.3: A 2-factor in a given graph G
no Hamilton cycles. Similarly, a set S of edge-disjoint k-factors in G is said to be maximal
if G?E(S) contains no k-factors. In either case, the spectrum is the set that contains the
integer s if and only if such a maximal set of size s exists.
Figure 1.4: A Hamilton decomposition of K7
In this dissertation, graphs may have multiple edges and loops, with each loop con-
tributing 2 to the degree of the incident vertex. The number of edges between w and v in G
is denoted by mG(w;v) or simply by m(w;v). If G has an edge-coloring, then let G(i) be the
subgraph of G induced by the edges colored i, and let !(G) be the number of components
in G. An edge-coloring of G is said to be equitable if for each pair of colors i and j and for
each v 2 V(G), jdG(i)(v)?dG(j)(v)j 2 f0;1g, and called evenly-equitable if for each pair of
colors i and j and for each v 2 V(G), dG(i)(v) is even and jdG(i)(v)?dG(j)(v)j2f0;2g.
2
1.2 History
The popularity of Hamilton cycles rises from optimization problems like the Traveling
Salesman Problem: Given a number of cities and the costs of traveling from any city to any
other city, what is the cheapest round-trip route that visits each city exactly once and then
returns to the starting city? Solution to this problem is equivalent to flnding a Hamilton
cycle with the least weight in a weighted complete graph. Although flnding a Hamilton
cycle in a graph is an NP-complete problem, the literature contains classic results which
give necessary and su?cient conditions for a graph to be Hamiltonian; some also exist for
the decomposition of certain graphs into Hamilton cycles.
In 1847, Kirkman [10] solved the existence and the spectrum problem for 3-cycle sys-
tems of Kn. Since then, cycle decomposition has been an interesting problem and many
results have appeared on this subject. Hamilton decompositions, where each cycle in the
system needs to be a spanning cycle, also dates back to at least 19th century. In 1894,
Walecki [12] determined the spectrum for Hamilton decompositions of Kn, and in 1976,
Laskar and Auerbach [11] determined this spectrum for complete multipartite graphs.
In 1982, A.J.W. Hilton [5] wrote a gem of a paper, giving necessary and su?cient
conditions for an edge-colored copy of Kn to be embedded in an edge-colored copy of Kv
in such a way that each color class induces a Hamilton cycle. In so doing, he demonstrated
the power of using graph homomorphisms to construct graph decompositions, calling them
amalgamations. The  exibility of his technique has been demonstrated over the next 25
years in a variety of settings, and this dissertation uses it too!
In 1993, Hofiman, Rodger, and Rosa [7] determined the spectrum for maximal sets
of Hamilton cycles of Kn by using amalgamations. They also determined the complete
3
spectrum for maximal sets of 2-factors of Kn by using Tutte?s f-factor Theorem, proving
the following result.
Theorem 1.1 ([7]) There exists a maximal set S of x edge-disjoint 2-factors in Kn if and
only if
1. x = n?12 if n is odd, and
2. n?
pn
2 ? x ?
n?2
2 if n is even.
This result stands at the other end to an avenue of research in the literature, setting
limits on results that seek to extend sets of edge-disjoint 2-factors of one kind to a (complete)
2-factorization of Kn in which the added 2-factors have another property. For example,
Buchanan [4], in his dissertation written under the supervision of A.J.W. Hilton, used
amalgamations to show that Kn ?E(U) has a Hamilton decomposition for any odd n and
for any 2-factor U of Kn in 1997. This result and extensions of it have now also been proved
using difierence methods [3, 17].
Another such example of research in the literature is the Hamilton-Waterloo problem:
For which values of s;t, and z does there exist a 2-factorization of Kn (or of Kn ?F, the
spouse avoiding version of the problem where n is even and F is a 1-factor) in which z of
the 2-factors consist entirely of s-cycles, and the rest consist of t-cycles? Horak, Nedela,
and Rosa [8] recently addressed this problem, making progress in the case when s = n (so
these 2-factors are Hamilton cycles) and t = 3. Results also address the situation where
both s and t are small (see [1] for example).
Here we continue the tradition begun by A.J.W. Hilton by flnding necessary and su?-
cient conditions on (x;n) to be able to partition E(Kn) into 2 sets, one of which induces a
4
2x-regular graph that has a Hamilton decomposition, the other of which induces a primitive
graph. Not only is this an interesting graph decomposition, but it also has the appeal of
setting limits on results like those addressed by Horak, Nedela, and Rosa and by Buchanan
described above. The results proved here show that when n is even, one could select x
edge-disjoint Hamilton cycles for any x ? n?
pn
2 and be left with no 2-factors of any type
in the complement.
In Chapter 5, we extend the results for the graphs that have primitive complements in
complete multipartite graphs Kpm.
5
Chapter 2
Primitive graphs
If d is even, then Petersen?s Theorem [16] precludes any non-trivial primitive d-regular
graphs. It is known that there exist primitive regular graphs for every odd degree d [7].
In fact, there exists a primitive regular graph of order n and odd degree d if and only if
n ? (d+1)2 and n is even. We now deflne a family of such graphs. For each d ? 3 (d odd)
and each n ? (d+1)2, deflne a set of d-regular graphs on n vertices G(n;d) as follows:
G 2 G(n;d) if and only if
(a) Gcontainsacut-vertexv suchthatG?v hasapartitionintodsubgraphsC1;C2;:::;Cd,
where C1;C2;:::;Cd?1 are components of G?v, and Cd is the union of the remaining
components of G?v,
(b) Each of C1;C2;:::;Cd?1 contains exactly d+2 vertices, exactly one of which is adja-
cent to v,
(c) Cd has n?(d?1)(d+2)?1 vertices, exactly one of which is adjacent to v, and
(d) G is d-regular.
Note that (c) is implied by the other conditions.
In this dissertation it is easily shown that any G 2 G(n;d) is primitive, and then the
amalgamation technique is used to show that Kn?E(G) has a Hamilton decomposition for
some G 2 G(n;d). This shows that the spectrum of edge-disjoint Hamilton cycles that have
6
primitive complements is equal to the spectrum of maximal sets of 2-factors. Computing
this flrst spectrum is the main result of Chapter 4.
Lemma 2.1 For each odd d ? 3 and even n ? (d+1)2, any G 2 G(n;d) is primitive.
Proof Note that, by construction, each of C1;:::;Cd in G?v has an odd number of vertices.
Suppose there exists a proper d0-factor F. Since d0 < d, there would be two of C1;:::;Cd,
say Ci and Cj, such that F contains the edge joining Ci to v but does not contain the edge
joining Cj to v. But then in the components induced by V(Ci) and V(Cj) in F ?v, the
number of vertices of odd degree difiers by 1. So, one of the components has an odd number
of vertices of odd degree, which is a contradiction.
Figure 2.1: The only graph in G(16;3)
7
Figure 2.2: One graph in G(42;5): Cd does not need to be connected
8
Chapter 3
Amalgamations and preliminary results
Informally, an amalgamation of a graph H is a new graph A, formed by partitioning
the vertices of H and representing each element p of the partition P with a single vertex
in A, where edges incident with this single vertex are in one-to-one correspondence with
the edges incident with original vertices of H in P; so edges in H joining two vertices in p
correspond to loops in A. In other words, for each edge fu;vg in H, if u 2 p1 and v 2 p2,
then we add an edge fp1;p2g in A (edges between two vertices in the same element of the
partition correspond to loops in A).
Formally, an amalgamation A of a graph H is formed by a graph homomorphism
f : V(H) ! V(A), where each vertex v of A represents ?(v) = jf?1(v)j vertices of H.
?(v) is called the amalgamation number of v, and f is called the amalgamation function of
H. Notice that any edge coloring of H naturally induces an edge-coloring of A under the
homomorphism f. In an edge coloring of A, A(k) represents the subgraph of A induced by
the edges colored k.
So, how do we use amalgamations? Given a graph A with amalgamation numbers,
one could try to flnd graphs which have A as an amalgamation. Conceptually, this could
be achieved by taking each vertex v with ?(v) > 1 and \peeling out" vertices one by one,
at each stage producing a graph H for which A is an amalgamation. H is said to be a
disentanglement of A. So, every disentanglement H of A has an associated amalgamation
function f of H. Furthermore, if A is edge-colored, then this disentanglement naturally
induces an edge-coloring of H.
9
Figure 3.1: An amalgamation of K5 in which vertices have been partitioned into three parts:
circle, square, and triangle
A disentanglement H of A is said to be regular if each color class of H is regular, and
a disentanglement H of A is said to be flnal if ?(h) = 1 for all h 2 V(H).
In Chapter 4, we want to color the edges of an amalgamation of Kn so that when we
disentangle the amalgamation, color class 0 will induce a primitive graph and each other
color class will induce a Hamilton cycle. In Chapter 5, we use the same technique for
complete multipartite graphs. The crucial tool for the proofs is Theorem 3.3, which says
that we can disentangle the amalgamation of Kn and that the colored edges incident to a
vertex in the amalgamation will split up evenly among the corresponding vertices in the
disentanglement. What we need to do is to show that the conditions of Theorem 3.3 hold.
Now, let n and d be flxed. For every graph G 2 G(n;d), let K(G) be a 2-edge colored
copy of Kn with colors 0 and fi in which the edges colored 0 induce a copy of G (in a later
proof, the edges colored fi will be partitioned into several color classes).
Notice that given n and d, any two graphs in G(n;d)
(a) have the same number of edges in Ci, for 1 ? i ? d, and
10
 
17 loops 17 loops 32 loops
?(a5) = 13
a5a4a3a1
v
a2
?(a1) = 7 ?(a2) = 7 ?(a3) = 7 ?(a4) = 7
Figure 3.2: An amalgamation of all graphs in G(42;5) in which vertices of the same com-
ponent are amalgamated together
(b) have the same number of edges joining the cut-vertex v to the vertices in Ci, for
1 ? i ? d.
LetK0(G)betheamalgamationformedfromK(G)usingthepartitionffvg;V(C1);:::;
V(Cd)g. Properties (a) and (b) imply that for any two graphs G1;G2 2 G(n;d), the amalga-
mationsK0(G1)andK0(G2)areisomorphic. Thus, weletK(n;d)betheuniqueedge-colored
amalgamated graph formed like this. Note that V(K(n;d)) = fai j 0 ? i ? dg, and that
?(ai) =
8>
>>>>
<
>>>>
>:
1 if i = 0,
d+2 if 1 ? i ? d?1, and
n?(d?1)(d+2)?1 if i = d.
(?)
Then K(n;d) has the following properties:
11
(a0) There are no edges colored 0 joining ai and aj, for 1 ? i < j ? d,
(b0) There is exactly one edge colored 0 joining ai and a0, for 1 ? i ? d,
(c0) dA(0)(ai) = ?(ai)d, for 0 ? i ? d, and
(d0) dA(fi)(ai) = (n?1?d)?(ai), for 0 ? i ? d.
Lemma 3.1 Every regular flnal disentanglement H of K(n;d) has the property that H(0) 2
G(n;d).
Proof Let H be a regular flnal disentanglement of K(n;d). We check to see that H satisfles
properties (a)?(d) in the deflnition of G(n;d). By (a0), there are no edges colored 0 joining
ai and aj, for 1 ? i < j ? d, so there is a cut-vertex in H(0) and this satisfles (a). By (?) and
(b0), each of C1;:::;Cd?1 contains exactly d+2 vertices and Cd contains n?(d?1)(d+2)?1
vertices; in each case exactly one vertex of which is adjacent to cut-vertex v. This proves
(b) and (c).
By (c0), dA(0)(ai) = ?(ai)d. Since H is regular and it is a flnal disentanglement, ?(h) = 1
for each h 2 H. This says that H(0) is d-regular, proving (d). Hence, H(0) 2 G(n;d).
We will use the following two results. We will color the edges with colors 0;1;:::;?
and s = ?+1 in Chapter 4 and with colors 0;1;:::;?;fi and s = ?+2 in Chapter 5. So, we
state the results here for s-edge-colorings.
Lemma 3.2 ([13]) Let H ?= Kn be an s-edge-colored graph where each color class i is
di-regular, and let f : V(H) ! V(G) be an amalgamation function with amalgamation
numbers given by the function ? : V(G) !N. The following conditions hold for any pair of
vertices w;v 2 V(G) :
12
(1) d(w) = ?(w)(n?1),
(2) the number of edges between w and v is m(w;v) = ?(w)?(v) if w 6= v,
(3) w has ?(w)(?(w)?1)=2 loops, and
(4) dG(i)(w) = ?(wi)di for each color i 2f0;1;:::;?g.
Theorem 3.3 ([13]) Let A be an s-edge-colored graph satisfying conditions (1) ? (4) of
Lemma 3.2 for the function ? : V(A) ! N. Then there exists a disentanglement H of A
with amalgamation function f(H) such that H ?= Kn and the following two conditions hold:
(i) For any z 2 V(A), degree dH(i)(u) 2f
jd
A(i)(z)
?(z)
k
;
ld
A(i)(z)
?(z)
m
g for all i 2 0;:::;? and all
u 2 f?1(z), and
(ii) If dA(i)(z)?(z) is an even integer for all z 2 V(A), then !(A(i)) = !(H(i)).
This result will be used in the following way in Chapter 4: We will color the edges of
K(n;d) with 2 colors; 0 and fi. Then, we will recolor the edges colored fi with (n?d?1)=2
colors in such a way that each color class produces a Hamilton cycle in Kn when Theorem
3.3 is applied to the recolored graph. To do this, we will need Lemma 3.4. It will also
be clear that the edges colored 0 in Kn induce a copy of G for some G 2 G(n;d). An
edge-coloring of G is said to be evenly-equitable if for each pair of colors i and j and for
each v 2 V(G), dG(i)(v) is even and jdG(i)(v)?dG(j)(v)j2f0;2g.
Lemma 3.4 ([6]) For each m ? 1, each flnite eulerian graph has an evenly-equitable edge-
coloring with m colors.
13
Chapter 4
Hamilton decompositions of graphs with primitive complements
In this chapter, we will give a proof to the following theorem.
Theorem 4.1 There exists a set S of x edge-disjoint Hamilton cycles in Kn such that
Kn ?E(S) is primitive if and only if
1. x = n?12 if n is odd, and
2. n?
pn
2 ? x ?
n?2
2 if n is even.
We begin by proving the following theorem, which implies the su?ciency for even n.
Theorem 4.2 For each odd d ? 3 and each even n ? (d + 1)2, there exists a G 2 G(n;d)
such that Kn ?E(G) has Hamilton decomposition.
Proof We begin with the 2-edge-colored graph K(n;d) on d + 1 vertices, which is an
amalgamation of Kn and has the amalgamation numbers given in (?).
Let A = K(n;d) for convenience. By multiplying the amalgamation numbers in (?) by
(n?1), we get:
dA(a0) = n?1;
dA(ai) = (d+2)(n?1) for 1 ? i ? d?1, and
dA(ad) = (n?1)(n?(d?1)(d+2)?1);
where a0 2 V(A) corresponds to the cut-vertex v in G 2 G(n;d), and ai 2 V(A) corresponds
to the vertices in Ci for 1 ? i ? d.
14
 
ad
a0 = v
a2a1 a3
Figure 4.1: A = K(n;d)
Next, we recolor the edges of A(fi) with colors 1;:::;? = (n?d?1)=2 so that, for each
color k 2f1;2;:::;?g and each vertex z 2 V(A):
(a) A(k) is connected, and
(b) dA(k)(z) = 2?(z) (we already know dA(0)(z) = d?(z)).
Then, we can apply Theorem 3.3 to obtain the graph H ?= Kn satisfying
(i) for all u 2 f?1(z), dH(k)(u) = dA(k)(z)?(z) =
8>
<
>:
2 for 1 ? k ? ?;
d for k = 0;
15
 
ad
a0 = v
a2a1 a3
Figure 4.2: A(fi) after we removed the edges of the primitive graph
(ii) for 1 ? k ? ?, H(k) is connected (since dA(k)(z)?(z) = 2 is even for all z 2 V(A)).
Notice that (i) and (ii) imply that, for each color k 2f1;2;:::;?g, the color class H(k)
induces a Hamilton cycle. By Lemma 3.1, the edges colored 0 in H induce a primitive
graph. We only need to specify the (?+1)-edge-coloring of A.
We now start recoloring the edges of A(fi). In the flrst step, we will guarantee the
connectivity of each color class. In the second step, we will boost the degree of each vertex
ai in each color class to 2?(ai).
16
 
a1
a0 = v
a2 a3 ad
Figure 4.3: First step in recoloring: recolor 2 edges between ai and ad with k, for 1 ? k ? ?,
and 1 ? i ? d?1
First, for 1 ? i ? d ? 1 and for 1 ? k ? ?, recolor two edges joining vertices ai and
ad with color k. To do this, we should check if there are at least 2? = n ? d ? 1 edges
colored fi between ai and ad to ensure this flrst step is possible. Suppose 1 ? i ? d ? 1.
All the edges between ai and ad are in A(fi). Since A is an amalgamation of Kn, there
are ?(ai)?(ad) = (d + 2)(n?d2 ?d + 1) edges between ai and ad. So, we now show that
(d+2)(n?d2 ?d+1) ? n?d?1.
17
Recall that by the hypothesis, n ? (d+1)2 and d ? 3. So,
n(d+1) ? (d+1)3 = d3 +3d2 +3d+1
> d3 +3d2 ?3; since d ? 3.
Therefore,
(d+2)(n?d2 ?d+1) = nd?d3 ?d2 +d+2n?2d2 ?2d+2
= nd+n+n?d3 ?3d2 ?d+2
= (n?d?1)+nd+n?d3 ?3d2 +3
= (n?d?1)+n(d+1)?(d3 +3d2 ?3)
> n?d?1:
Hence, we have enough edges in A(fi) to recolor two edges between ai and ad with color k,
for each color k 2f1;2;:::;?g and each i 2f1;2;:::;d?1g.
Now, in our second step, we recolor the remaining edges colored fi with the same ?
colors. Let ?A(fi) be a graph induced by the remaining edges. Then, ?A(fi) is connected since
foreachi 2f1;2;:::;d?1g, vertexai isjoinedtoad with(d+2)(n?d2?d+1)?(n?d?1) > 0
edges and the degree d?A(fi)(ai) is even:
d?A(fi)(ai) =
8>
>>>>
<
>>>>
>:
2? for i = 0,
?(ai)2??2? for 1 ? i ? d?1, (??)
?(ai)2??2?(d?1) for i = d.
So, ?A(fi) is eulerian and, by Lemma 3.4 we can give ?A(fi) an evenly equitable edge-coloring
with ? colors. So, for each ai 2 V( ?A(fi)), and each 1 ? k ? ?, dA(k)(ai) is either 2
jd
?A(fi)(ai)
2?
k
18
or 2
ld
?A(fi)(ai)
2?
m
. Since 2? is a factor of d?A(fi)(ai) for each vertex ai 2 V( ?A(fi)), we have
dA(k)(ai) = 2
jd
?A(fi)(ai)
2?
k
= 2
ld
?A(fi)(ai)
2?
m
= d ?A(fi)(ai)? :
Substituting from (??), we get
dA(k)(ai) =
8
>>>>
><
>>>>
>:
2 for i = 0,
2(?(ai)?1) for 1 ? i ? d?1,
2(?(ai)?d+1) for i = d.
For 1 ? i ? d ? 1, and for 1 ? k ? ?, ai is incident with two edges colored k that were
recolored in step 1 and is incident with 2?(ai)?2 edges colored k that were recolored in step
2; ai is incident with 2?(ai) edges colored k, as required by (b). Similarly, dA(k)(ai) = 2?(ai)
for i 2f0;dg.
Hence, we have the desired (? + 1)-coloring of K(n;d). So, Theorem 3.3 provides an
(?+1)-edge-coloring of Kn where color 0 induces a primitive graph G and each of colors 1
to ? induces a Hamilton cycle in Kn ?E(G).
Now, we prove the converse.
Theorem 4.3 If there exists a set S of x edge-disjoint Hamilton cycles such that Kn?E(S)
is primitive, then x ? (n?pn)=2 when n is even, and x = (n?1)=2 when n is odd.
Proof If Kn ?E(S) is primitive, then it must be regular; say it is d-regular. We consider
the cases when n is odd and when n is even.
If n is odd and x < (n?1)=2, then since Kn?E(S) is regular of even degree, Petersen?s
Theorem [16] guarantees that it contains a 2-factor. Hence Kn ?E(S) is not primitive.
19
If n is even, then Hofiman et al. [7] showed that Kn ? E(S) can be primitive with
degree d if and only if d is odd and n ? (d + 1)2. So, pn ? 1 ? d. Since S contains
x = (n?1?d)=2 edge-disjoint Hamilton cycles, substituting for d gives us:
x ? n?1?
pn+1
2 =
n?pn
2 :
Hence, we are done.
Theorem 4.2 and Theorem 4.3 together prove Theorem 4.1.
We conclude this chapter with the following avenue for future research! Let G0(n;d) be
the more general family of graphs deflned by all the properties of graphs in G(n;d) except
that properties (b) and (c) are relaxed to allow C1;:::;Cd to contain any odd number of
vertices. It is easy to see that graphs in G0(n;d) are primitive.
Conjecture: There exists a Hamilton decomposition of Kn?E(G) for all G 2 G0(n;d).
20
Chapter 5
Hamilton decompositions with primitive complements in Kpm
In this chapter, we give su?cient conditions to flnd a set of edge-disjoint Hamilton
cycles in Kpm where the complement is primitive. Let?s start with giving the preliminary
results we will use in the proof of the main theorem.
We will use the following results to partition the vertices of the primitive graph into p
parts, each of size m, then use it as the vertex set for Kpm. A vertex coloring c of a graph
G is said to be equitable if jci ?cjj? 1 for all colors 1 ? i;j ? p, where ci is the number of
vertices in G colored i.
Theorem 5.1 ([18]) If G is a graph satisfying ?(G) ? r, then G has an equitable (r+1)-
coloring.
Lemma 5.2 Let d ? 3 be odd and n = mp ? (d + 1)2 be even, for some odd m. For
p ? d + 1, we can give any G 2 G(n;d) an equitable p-vertex coloring which induces an
equitable vertex coloring in Cd and satisfying jX1j = jX2j = ::: = jXpj = m , where Xk is
the set of vertices in G colored k, for 1 ? k ? p.
Proof By Theorem 5.1, we know that if G is a graph satisfying ?(G) ? r, then G has an
equitable (r +1)-coloring.
Let G 2 G(n;d). Since Cd is d-regular, ?(Cd) = d. Then, for p ? d + 1, we can give
Cd an equitable p-coloring. Since G ? Cd is also d-regular, similarly we can give G ? Cd
an equitable p-coloring. Since in G these two subgraphs are joined buy a cut-edge, the
colors can be named so that the union of these two colorings gives us an equitable p-vertex
21
coloring of G with all color classes of size bnpc or dnpe. But p divides n = mp and the size of
all color classes is bnpc = dnpe = m. Hence, we are done.
The next Lemma will help us in the proof of the main result.
Lemma 5.3 For any graph G, if d?(G)??(G)k e = 1, then in any equitable edge-coloring of
G with k-colors, jci(u)?ci(v)j? 2 for any u;v 2 G, and any color i, 1 ? i ? k.
Proof Let c : E(G) 7?! f1;2;:::;kg be an equitable k-edge-coloring of G. Then, for any
a 2 V(G), and any i 2f1;2;:::;kg
jci(a)j = ddG(a)k e or bdG(a)k c
Then, for any u;v 2 V(G) and any i 2f1;2;:::;kg,
jci(u)?ci(v)j ? ddG(u)k e?bdG(v)k c
? d?(G)k e?b?(G)k c
= d?(G)k e?d?(G)k e+d?(G)k e?b?(G)k c
? d?(G)??(G)k e+1
= 2
We will use Tutte?s f-factor Theorem in the proof of Theorem 5.5. Before stating
Tutte?s f-factor Theorem, let?s give necessary deflnitions. To assist the reader, throughout
the section we adopt Tutte?s notation [20].
The valency of a vertex x in a graph G is the degree of x in G and is denoted by
val(G;x). If f is a function from the vertex set V(G) of G into the set of integers, deflne
22
another function f0 by the rule f0(x) = val(G;x)?f(x) for each vertex x of G. Given such
a function f, an f-factor is a spanning subgraph F of G satisfying val(F;x) = f(x) for each
vertex x of G.
A G-triple is an ordered triple (S;T;U) where fS;T;Ug partitions V(G). For any
subset S of V(G), f(S) = Pv2S f(v). For any disjoint subsets S and T of V(G), ?(S;T)
denotes the number of edges of G joining S to T (in other sections this would be represented
by m(S;T)).
If B = (S;T;U) is a G-triple and C is any component of U in G, then deflne
J(B;f;C) = f(C)+?(V(C);T):
We say that C is an ODD component if J(B;f;C) is an odd integer. Note that we use
capital letters to distinguish it from \odd component" where the number of vertices in the
component is odd. The number of ODD components of U in G with respect to B and f
is denoted by h(B;f). Now, we deflne the deflciency ?(B;f) of the G-triple B = (S;T;U)
with respect to f, as follows:
?(B;f) = h(B;f)?f(S)?f0(T)+?(S;T):
An f-barrier of G is a G-triple B = (S;T;U) such that ?(B;f) > 0. We can now state
Tutte?s f-factor Theorem.
Theorem 5.4 ([20]) Given G and f, exactly one of the following statements is true:
(1) G has an f-factor.
23
(2) G has an f-barrier.
In other words, if we let f be a vertex-function of a graph G, then G has an f-factor or
there exists a G-triple B = (S;T;U) of G with ?(B;f) > 0, but not both.
Now, we can state our theorem which is a generalization of the Erd}os-Gallai Theorem.
A multigraph is a graph in which multiple edges between two vertices are allowed, and a
degree sequence is called ?-multigraphic if there is a multigraph of index ? with this degree
sequence.
Theorem 5.5 A sequence ? = (d1;d2;:::;dp) of non-negative integers with d1 ? d2 ?
::: ? dp and an even sum is multigraphic with multiplicity at most ? if and only if
kX
i=1
di ? ?k(k?1)+
pX
i=k+1
minfdi;?kg , for every k, 1 ? k ? p:
Proof Let?s flrst assume that the sequence ? = (d1;d2;:::;dp) of non-negative integers
with d1 ? d2 ? ::: ? dp and an even sum is multigraphic with multiplicity at most ? and
let G be a graph realizing this degree sequence. Then for any set S of k vertices in G, the
total degree of the vertices in S is equal to the twice the number of edges in S plus the
number of edges between the sets S and G?S. The maximum number of edges in S is ??k2?
and the maximum number of edges between S and G?S is Ppi=k+1 minfdi;?kg. Hence,
Pk
i=1 di ? ?k(k?1)+
Pp
i=k+1 minfdi;?kg follows for every k, 1 ? k ? p:
Now, assume the inequality Pki=1 di ? ?k(k?1)+Ppi=k+1 minfdi;?kg holds for every
k, 1 ? k ? p: We want to show that H = ?Kp has an f-factor with f(vi) = di for all vi 2 H.
We will use Tutte?s f-factor Theorem and show that ?(B;f) ? 0 for all B = (S;T;U), where
fS;T;Ug is a partition of V(H).
24
The value of ?(B;f) = h(B;f)?f(S)?f0(T)+?(S;T) is greater when f(S) and f0(T)
are smaller. We can make f(S) small by putting the vertices with the smallest f value in S
and we can make f0(T) small by putting the vertices with greatest f value in T. Since our
integer sequence is in a decreasing order, there exist two numbers t = jTj and s = jSj such
that ? takes its maximum value when T = fv1;:::;vtg and S = fvp?s+1;:::;vpg. Then,
letting h = h(B;f) and ? = ?(B;f) we get
? = h?Ppi=p?s+1 di ??t(p?1)+Pti=1 di +?ts
? h?Ppi=p?s+1 di ??t(p?1)+?t(t?1)+Ppi=t+1 minfdi;?tg+?ts (1)
= h?Ppi=p?s+1 di ??t(p?t?s)+Pp?si=t+1 minfdi;?tg+Ppi=p?s+1 minfdi;?tg
= h??t(p?t?s)+Pp?si=t+1 minfdi;?tg+Ppi=p?s+1(minfdi;?tg?di)
? h (since ??t(p?t?s)+Pp?si=t+1 minfdi;?tg? 0 (2)
and Ppi=p?s+1(minfdi;?tg?di) ? 0)
? 1 (since H[U], being a subgraph of ?Kp, is connected, so h 2f0;1g) (3)
with ? = 1 if and only if
(4) Pti=1 di = ?t(t?1)+Ppi=t+1 minfdi;?tg (from (1)), and
(5) Pp?si=t+1 minfdi;?tg??t(p?t?s) = 0 (from (2)), and
(6) Ppi=p?s+1(minfdi;?kg?di) = 0 (from (2)), and
(7) h = 1 (from (3)).
So the result is proved unless (4)-(7) all hold. Now, we will show that if (4)-(6) are
true, then h = 0.
25
Condition (4) implies ?t(p?t?s) = Pp?si=t+1 minfdi;?tg. Note that this also implies
that di ? ?t for i 2 ft + 1;:::;p ? sg. Condition (5) implies Ppi=p?s+1 minfdi;?tg =
Pp
i=p?s+1 di.
We know Ppi=1 di = f(T)+f(U)+f(S) is even. We have
Pp
i=1 di = f(T)+f(U)+f(S)
= Pti=1 di +f(U)+f(S)
= ?t(t?1)+Ppi=t+1 minfdi;?tg+f(U)+f(S)
= ?t(t?1)+Pp?si=t+1 minfdi;?tg+Ppi=p?s+1 minfdi;?tg+f(U)+f(S)
= ?t(t?1)+?t(p?t?s)+Ppi=p?s+1 minfdi;?tg+f(U)+f(S)
= ?t(t?1)+?t(p?t?s)+Ppi=p?s+1 di +f(U)+f(S)
= ?t(t?1)+?t(p?t?s)+2f(S)+f(U):
Since all of ?t(t ? 1), 2f(S), and the left hand side are even, ?t(p ? t ? s) + f(U) =
?(U;T) + f(U) is even, so U is EVEN. Therefore h = 0. Hence, we have ? ? 0 for every
case and H = ?Kp has an f-factor where f(vi) = di for all vi 2 H.
We will use the Theorem 5.5 in the proof of the following lemma.
Lemma 5.6 Let p be even. Suppose ? = (d1;d2;:::;dp) is a sequence of integers with
6 ? d1 ? d2 ? ::: ? dp ? 1, satisfying
(i) d1 ?dp ? 4,
(ii) Ppi=1 di is even, and
(iii) d1 ?Ppi=2 di.
26
Then ? is ?-multigraphic, where ? can be chosen to satisfy
? =
8>
>>>>
<
>>>>
>:
2 if p ? 6
3 if p = 6 and ? : (5;5;1;1;1;1)
4 if p = 4
Proof Case 1: First, let p = 4 and ? = 4. It is enough to show that we have
kX
i=1
di ? 4k(k?1)+
4X
i=k+1
minfdi;4kg , for every k, 1 ? k ? 4
by Theorem 5.5. We will denote the left hand side of the inequality by LHS and right hand
side of the inequality by RHS for simplicity. We will proceed case by case for each k:
k = 4: LHS ? 24 since each vertex may have degree at most 6. RHS ? 4:4:3 = 48 > 24.
k = 3: Similarly, LHS ? 18 and RHS ? 4:3:2+minfd4;12g > 24 > 18.
k = 2: LHS ? 12. Clearly RHS ? 4:2 + (1 + 1) = 10, so we only need to consider the
case where LHS ? 11 but this means at least one of the vertices has degree 6. Since the
difierence between the degrees can not be more than 4, all other vertices must have degrees
at least 2, implying that RHS ? 4:2+(2+2) = 12.
k = 1: Since each vertex has degree at most 6, LHS ? 6. We will analyze this case in
two subcases.
If di ? 4 for i 2 f2;3;4g, then P4i=2 minfdi;4kg = P4i=2 di ? d1 by condition (iii).
Hence LHS ? RHS.
If there is at least one di > 4 for i 2 f2;3;4g, then since other 2 vertices have degree
at least 1, RHS ? 7 ? LHS.
In all cases when p = 4, we have shown that the above inequality holds.
27
Case 2: Now, let ? = 3, p = 6, and the degree sequence be (5,5,1,1,1,1).
The below flgure gives a realization of this degree sequence with ? = 3.
Figure 5.1: A graph with degree sequence (5;5;1;1;1;1)
Case 3: Now, let ? = 2, p ? 6, and ? 6= (5;5;1;1;1;1).
It is enough to show that we have
kX
i=1
di ? 2k(k?1)+
4X
i=k+1
minfdi;2kg , for every k, 1 ? k ? p
by Theorem 5.5. We will again proceed case by case for each k.
k ? 4: Since each vertex has degree at most 6, we have LHS ? 6k. Also, RHS ?
2k(k?1) = k(2k?2) ? 6k for k ? 4.
k = 3: LHS ? 18.
If there is at least one vertex with degree 6, there can not be any vertices with degree
1. So, RHS ? 2:3:2 + 3:2 = 18 since p ? 6. If there is no vertex with degree 6, then LHS
? 15, and RHS ? 2:3:2+(1+1+1) = 15.
k = 2: LHS ? 12.
If there is at least one vertex with degree 6, there can not be any vertices with degree
1. So, RHS ? 2:2:1+(2+2+2+2) = 12 since p ? 6.
28
Suppose d1 ? 5; So, LHS ? 10.
If d1 = d2 = 5, then since we exclude the case where the sequence is (5;5;1;1;1;1),
Pp
i=3 minfdi;2g? 5. Butwecannothaveoddnumberofverticeswithodddegree, implying
that Ppi=3 minfdi;2g? 6. So, RHS ? 2:2:1+6 = 10 = LHS.
If LHS = 9 with d1 = 5, again since we can not have odd number of vertices with odd
degree, Ppi=3 minfdi;2g ? 5. So, RHS ? 2:2:1 + 5 = 9. If LHS ? 8, RHS ? 2:2:1 + (1 +
1+1+1) = 8 since we have at least 6 parts, and each vertex has degree at least 1.
k = 1: LHS ? 6 since each vertex has degree at most 6.
If d1 = 6, then the rest of the vertices must have degree at least 2. So, RHS ?
0+(2+2+2+2+2) = 10 > 6. If d1 ? 5, then RHS ? 0+(1+1+1+1+1) = 5 ? LHS.
For all the cases we have shown that the inequality holds. Hence, we are done.
We are now ready to prove an important technical result, which is used to obtain
memorable corollaries. We flrst deflne a graph ?0 that will eventually be shown to be an
amalgamation of Hamilton cycles in Kpm.
Let G 2 G(n;d). By Lemma 5.2, we can give G a proper p-vertex coloring c in
which jX1j = jX2j = ::: = jXpj = m where Xi is the set of vertices colored i. Now, let
H(G;c) = Kpm ?E(G) and X1;X2;:::;Xp be the parts of Kpm.
Recall from Chapter 2 that if G 2 G(n;d), then G has a cut-vertex v; one subgraph Cd
of G?v may be larger than the other components. Let X = V(Cd), Y = V(G(n;d))?X,
and ? = jE(H(G;c)[Y])j. Let ?0(T0;B) be the multigraph formed from H(G;c) by applying
29
the amalgamation function
f(v) =
8>
<
>:
ti if v 2 X \Xi
bi if v 2 Y \Xi
where T0 = Spi=1 ti and B = Spi=1 bi (think of ti and bi as top and bottom vertices respec-
tively colored i).
By using Lemma 5.2 to color the vertices of G, it follows immediately that ?(ti) 2
fbjXjp c;djXjp eg and ?(bi) 2fbjYjp c;djYjp eg.
Let ?(T = T0 [f1g;B) be formed from ?0(T0;B), by
1. deleting the edges joining two vertices in X, then
2. adding a new vertex 1 to T0, deleting each edge fbi;bjg, and joining both bi and bj
to 1 with an edge instead.
So,
d?(v) ? d?0(v) for all v 2 T0,
d?(v) = d?0(v) for all v 2 B, and
d?(1) = 2e(?0B):
(?)
Now, ?(T;B) is a bipartite graph. Let ? = ?(T;B), ?T = ?(T;B)[T], and ?B = ?(T;B)[B]
for simplicity.
The following result will be used in the proof of Theorem 5.8, and it is also a vital tool
used in proving Theorem 3.3.
Theorem 5.7 ([19]) Every bipartite multigraph has an equitable k-edge-coloring for all
k ? 1.
30
We are now ready to prove the main result. The following builds upon ?0 and H(G;c)
deflned above.
Theorem 5.8 Let m and d ? 3 be odd, and p ? d + 1 be even such that mp ? (d + 1)2.
Then there exists a set S of ? Hamilton cycles in Kpm such that Kpm ?E(S) is primitive, if
8>
>>>>
<
>>>>
>:
? ? ?;
?(ti)?(tj) ? ??+2b ?p?1c for any ti;tj 2 T0, and
?(?T0)??(?T0)
2 ? ?;
where ? ? 4 when p = 4, ? ? 3 when p = 6, and ? = 2 when p ? 8.
Proof Since n = mp ? (d+1)2, there exists a primitive graph G 2 G(n;d) with m;p, and
d as assumed. Let H(G;c), ?, and ?0 be as described in the previous paragraphs. We need
to give an ?-edge-coloring to the edges of H(G;c) where each color induces an Hamilton
cycle. This is done in 3 steps:
(1) the edges of ?0 except for the ones joining two vertices in T are equitably colored;
(2) the remaining edges in ?0 are colored in 3 steps:
(i) color some edges with to boost the degree of each vertex to an even number
in each color class; then
(ii) ensure each color class is connected; and thirdly
(iii) color the remaining edges;
(3) ?0 is disentangled.
31
In order for each color class eventually induce a Hamilton cycle, we need each color k,
1 ? k ? ? to appear 2?(v) times at each vertex v 2 T0 [B in ?0. Since ? is bipartite, by
Theorem 5.7 we can begin with an equitable 2?-edge-coloring of the edges of ? (i:e: using
twice as many colors as we end up with). By (?), we have d?(1) = 2?. Also, the assumption
? ? ? implies 2? ? 2?. This implies that every color k, 1 ? k ? 2?, appears on at most one
of the edges incident with 1, and appears on exactly ?(B) edges in ? (by Theorem 5.7).
Now, deflne a coloring of the edges of ?0 from ? as follows:
(a) for each edge fbi;bjg in ?0, if f1;big and f1;bjg are colored t and k respectively,
then color fbi;bjg with t and recolor all edges colored k with t;
(b) arbitrarily pair the remaining colors and recolor the edges joining the vertices of T to
the vertices of B one of the paired colors.
This completes step (1). Notice that, for 1 ? k ? ?, the number of edges colored k
joining vertices in T0 to the vertices in B is
8>
<
>:
2?(B)?2 if k is a color on an edge incident with 1 in ?, and
2?(B) otherwise.
Now we can start step (2) in coloring edges of ?0. Since we assumed ?(?T0)??(?T0) ?
2?, for any vertex ti;tj 2 T0 and for any color k, 1 ? k ? 2?, in the 2?-edge coloring
of ? we have jck(ti) ? ck(tj)j ? 2 by Lemma 5.3. So, in the ?-edge coloring of ?0 we get
jck(ti)?ck(tj)j? 4. For any color 1 ? k ? ? and any vertex ti 2 T0, let ck = maxfck(ti)gpi=1,
32
and deflne
dk =
8>
>>>>
<
>>>>
>:
ck +3 if ck is odd and p = 4,
ck +2 if ck is even, and
ck +1 otherwise.
Then deflne a function DIFk(ti) = dk ?ck(ti). To boost each vertex ti 2 T0 to have even
degree in each color class, the edges of a subgraph with degree sequence fDIFk(ti)gpi=1 are
colored k for 1 ? k ? ?. First, we need to show (DIFk(t1);DIFk(t2);:::;DIFk(tp)) is
a degree sequence by using Lemma 5.6. We can relabel the vertices so that DIFk(t1) ?
DIFk(t2) ?;:::;? DIFk(tp).
Since, for each k, Ppi=1 ck(ti) is equal to 2?(B) or 2?(B) ? 2, this sum is even. So,
there are even number of vertices with odd ck(ti). Clearly DIFk(ti) is odd if ck(ti) is odd,
implying that there are also even number of odd DIFk(ti)?s, and so Ppi=1 DIFk(ti) is even
as well. So, Lemma 5.6 (ii) is satisfled.
Since jck(ti)?ck(tj)j ? 4 and we add at most 2 to the ck(ti)?s for p ? 6, the largest
possible value of DIFk(ti) is 6 when p ? 6.
Supposep ? 6andthereisatleastonevertextj withDIFk(tj) = 6. ThenPpi=1 DIFk(ti)?
maxfDIFk(ti)gpi=1 ? 10 ? 6sincetheDIFk(ti) ? 2foreachvertex. ThereforePpi=1 DIFk(ti)?
maxfDIFk(ti)gpi=1 ? maxfDIFk(ti)gpi=1, and so Lemma 5.6 (iii) is satisfled.
Next suppose p ? 6 and maxfDIFk(ti)gpi=1 ? 5. Then we have Ppi=1 DIFk(ti) ?
maxfDIFk(ti)gpi=1 ? 5 since the DIFk(ti) ? 1 for each vertex. Again, this implies that
Pp
i=1 DIFk(ti)?maxfDIFk(ti)g
p
i=1 ? maxfDIFk(ti)g
p
i=1, so Lemma 5.6 (iii) is satisfled.
Similarly, for p = 4 and odd ck, the largest possible DIFk(ti) is 7 since we add 3 to
the ck. So, we have Ppi=1 DIFk(ti) ? maxfDIFk(ti)gpi=1 ? 9 since the DIFk(ti) ? 3 for
33
each vertex. Therefore Ppi=1 DIFk(ti)?maxfDIFk(ti)gpi=1 ? maxfDIFk(ti)gpi=1 since the
DIFk(ti) ? 7 for each vertex. For even ck the largest possible DIFk(ti) is 6 since we add 2
to the ck. So, maxfDIFk(ti)gpi=1 ? 6, implying Ppi=1 DIFk(ti)?maxfDIFk(ti)gpi=1 ? 6;
Pp
i=1 DIFk(ti) ? maxfDIFk(ti)g
p
i=1 ? maxfDIFk(ti)g
p
i=1. Therefore Lemma 5.6 (iii) is
satisfled for every case. Hence, (DIFk(t1);DIFk(t2);:::;DIFk(tp)) is a ?-multigraphic
degree sequence.
Since we assumed that ?(ti)?(tj) > ?? for every ti;tj 2 T0, we have enough edges
between any ti;tj 2 T to realize this degree sequence with multigraph of index ?, for each
color k, 1 ? k ? ?. So, for each 1 ? i ? p and 1 ? k ? ?, we can increase the degree of ti in
the k?th color class from ck(ti) to dk by adding this graph. This completes step 2-(i).
Next, to ensure that each color class is connected, we add an Hamilton cycle on p
vertices to ?0T0 for each color k, for 1 ? k ? ?. Since p is even, there are p?1 Hamilton
cycles in a Hamilton decomposition of 2Kp. Since we need one Hamilton cycle for each
color class, we need to have b ?p?1c copies of 2Kp to have enough Hamilton cycles to ensure
each of the ? color class is connected. The condition ?(ti)?(tj) ? ?? + 2b ?p?1c guarantees
there are still enough edges between every ti;tj 2 T0 to do that. Now, the degree of each
ti 2 T0 at each color class is dk +2, and step 2-(ii) is completed.
By the assumption that m and d are odd and p is even, the degree of each vertex in
Kpm ? E(G) is m(p ? 1) ? d = 2? is even, so the degree of each vertex ai of ?0, namely
?(ai)2?, is also even. If we take out the colored edges from ?0, the degree of each vertex in
the new graph ?? is 8
><
>:
?(ai)2???(dk +2) for ai 2 T, and
0 for ai 2 B.
34
Since dk is even, d??(ti) = ?(ai)2???(dk + 2) is even. So, the graph ?? is eulerian. By
Lemma 3.4, we can give ?? an evenly equitable edge coloring with ? colors. So, for each
ti 2 T0, and each 1 ? k ? ?, d??(k)(ti) is either 2
jd
??(ti)
2?
k
or 2
ld
??(ti)
2?
m
. But dk is even, so 2?
divides d??(ti). Therefore, for each ai 2 V(?0),
d??(k)(ai) =
8>
<
>:
2?(ai)?dk ?2 for ai 2 T0, and
0 for ai 2 B.
We now gather together all we know. For all ti 2 T0 and 1 ? k ? ?, ti is incident with
ck edges colored with color k in step 1, DIFk+2 edges colored with color k in step 2-(i) and
2-(ii), and 2?(ti)?(ck +DIFk(ti)+2) = 2?(ti)?(dk +2) edges colored with color k in step
2-(iii). So now, when we add them up, each vertex ti is incident with 2?(ti) edges colored
with k. Because of step 2-(ii), each color class is connected. Similarly, d??(k)(bi) = 2?(bi)
for each bi 2 B.
Now, for 1 ? i ? p we can add ??(ai)2 ? loops to each ai 2 V(?0) and ?(ti)?(bi) edges
between ti 2 T0 and bi 2 B, coloring the new edges and loops with color fi. Also, add the
edges colored 0 corresponding to E(G), the edges in the primitive graph G 2 G(n;d). Now
we have the amalgamated graph A described in the Lemma 3.2 where for 1 ? k ? ?
(a) A(k) is connected, and
(b) dA(k)(ai) = 2?(ai), for all ai 2 A
where A(k) is the subgraph of A induced by the edges colored k, and dA(k)(ai) is the degree
of ai in A(k).
We can now apply Theorem 3.3 to obtain the graph H, satisfying
35
(i) H ?= Kn
(ii) for all u 2 f?1(ai),
dH(k)(u) = dA(k)(ai)?(a
i)
=
8
><
>:
2 for 1 ? k ? ?
m?1 for k = fi
(iii) for 1 ? k ? ?, H(k) is connected, since dA(k)(ai)?(ai) = 2 is even for all ai 2 V(A).
Hence, we have the desired s = ?+2 coloring, in which
(1) removing the edges colored fi converts Kmp to Kpm,
(2) the edges colored 0 induce a graph in G(n;d), and
(3) each of the other colors induces a Hamilton cycle.
Theorem 5.8 leads to the following Corollary.
Corollary 5.9 Let p be flxed. Then there exists a set S of ? Hamilton cycles in Kpm for all
m ? md such that Kpm ?E(S) is primitive, where md is a function of d.
Proof We will show that for flxed p there exists a constant md for each d such that the
conditions of the Theorem 5.8 are satisfled for all m ? md.
Let?s flrst consider the condition ? ? ?. We can write it as ??? = m(p?1)?d2 ?? ? 0.
Then f(m) = m(p?1)?d2 ?? is an increasing function of m since ? is flxed for a flxed d, and
f is linear on m with positive coe?cient since p ? 4. So, there exists a constant m1 such
that f(m) ? 0 for all m ? m1.
Now, let?s consider the second condition, ?(ti)?(tj) ? ?? + 2b ?p?1c for any ti;tj 2 T0.
Since ?(ti)?(tj) ? bV(Cd)p c2, it is enough to show g(m) = bV(Cd)p c2 ? ?? ? 2b ?p?1c is an
increasing function.
36
g(m) = bV(Cd)p c2 ????2b ?p?1c
= bmp?d2?d+1p c2 ??m(p?1)?d2 +2bm(p?1)?dp?1 c
= bm? (d2+d?1)p c2 ??m(p?1)?d2 +2bm? dp?1c
Obviously, g is a quadratic function on m and concave up. So, there exists a m2 such that
g(m) ? 0 for all m ? m2.
Lastly, let?s consider ?(?T0)??(?T0)2 ? ?. We will show that h(m) = 2???(?T0)+?(?T0)
is an increasing function on m. Since we partitioned the vertices into p parts by giving
an equitable p-vertex coloring to Cd and an equitable p-vertex coloring to the rest of the
vertices of the primitive graph on mp vertices, if we let a = bjV(C1)[V(C2)[???[V(Cd?1[v)jp c,
then ?(bi) is either a or a + 1 for all bi 2 B. So, for all ti 2 T0, ?(ti) is either m ? a or
m?a?1. If we let b = jV(C1)[V(C2)[???[V(Cd?1 [v)j, we get
?(?T0) = (m?a)(b?a)?(m?a)d
= mb?ma?ab?a2 ?md+ad
and
?(?T0) = (m?a?1)(b?a?1)?(m?a?1)d
= mb?ma?m?ab+a2 +2a?b+1?md+ad+d:
So,
h(m) = 2???(?T0)+?(?T0)
= m(p?1)?m+2a?b+1
= m(p?2)+2a?b+1:
37
Since a and b do not depend on m, and p and d are flxed, h(m) is a linear function of
m. Also since p ? 4, (p? 2) is positive. Therefore, there exists a constant m3 such that
h(m) ? 0 for all m ? m3.
Hence, for flxed p, there exists a constant md = maxfm1;m2;m3g for each d so that
for all m ? md all three conditions of Theorem 5.8 is satisfled.
The following corollary is an example of the use of Corollary 5.9, speciflcally evaluating
md in some cases.
Corollary 5.10 Let p = 6. Then there exists an Hamilton decomposition of a graph G on
mp vertices with primitive complement in Kpm for all m ? md where
md =
8
><
>:
15 if d = 3; and
113 if d = 5:
Proof First, let d = 3:
We will flrst show that f(m) ? 0 for all m ? 15, where f(m) = m(p?1)?d2 ??. For p = 6
and d = 3, we have ? = 34, and so we have f(m) = 5m?32 ?34. f(15) = 36?34 = 2 ? 0
and since f is an increasing function we have f(m) ? 0 for all m ? 15.
Second, we will show that g(m) ? 0 for all m ? 15, where
g(m) = bV(Cd)p c2 ????2b ?p?1c
= bmp?d2?d+1p c2 ??m(p?1)?d2 +2bm(p?1)?dp?1 c:
Since ? 2 f2;3g for p = 6, and b = 11 for d = 3, we have g(m) = b6m?116 c2 ?(5m?32 )3?
2b5m?310 c. So, g(15) = 132 ? 108 ? 14 = 47 and g(13) = 112 ? 117 ? 12 = 16. Since g is
38
quadratic on m with positive coe?cient where g(15) > g(13) it is increasing around 15.
Hence, g(15) ? 0 implies that g(m) ? 0 for all m ? 15.
Next, let?s show h(m) ? 0 for all m ? 15, where
h(m) = 2???(?T0)+?(?T0)
= m(p?1)?m+2a?b+1
= m(p?2)+2a?b+1:
For p = 6 and d = 3 we have a = 1 and b = 11. So, we have h(m) = 4m+2?11+1 = 4m?8
and h(15) = 52 ? 0. Since h is an increasing function, we can say h(m) ? 0 for all m ? 15.
Hence, we are done with the d = 3 case.
Now, for d = 5, we can proceed similarly.
For p = 6 and d = 5, we have a = 4, b = 29, and ? = 278. So, we have f(m) =
5m?5
2 ?278. f(113) = 280?278 = 2 ? 0 and f is increasing.
Next, we have g(m) = b6m?296 c2?(5m?52 )3?2b5m?510 c. Also, g(113) = 1082?(280)3?
(52)2 = 10;712 and g(111) = 1062 ? (275)3 ? 2(55) = 10;311. Since g is quadratic,
g(113) > g(111), and g(113) ? 0, g(m) ? 0 for all m ? 113.
Lastly, we have h(m) = m(p ? 2) + 2a ? b + 1. For p = 6 and d = 5, we have
h(m) = 4m + 8?29 + 1 = 4m?20. So, h(113) = 432. Since h is an increasing function,
we have h(m) ? 0 for all m ? 113.
Hence, we are done.
Remark: Notice that f(md ? 2) < 0 in both cases, so we can not lower md with this
approach.
39
Chapter 6
Conclusion
In this dissertation, we used a very powerful graph homomorphism tool called amalga-
mation. Also the results of Leach and Rodger [13] we mentioned in Chapter 3 are used in
proving our technical results.
In Chapter 4, the problem of Hamilton decompositions of graphs with primitive com-
plements in Kn was completely solved by the following result.
Theorem 4.1 There exists a set S of x edge-disjoint Hamilton cycles in Kn such that
Kn ?E(S) is primitive if and only if
8>
>>>>
<
>>>
>>:
x = n?12 if n is odd,and
x ? n?
pn
2 if n is even.
And at the and of the Chapter 4, we conjectured that if some conditions on G(n;d)
are relaxed to allow another family of primitive graphs G0(n;d), then there still exists a
Hamilton decomposition of Kn ?E(G) for all G 2 G0(n;d).
In Chapter 5, we worked on Hamilton decompositions of graphs with primitive com-
plements in complete multipartite graphs Kpm. We proved that Erd}os-Gallai Theorem can
be modifled for multigraphs. Then, we proved the following theorem.
40
Theorem 5.8 Let m and d ? 3 be odd, and p ? d+1 be even such that mp ? (d+1)2.
Then there exists a set S of ? Hamilton cycles in Kpm such that Kpm ?E(S) is primitive, if
8>
>>>>
<
>>>
>>:
? ? ?
?(ti)?(tj) ? ??+2b ?p?1c for any ti;tj 2 T0, and
?(?T0)??(?T0)
2 ? ?
where ? ? 4 when p = 4, ? ? 3 when p = 6, and ? = 2 when p ? 8.
Theorem 5.8 leaded us stronger results for multipartite graphs with p flxed and n large
enough.
This work also leads us other interesting questions; since the chromatic number of the
primitive graph is important to partition its vertices, it would be interesting to know what
the smallest primitive graph with given chromatic number is. This is an open question that
is likely to be challenging to solve. It is one that needs to be addressed if one is to tackle
the case where p ? d.
41
Bibliography
[1] P. Adams, E.J. Billington, D.E. Bryant, and S.I. El-Zanati, On the Hamilton-Waterloo
problem, Graphs and Combin., 18 (2002), no. 1, 31{51.
[2] J.A. Bondy, and U.S.R. Murty, Graph Theory with Applications, Macmillan & Co.,
London, 1976.
[3] D.E. Bryant, Hamilton cycle rich two-factoizations of complete graphs, J. Comb. De-
signs, 12 (2004), no. 2, 147{155.
[4] H. Buchanan II, Graph factors and Hamiltonian decompositions, Ph.D. Dissertation,
West Virginia University, 1997.
[5] A.J.W. Hilton, Hamiltonian decompositions of complete graphs, J. Combin. Theory
Ser. B, 36 (1984), no. 2, 125{134.
[6] A.J.W. Hilton, Canonical edge-colourings of locally flnite graphs, Combinatorica, 2
(1982), 37{51.
[7] D.G. Hofiman, C.A. Rodger, and A. Rosa, Maximal sets of 2-factors and Hamiltonian
cycles, J. Combin. Theory Ser. B, 57 (1993), no. 1, 69{76.
[8] P. Horak, R. Nedela, and A. Rosa, The Hamilton-Waterloo problem: the case of Hamil-
ton cycles and triangle-factors, Discrete Math., 284 (2004), no. 1-3, 181{188.
[9] D. K?onig, Theorie der endlichen und unendlichen Graphen, Leipzig, 1936.
[10] T.P.Kirkman, On a problem in combinations, CambridgeandDublinMathJ., 2(1847),
197{204.
[11] B. Auerbach and R. Laskar, On decomposition of r-partite graphs into edge-disjoint
Hamilton circuits, Discrete Math., 14(3) (1976), 265{268.
[12] E. Lucas, R?ecr?eationes Math?ematiques, vol. II, Gauthier-Villars, Paris, 1892.
[13] C.D. Leach and C.A. Rodger, Hamilton decompositions of complete graphs with a 3-
factor leave, Discrete Math., 279 (2004), 337{344.
[14] S.L. Logan and C.A. Rodger, Maximal sets of Hamilton cycles in complete multipartite
graphs ?II, submitted.
[15] H.L. Fu, S. L. Logan, and C. A. Rodger, Maximal sets of Hamilton cycles in K2p ?F,
Discrete Math., to appear.
42
[16] J. Petersen, Die Theorie der regul?aren graphs, Acta Math., 15 (1891), 193{220.
[17] C.A. Rodger, Hamilton decomposable graphs with specifled leaves, Graphs and Combin.,
no. 4, 20 (2004), 541{543.
[18] A. Hajnal and E. Szemer?edi, Proof of a conjecture of P. Erd}os, Combinatorial Theory
and its Applications, Vol. 2 (P. Erd}os, A. R?enyi, and T. S?os, Eds.), 601{623, North-
Holland, London, 1970.
[19] D. de Werra, Equitable colorations of graphs, Revue Franqaise d?Informatique et de
Recher-. che Oprationnelle, R-3 (1971), 3{8.
[20] W.T. Tutte, Graph factors, Combinatorica 1, (1981), 79{97.
43