C4-Factorizations with Two Associate Classes
by
Michael Tiemeyer
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial fulfillment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
May 14, 2010
Keywords: 4-cycle, Factorization
Copyright 2010 by Michael Tiemeyer
Approved by:
Chris Rodger, Chair, Scharnagel Professor of Mathematics & Statistics
Dean Hoffman, Professor of Mathematics & Statistics
Pete Johnson, Professor of Mathematics & Statistics
Doug Leonard, Professor of Mathematics & Statistics
Abstract
Let K = K(a,p;?1,?2) be the multigraph with: the number of vertices in each part
equal to a; the number of parts equal to p; the number of edges joining any two vertices
of the same part equal to ?1; and the number of edges joining any two vertices of different
parts equal to ?2. This graph was of interest to Bose and Shimamoto in their study of group
divisible designs with two associate classes [1]. Necessary and sufficient conditions for the
existence of z-cycle decompositions of this graph have been found when z ? {3,4}[4, 5]. The
existence of resolvable 4-cycle decompositions of K has been settled when a is even [2], but
the odd case is much more difficult. In this paper, necessary and sufficient conditions for
the existence of a C4-factorization of K(a,p;?1,?2) are found when a ? 1(mod 4) and ?1 is
even, and all cases with one exception have been solved when ?1 is odd.
ii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 ?1 is Even . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 ?1 is Odd and Small . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 ?1 is Odd and Large . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
iii
List of Figures
1.1 K(a,p;?1,?2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Example C4-factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.1 Example of a mixed C4-factor, P(s,4), of K(13,4;?1,?2). . . . . . . . . . . . 7
3.2 Example of an efficient C4-factor, P?(s,j,r), of K. . . . . . . . . . . . . . . . 8
5.1 Example of a 2-factor, M0(j). . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2 Example of an inefficient C4-factor. . . . . . . . . . . . . . . . . . . . . . . . 25
5.3 W(j) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.4 C with a = 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.5 D with a = 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.6 The 4-cycles of R1,1 incident with vertices {4i + 2 | i ? Zb}; the other half of
R1,1 is formed by moving each cycle ?down? one level in each part. . . . . . 31
5.7 The 4-cycles of T1 incident with vertices {4i+2 | i ? Zb}; the other half of T1
is formed by moving each cycle ?down? one level in each part. . . . . . . . . 33
5.8 T2 with a = 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.9 Near C4-factor of W+(j) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.10 Near C4-factor of W+(j) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
iv
List of Tables
5.1 Locations of Mixed Edges in A . . . . . . . . . . . . . . . . . . . . . . . . . 30
v
Chapter 1
Introduction
In this dissertation, graphs usually contain multiple edges. In particular, if G is a simple
graph then for any ? ? 1, let ?G denote the multigraph formed by replacing each edge in G
with ? edges. Throughout this dissertation we allow sets to contain repeated elements. Let
Cz denote a cycle of length z.
Let K = K(a,p;?1,?2) denote the graph formed from p vertex-disjoint copies of the
multigraph ?1Ka by joining each pair of vertices in different copies with ?2 edges (so naturally,
?1,?2 are non-negative integers). The vertex set, V (K(a,p;?1,?2)), is always chosen to be
Za?Zp, with parts Za?{j} for each j ? Zp; naturally, each part induces a copy of ?1Ka.We
say the vertex (i,j) is on level i and in part j. An edge is said to be a mixed edge if it joins
vertices in different parts, and is said to be a pure edge (in part j) if it joins two vertices in
the jth part.
. . . . . . . . . . . .
. . .
. . .
. . .
?1
1 2 3 p
?2
a
4
3
2
1
Figure 1.1: K(a,p;?1,?2)
A 2-factor of a graph G is a spanning 2-regular subgraph of G. A 2-factorization of
G is a set of edge-disjoint 2-factors, the edges of which partition E(G). A Cz-factorization
1
is a 2-factorization such that each component of each 2-factor is a cycle of length z; each
2-factor of a Cz-factorization is known as a Cz-factor. A G-decomposition of a graph H is
a partition of E(H), each element of which induces a copy of G. Cz-factorizations are also
known as resolvable Cz-decompositions.
There has been considerable interest over the past 20 years in Cz-decompositions of
various graphs, such as complete graphs and complete mutipartite graphs. In the resolvable
case, these results are collectively known as addressing the Oberwolfach problem. More
recently, the existence problem for Cz-decompositions of K (a,p;?1,?2) for z = {3,4} has
been solved [4, 5]. Such decompositions are known as Cz-group-divisible designs with two
associate classes, following the notation of Bose and Shimamoto who considered the existence
problem for Kz-group divisible designs. The reason for this name is that the structure can
be thought of as partitioning ap symbols, or vertices, into p sets of size a in such a way that
symbols that are in the same set in the partition occur together in ?1 blocks, and are known
as first associates, whereas symbols that are in different sets in the partition occur together
in ?2 blocks, and are known as second associates.
Cz-factorizations of G have also been of interest[6]. Recently the existence of a C4-
factorization of K (a,p;?1,?2) has been completely settled when a is even [2], but the case
where a is odd is proving to be considerably more difficult. In this dissertation, we consider
the case where a ? 1(mod 4), completely settling the case where ?1 is even and and all but
one exception when ?1 is odd.
It turns out that every C4-factor must contain at least p mixed edges. So a C4-factor
is said to be efficient if it contains exactly p mixed edges, and otherwise it is said to be
inefficient. If a C4-factor consists entirely of mixed edges, we say it is a mixed C4-factor.
When ?1 is even, it is possible for all C4-factors to be efficient; indeed, this is necessary
when ?1 is maximum. However, when ?1 is odd, there must be some C4-factors that are
inefficient, and it is this property that makes the ?1 odd case so difficult.
2
Example 1 The following examples of C4-factors of K(5,4;4,2) give good insight into
the constructions used in Sections 3 and 4 (see Figure 1.2):
(0,3)(0,0)
(4,0) (4,3)
Figure 1.2: Example C4-factors
For each r ? Z5, let pi?r (k) = {(r + 1,k),(r + 2,k),(r + 4,k),(r + 3,k)} be a near
C4-factor (i.e. includes all except one of the vertices) in the kth part. Then uniontext0?k?3 pi?r (k)?
{(r,0),(r,1),(r,2),(r,3)} is a C4-factor of K (see the solid edges) for the case when r = 0.
Notice that uniontext0?k?3 pi?r (k)?{(r,0),(r,2),(r,1),(r,3)} is also a C4-factor that could be used
if ?1 is large (see the dashed mixed edges). Finally, observe that mixed edges can easily be
used in C4-factors of the form P(s,j) = {((i,0),(i + j,1),(i,2),(i + j,3))|i ? Z5} (see the
dotted lines for one component when j = 2).
3
Chapter 2
Preliminary Results
We begin by finding some necessary conditions in the next two lemmas.
Lemma 2.1 Let a be odd. If there exists a C4-factorization of K(a,p;?1,?2), then:
1. p ? 0(mod 4), and
2. ?2 > 0 and is even.
Proof Since the number of 4-cycles in each C4-factor is the number of vertices divided by
four, four must divide ap, and since a is odd, p ? 0(mod 4). Similarly, if ?2 = 0 then the
number of vertices in each part, namely a, would be divisible by 4, contradicting a being
odd.
Each vertex is joined with ?1 edges to each of the (a?1) other vertices in its own part
and with ?2 edges to each of the a(p?1) vertices in the other parts; so the degree of each
vertex is:
dK(v) = ?1(a?1)+?2a(p?1).
Clearly, since K has a C4-factorization, it is regular of even degree. Since a is odd, (a?1)
is even so the first term in dK(v) is even. The second term must therefore be even, so since
both a and (p?1) are odd, ?2 must be even.
Lemma 2.2 Let a ? 1(mod 4). If there exists a C4-factorization of K(a,p;?1,?2), then
?1 ? ?2a(p?1).
4
Proof Since a ? 1(mod 4), each C4-factor contains at most (a?1) pure edges in each part.
So each C4-factor contains at most (a?1)p pure edges. Since there are ?1parenleftbiga2parenrightbigp pure edges,
the number of C4-factors in any C4-factorization is at least:
?1parenleftbiga2parenrightbigp
(a?1)p =
?1a
2 .
Each C4-factor has ap edges, of which at most (a?1)p = ap?p are pure, so there are at least
p mixed edges in any C4-factor. Then the number of mixed edges in any C4-factorization is
at least:
?1ap
2 .
Therefore, this number must be at most the number of mixed edges, ?2parenleftbigp2parenrightbiga2, in K:
?1ap
2 ? ?2
parenleftbiggp
2
parenrightbigg
a2,
so
?1 ? ?2a(p?1).
A set of 4-cycles is said to be a near C4-factor of G if it contains |V(G)|4 4-cycles, which
are vertex-disjoint; the vertex in V(G) that is in none of these cycles is called the deficient
vertex of the near C4-factor. We will use the following known results in considering C4-
factorizations of K(a,p;?1,?2).
Lemma 2.3 [3] Suppose a ? 1(mod 4). Then near C4-factorizations of ?Ka exist for all
even ?.
Lemma 2.4 [7] Suppose p ? 0(mod 4). Then C4-factorizations of ?Kp exist for all even ?.
5
Chapter 3
?1 is Even
Theorem 3.1 Suppose a ? 1(mod 4), and ?1 is even. There exists a C4-factorization of
K(a,p;?1,?2) if and only if:
1. p ? 0(mod 4),
2. ?2 > 0 and is even, and
3. ?1 ? ?2a(p?1).
Proof The necessity of these conditions follows from Lemmas 2.1 and 2.2. So now assume
that K satisfies conditions (1-3).
Using Lemma 2.4, let pi = {pis|s ? Z?2(p?1)
2
, pis is the sth C4-factor of a C4-factorization
of ?2Kp}. For each s ? Z?2(p?1)
2
, j ? Za, and i ? Za, let
P(s,j,i) = {((i,w),(i+j,x),(i,y),(i+j,z)) | (w,x,y,z) ? pi,w < x,y,z}.
Then for each s ? Z?2(p?1)
2
and for each j ? Za, define the following mixed C4-factor of
K(a,p;?1,?2) (see Figure 3.1):
P(s,j) =
uniondisplay
i?Za
P(s,j,i).
Notice that it is easy tosee thatthese C4-factorscan be used toproduce aC4-factorization
of K(a,p;0,?2), namely:
uniondisplay
s?Z?2(p?1)
2
uniondisplay
j?Za
P(s,j).
6
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
Figure 3.1: Example of a mixed C4-factor, P(s,4), of K(13,4;?1,?2).
However, we may have pure edges to use too, which is accomplished by spreading the
4-cycles in P(s,j) among a C4-factors, each of which contains P(s,j,i) for some i ? Za
together with a pure near C4-factor in each part. More specifically, for each r ? Za and
k ? Zp, using Lemma 2.3, let pi?r (k) be the near C4-factor of a near C4-factorization of 2Ka
on the vertex set Za ?{k} with deficient vertex (r,k).
For each r ? Za, s ? Z?2(p?1)
2
, and j ? Za, let
P?(s,j,r) = P(s,j,r)?
?
??
?
uniondisplay
(w,x,y,z)?pis
w<x,y,z
parenleftBig
pi?r (w)?pi?(r+j)(mod a)(x)?pi?r (y)?pi?(r+j)(mod a)(z)
parenrightBig
?
??
?
be an efficient C4-factor of K (see Figure 3.2).
Notice that in parts w and y, P(s,j,r) contains the vertex only on level r, and in parts
x and z, it contains the vertex only on level (r + j)(mod a); in each case this vertex is the
deficient vertex in the near C4-factor being used. So, then P?(s,j,r) is a C4-factor of K
that contains exactly p mixed edges and p near C4-factors of Ka. Furthermore,
7
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
Figure 3.2: Example of an efficient C4-factor, P?(s,j,r), of K.
uniondisplay
r?Za
P?(s,j,r)
contains:
(a) each pure edge twice, and
(b) precisely the mixed edges in P(s,j).
Let S = {(s,j) | s ? Z?2(p?1)
2
,j ? Za}. Let S1 ? S have size ?12 . Notice that by condition
3 of the theorem, ?1 ? ?2a(p ? 1), so |S1| = ?12 ? ?2a(p?1)2 = |S|, so such a set |S1| exists.
Then
uniondisplay
r?Za
(s,j)?S1
P?(s,j,r)
is a set of ?1a2 C4-factors that contains each pure edge 2|S1| = ?1 times by (a), and uses
precisely the mixed edges in
8
uniondisplay
(s,j)?S1
P(s,j)
by (b). Therefore, the required C4-factorization of K is defined by
P =
?
??
?
uniondisplay
r?Za
(s,j)?S1
P?(s,j,r)
?
??
??
?
? uniondisplay
(s,j)?S\S1
P(s,j)
?
?.
Notice that
|P| = a|S1|+|S \S1|
= ?1a2 + ?2a(p?1)2 ? ?12
= ?1(a?1)2 + ?2a(p?1)2
as required.
9
Chapter 4
?1 is Odd and Small
We now turn our attention to the case where ?1 is odd. The main difficulty now is that
there is no near C4-factorization of ?1Ka, and so some C4-factors cannot look like P?(s,j,r)
in the previous section. Instead, they must use more than p mixed edges; thus, some C4-
factors must be inefficient. So we need tools that will construct the inefficient C4-factors.
There are two constructions used to produce the C4-factorization of K when ?1 is odd.
One construction produces the required C4-factorization when ?1 falls within the range
1 ? ?1 ? a(p ? 1)?2 ? a, and the other does so when (a ? 2) ? ?1 ? a(p ? 1)?2 ? 1.
Notice that the former construction produces the factorization for small values of ?1, and
the latter for large values of ?1. There is a large intersection of values for ?1 for which either
construction is appropriate, but clearly both are needed to produce the factorization for all
possible ?1 values.
We begin with the construction that produces the factorization of K for small values of ?1.
Let P2 denote a path of length 2. We begin with a special cyclic P2 ?decomposition of
Ka. Let V(Kn) = Zn, and define the difference of the edge {x,y} ? E(Kn), with x < y, to be
d(x,y) = min{y?x,n?(x?y)}. If B is a set of paths of length 2, let V(B) and E(B) denote
the set of vertices and edges in the paths in B respectively, and let d(B) be the multiset of
differences of the edges in E(B). For j ? Zn, let Bj = {(x + j,y +j,z + j) | (x,y,z) ? B},
reducing the sums modulo n. It is well known that if d(B) = {1,2,..., n?12 }, then
uniondisplay
j?Zn
Bj
10
is a cyclic P2-decomposition of Kn. Each 2-path in B is known as a base path.
Lemma 4.1 Let a ? 1(mod 4). There exists a cyclic P2-decomposition of Ka with set of
base paths B = {bk | k ? Za?1
4
}, for which:
1. the base paths bk for each k ? Za?1
4
are vertex disjoint, and
2. there exists a function, f, such that:
(a) f : B ? Za \V(B), and
(b) N(B) = {N(bk,x) = (a ? f(bk) ? x) | k ? Za?1
4
,xis an end vertex of bk} ? Za
(reducing calculations modulo a) has size a?12 (i.e. contains no repetitions).
Remark Let f(B) = {f(bk) | bk ? B}. Notice that since |V(B)| = 3a?34 ,|f(B)| = |B| =
a?1
4 , and since the range of f ensures that V(B)?f(B) = ?, it follows that V(B)?f(B) =
Za\{v} for some v ? Za. This vertex v is named the deficient vertex of B. For Bj, j ? Za, we
can choose the deficient vertex to be j; so in particular, 0 is the deficient vertex of B = B0.
Proof The set of base paths, B, and function, f, are produced as follows, considering two
cases in turn:
Case 1: n = 8m+ 1. Define
? = {bk = (4m?1?3k,1 +k,4m?2?3k) | 1 ? k < m},
? = {bk = (8m?3k,4m+k,8m?1?3k) | 0 ? k < m},
? = {(4m?1,1,4m?2)},and
B = ??? ??.
For each bk ? ?,f(bk) = 4m?3k; for each bk ? ?,f(bk) = 8m?2?3k; and for ?,f(b) = 5m.
To see that B is a set of base paths, note that:
11
(i) if bk ? ?, then bk contains edges of differences 4m ? 2 ? 4k and 4m ? 3 ? 4k for
1 ? k < m;
(ii) if bk ? ?, then bk contains edges of differences 4m?4k and 4m?1?4k for 0 ? k < m;
and
(iii) the path in ? contains edges of differences 4m?2 and 4m?3.
So D(B) = {1,2,...,4m} as required.
To see that f satisfies condition (2a), notice that:
(i) V(???) ? {1,2,...,4m?1}, and if v ? V(???) with v ? m+3, then v ? 4m?1 or
4m?2(mod 3), and
(ii) V(?) ? {4m,4m + 1,...,8m}, and if v ? V(?) with v ? 5m, then v ? 8m or 8m ?
1(mod 3).
So, since f(bk) ? 4m(mod 3) for each bk ? ?, f(bk) ? 8m + 1(mod 3) for each bk ? ?,
and f(b) = 5m for ? /? V(B), f satisfies condition (2a). To see that f satisfies condition
(2b), notice that:
(i) if bk ? ?, then N(bk) = {n?(4m?3k)?(4m?1?3k),n?(4m?3k)?(4m?2?3k)} =
{6k + 2,6k + 3} for 1 ? k < m;
(ii) if bk ? ?, then N(bk) = {n?(8m?2?3k)?(8m?3k),n?(8m?2?3k)?(8m?1?3k)} =
{6k + 4,6k + 5} for 1 ? k < m; and
(iii) if b ? ?, then N(b) = {n?5m?(4m?1),n?5m?(4m?2)} = {7m+ 3,7m+ 4}.
Since clearly no element of Zn occurs in two of the above sets, f satisfies condition (2b).
Case 2: n = 8m+ 5. Define
? = {bk = (4m+ 4?3k,k,4m+ 2?3k) | 1 ? k ? m},
12
? = {bk = (8m+ 5?3k,4m+ 2 +k,8m+ 3?3k) | 1 ? k ? m},
? = {(8m+ 3,4m+ 2,8m+ 4)},and
B = ??? ??.
For each bk ? ?,f(bk) = 4m + 3 ? 3k; for each bk ? ?,f(bi) = 8m + 4 ? 3k; and for
?,f(b) = m+ 1.
To see that B is a set of base paths, note that:
(i) if bk ? ?, then bk contains edges of differences 4m + 4 ? 4k and 4m + 2 ? 4k for
1 ? k < m;
(ii) if bk ? ?, then bk contains edges of differences 4m + 3 ? 4k and 4m + 1 ? 4k for
1 ? k < m; and
(iii) the path in ? contains edges of differences 4m+ 1 and 4m+ 2.
So D(B) = {1,2,...,4m+ 2} as required.
To see that f satisfies condition (2a), notice that:
(i) V(?) ? {1,2,...,4m + 1}, and if v ? V(?) with v ? m + 1, then v ? 4m + 4 or
4m+ 2(mod 3),
(ii) V(?) ? {4m + 3,4m + 4,...,8m+ 2}, and if v ? V(?) with v ? 5m + 3, then v ? 8m
or 8m+ 5(mod 3), and
(iii) V(?) ? {4m + 2,8m + 3,8m + 4}, and if v ? V(?), then v ? 4m + 2,8m, or 8m +
4(mod 3).
So, since f(bk) ? 4m + 3(mod 3) for each bk ? ?, f(bk) ? 8m + 4(mod 3) for each
bk ? ?, and f(b) = m + 1 for ?, f satisfies condition (2a). To see that f satisfies condition
(2b), notice that:
13
(i) if bk ? ?, then N(bk) = {n?(4m+3?3k)?(4m+4?3k),n?(4m+3?3k)?(4m+
2?3k)} = {6k ?2,6k} for 1 ? k ? m;
(ii) if bk ? ?, then N(bk) = {n?(8m+4?3k)?(8m+5?3k),n?(8m+4?3k)?(8m+
3?3k)} = {6k + 1,6k + 3} for 1 ? k ? m; and
(iii) if b ? ?, then N(b) = {n?(m+1)?(8m+3),n?(m+1)?(8m+4)} = {7m+5,7m+6}.
Since clearly no element of Zn occurs in two of the above sets, f satisfies condition (2b).
We now see how to use the base paths found in Lemma 4.1, finding C4-factors in K that
use each pure edge once and only a(a+1)p2 mixed edges.
The mixed difference from x to y of the mixed edge {(j,x),(k,y)} in K is defined to be
min{k ?j,a?k ?j}.
Corollary 4.1 Let p ? 0(mod 4) and a ? 1(mod 4). Let P(s,j) be the C4-factor of mixed
edges in K defined in the proof of Theorem 3.1. There exists a set S1 ? S = {(s,j)|s ?
Z?2(p?1)
2
,j ? Za} with |S1| = (a+1)2 such that there exists a C4-factorization of
K(a,p;1,0)+
?
? uniondisplay
(s,j)?S1
E(P(s,j))
?
?
containing a C4-factors.
Proof Let pi = {pis | s ? Z?2(p?1)
2
} be a C4-factorization of ?2Kp. Let B be the set of base 2-
paths in Ka with associated function f found in Lemma 4.1. Let B? = {b?k = (a?t,a?u,a?
v) | bk = (t,u,v) ? B} (reducing the sums modulo a) be another set of base paths (think
of these as ?upside-down versions? of the paths in B), and let f?(bk) = a ? f(b) (mod a).
14
Notice that for any fixed s ? Z?2(p?1)
2
, a C4-factor of K can be formed by:
C(s) = {((t,w),(u,w),(v,w),(f?(bk),x)),((a?t,x),(a?u,x),(a?v,x),(f(bk),y)),
((t,y),(u,y),(v,y),(f?(bk),z)),((a?t,z),(a?u,z),(a?v,z),(f(bk),w)),
((0,w),(0,x),(0,y),(0,z))| (w,x,y,z) ? pi,w < x,y,z,bk = (t,u,v) ? B};
properties 1) and 2a) of Lemma 4.1 ensure that the 4-cycles are all vertex disjoint.
Next, let C(s,i) be formed by adding i(mod a) to the first coordinate in each vertex in
each 4-cycle in C(s). C(s,i) is also a C4-factor of K. Since B is a set of base paths, the
pure edges in ?i?ZaC(s,i) are the edges in K(a,p;1,0) (that is, one copy of each pure edge
in K). Also, by Property 2b) of Lemma 4.1, for each (w,x,y,z) ? pi,w < x,y,z, the mixed
edges in ?i?ZaC(s,i) are precisely:
1. all the edges of mixed differences from w and x and from y and z in N(B)?{0}; and
2. all the edges of mixed differences from x and y and from z and w in {a ? j|j ?
N(B)?{0}}.
So setting S1 = {(s,j) | s ? Z?2(p?1)
2
,j ? N(B)?{0}}, this is precisely the set of edges in
uniondisplay
(s,j)?S1
P(s,j).
We now use Lemma 4.1 and Corollary 4.1 to construct a C4-factorization of K =
K(a,p;?1,?2) when a ? 1(mod 4) and ?1 is odd. We begin the construction by using
the Corollary to produce C4-factors using each pure edge only once, thereby effectively re-
ducing ?1 by one. The construction from Theorem 3.1 is adapted to partition the remaining
pure and mixed edges into C4-factors, producing the required C4-factorization.
15
Theorem 4.2 Suppose a ? 1(mod 4) and ?1 is odd. There exists a C4-factorization of
K = K(a,p;?1,?2) if:
1. p ? 0(mod 4),
2. ?2 is even and greater than zero, and
3. ?1 ? ?2a(p?1)?a.
Remark Conditions 1 and 2 are necessary, as is shown in Lemma 2.1.
Proof Assume that K satisfies conditions (1-3). For each s ? Z?2(p?1)
2
, j ? Za, and i ? Za,
let pi, S, P(s,j,i), P(s,j), and P?(s,j,r) be defined as in Theorem 3.1. Let S1 be defined
as in Corollary 4.1; so S1 ? S with |S1| = (a+1)2 .
By Corollary 4.1, there exists a C4-factorization, C, of
K(a,p;1,0)+
?
? uniondisplay
(s,j)?S1
E(P(s,j))
?
?.
So it remains to partition the edges of the subgraph
Kprime = K(a,p;?1 ?1,0)+
?
? uniondisplay
(s,j)?S\S1
E(P(s,j))
?
?
of K into C4-factors.
Since ?1 ?1 is even, it turns out that we can adapt the construction used in Theorem
3.1. By Condition 3, ?1 ? ?2a(p?1)?a, so ?1?12 ? ?2a(p?1)2 ? a+12 = |S|?|S1|. Therefore,
we can choose a set S2 ? S\S1 with |S2| = ?1?12 . Let S3 = S\(S1?S2). Then each element
in
{P?(s,j,r) | (s,j) ? S2,r ? Za}
16
induces a C4-factor, and the union of the edges in all a(?1?1)2 C4-factors contains each pure
edge 2|S2| = ?1 ?1 times, and uses precisely the mixed edges in
uniondisplay
(s,j)?S2
P(s,j).
Clearly the remaining edges can be partitioned into the following sets that induce the C4-
factors:
{P(s,j) | (s,j) ? S3}.
So, the required C4-factorization of K is defined by:
C ?{P?(s,j,r) | (s,j) ? S2,r ? Za}?{P(s,j) | (s,j) ? S3}.
Notice that the number of C4-factors is
a+a(?1 ?1)2 +
parenleftbigg?
2a(p?1)
2 ?
(a+ 1)
2 ?
(?1 ?1)
2
parenrightbigg
= ?2(p?1)2 + (?1 ?1)2
as required.
17
Chapter 5
?1 is Odd and Large
We now turn our attention to the construction that produces the factorization of K for
the largest values of ?1. The one exception that we encounter in the proof is when a = 9;
it is later shown that the techniques used in this proof do not allow us to produce the C4-
factorization of K = K(9,p;?1,?2) with a(p?1)?2 ?a < ?1 ? a(p?1)?2 ?1.
We need a special C4-factorization of ?Kp.
Lemma 5.1 [7] Suppose ? is even. There exists a C4-factorization of ?Kp:
{F0,0,F0,1,F0,2}?{Fi | 1 ? i ? ?(p?1)?3}
on the vertex set Z4x in which:
1. F0,0 = {(4i,4i+ 1,4i+ 2,4i+ 3) |i ? Zx},
2. F0,1 = {(4i,4i+ 2,4i+ 1,4i+ 3) |i ? Zx}, and
3. F0,2 = {(4i,4i+ 1,4i+ 3,4i+ 2) |i ? Zx}.
In Theorem 5.1 of the paper, we construct structures known as frames. Let M(b,n)
be the complete multipartite graph with b parts B0,...,Bb?1 of size n. A 4-cycle system of
M(b,n) is said to be a frame if the 4-cycles can be partitioned into sets S1,...,Sz such that
for 1 ? j ? z, Sj is a 2-factor of M(b,n)\Bi for some i ? Zb.
Lemma 5.2 There exists a frame of M(b,4) for all b ? 3.
18
Proof There are several constructions based on the parity of b. We begin with the case
where b is odd.
Case 1: b is odd
Let Fprime be a near 1-factorization on the vertex set Zb, and for each d ? Zb let Fprimed be the
near 1-factor in Fprime with deficiency d; so each vertex in Zb \{d} occurs in exactly one edge
in Fprimed.
Let K(Bx,By) be the complete simple bipartite graph on the parts Bx = {x}?Z4 and
By = {y}?Z4, 0 ? x < y ? b ? 1. For each {x,y} ? E(Fprimed), define a C4-factorization of
K(Bx,By), consisting of two C4-factors:
pix,y(0) = {((x,0),(y,0),(x,2),(y,2)),((x,1),(y,1),(x,3),(y,3))}
pix,y(1) = {((x,0),(y,1),(x,2),(y,3)),((x,1),(y,2),(x,3),(y,0))}
For each d ? Zb, let
Md =
uniondisplay
{x,y}?E(Fprimed)
K(Bx,By),
which has a C4-factorization, Pd, consisting of the two C4-factors:
Md(j) =
uniondisplay
{x,y}?E(Fprimed)
pix,y(j) for each j ? Z2.
Notice that
M(b,4) =
uniondisplay
d?Zb
Md,
each edge of which therefore occurs in exactly one cycle in
uniondisplay
d?Zb
j?Z2
Md(j).
19
Notice also that each Md(j) is a 2-factor of M(b,4)\({d}?Z4) so the 4-cycles in
P(b) =
uniondisplay
d?Zb
Pd,
form a frame of M(b,4).
40 1 2 3
Figure 5.1: Example of a 2-factor, M0(j).
Case 2: b is even
There are two cases based on if b ? 0 or 2 (mod 4).
DefineC = {(c0(i),c1(i),...,cb?2(i)) | i ? Zb,cb?2(i) = ?,cj(i) = i+(?1)j+1 ceilingleftj/2ceilingrightfor 0 ?
j ? b ? 3} ? {(0,1,...,b ? 2)} to be a (b ? 1)-cycle system of 2Kb on the vertex set
V = Zb?1 ? {?}. Let cprime = (0,1,...,b ? 2). For each d ? V, let Cd be the cycle with
deficiency d.
Case 2.1: b ? 0 (mod 4)
For each c = (c0,c1,...,cb?2) ? C \{cprime}, say c = Cd, and for each j ? Z2, define a C4-
factor, P(c,j), of (V ?Z4)\({d}?Z4) as follows (with the first subscripts reduced modulo
(b?1) and the second subscripts reduced modulo 4):
P(c,j) = {((ci,2j+(1+(?1)i+1)),(ci+1,2j+(1+(?1)i+1)),(ci,1+2j+(1+(?1)i+1)),(ci+1,1+
2j + (1 + (?1)i+1))) | ? 1 ? i ? b2 ? 2} ? {((ci,2j + 2),(ci+1,2j),(ci,2j + 3),(ci+1,2j +
1)) | b2 ?1 ? i ? b?3}.
20
Also, for each j ? Z2, define a C4-factor, P(c,j), of (V ?Z4) \ ({?}?Z4) as follows
(with the first subscripts reduced modulo (b?1) and the second subscripts reduced modulo 4):
P(cprime,j) = {((i,2j),(i+ 1,2j + 2),(i,2j + 1),(i+ 1,2j + 3)) | i ? Zb?1}.
Notice that for each c ? C and each j ? Z2, P(c,j) is a 2-factor of M(b,4)\({d}?Z4)
where c = Cd so the 4-cycles in
uniondisplay
c?Cj?Z
2
P(c,j)
form a frame of M(b,4).
Case 2.2: b ? 2 (mod 4)
In the case where b ? 2 (mod 4), there are two constructions for the 2-factors. For
each c = (c0,c1,...,cb?2) ? C \{cprime}, say c = Cd, define two C4-factors, P0(c) and P1(c), of
(V ?Z4) \ ({d}?Z4) as follows (with the first subscripts reduced modulo (b? 1) and the
second subscripts reduced modulo 4):
1. P0(c) = {((ci,1+(?1)i+1),(ci+1,1+(?1)i+1),(ci,2+(?1)i+1),(ci+1,2+(?1)i+1)) | ?2 ?
i ? b2 ?2} ? {((ci,0),(ci+1,2),(ci,1),(ci+1,3)) | b2 ?1 ? i ? b?3}, and
2. P1(c) = {((ci,3+(?1)i+1),(ci+1,3+(?1)i+1),(ci,4+(?1)i+1),(ci+1,4+(?1)i+1)) | 0 ?
i ? b2 ?2} ? {((ci,2),(ci+1,0),(ci,3),(ci+1,1)) | b2 ?1 ? i ? b?2}
Also, for each j ? Z2, define a C4-factor, P(c,j), of (Zb ?Z4) \ ({?}?Z4) as follows
(with the first subscripts reduced modulo (b?1) and the second subscripts reduced modulo 4):
P(cprimej) = {((i,2j),(i+ 1,2j + 2),(i,2j + 1),(i+ 1,2j + 3)) | i ? Zb?1}.
21
Notice that for each c ? C and each j ? Z2, Pj(c) and P(c,j) are 2-factors of M(b,4)\
({d}?Z4) where c = Cd so the 4-cycles in
uniondisplay
c?Cj?Z
2
Pj(c)?P(c,j)
form a frame of M(b,4).
Theorem 5.1 Suppose a ? 1(mod 4),a negationslash= 9, and ?1 is odd. There exists a C4-factorization
of K(a,p;?1,?2) if and only if:
1. p ? 0(mod 4),
2. ?2 > 0 and is even, and
3. ?1 ? a(p?1)?2 ?1.
Proof The necessity of these conditions is proved in Lemmas 2.1 and 2.2, so now assume
that Conditions (1-3) are true.
If ?1 ? a(p ? 1)?2 ? a, then by Theorem 4.2 there exists a C4-factorization of K =
K (a,p;?1,?2). In this proof, we provide aconstruction that finds the required C4-factorization
whenever ?1 ? (a?2). Notice that the result will follow because a(p?1)?2 ?a ? (a?2)
since ?2 ? 2 and p ? 4. So now it suffices to assume that (a?2) ? ?1 ? a(p?1)?2 ?1. We
now construct a C4-factorization of K (a,p;?1,?2) in these cases.
We begin by showing that if the theorem is true when p = 4, then it is true for all p ? 8
with p ? 0 (mod 4). Let ?1 = l0 +l1 +???+l(?2(p?1)/2)?3 satisfying:
(a) l0 ? 6a?1 and is odd, and
(b) lj ? 2a and is even for 1 ? j ? (?2(p?1)/2)?3.
22
We begin by using Lemma 5.1 with ? = ?2. Notice that ?i?Z3F0,i is the union of
p/4 disjoint copies of 2K4. For each j ? Zp/4, let (Za ?{4j,4j + 1,4j + 2,4j + 3},Ti) be
a C4-factorization of K(a,4;l0,2), which we are currently assuming exists since it satisfies
Condition 3. Then clearly taking the union forallj ? Zp/4 of these C4-factorizations produces
a C4-factorization, (Za ?Zp,Tprime0), of l0Ka ? ?i?Z3F0,i.
For each i ? Z?2(p?1)/2?3\{0}, let (Za?Zp,Tprimei) be a C4-factorization of liKa ? Fi, which
exists by Theorem 3.1. Then
(Za ?Zp,?i?Z?2(p?1)/2?3Tprimei)
is a C4-factorization of K(a,p;?1,?2).
So we now assume that p = 4. As stated before, since ?1 is odd, some of the C4-factors
must be inefficient; these are produced first. We begin by considering the subgraph of K
with ?1 = 3. Let b = 14(a?1). Partition the vertices in Za\{0} into sets B = {B0,...,Bb?1},
each of size 4, where Bi = {4i+ 1,4i+ 2,4i+ 3,4i+ 4} for each i ? Zb.
Let M(B) = M(b,4) be the complete simple multipartite graph with parts being the
sets in B. In order to complete the factorization, we need a frame of M(B), which exists by
Lemma 5.2. In the frame of M(B) constructed in Lemma 5.2, notice that for each d ? Zb,
there are exactly two C4-factors, say Md,k for k ? Z2, on the vertex set Za \(Bd ?{0}). To
produce the inefficient C4-factors of K, we will use each Md,k twice.
Remark In order to produce a frame of M(b,4) using Lemma 5.2, b must be greater than
or equal to three. When a = 9, b = 2, and there is no frame of M(2,4); therefore, we must
currently exclude a = 9 from the theorem. However, when a = 9, we have previously shown
in Theorem 3.1 that if ?1 ? a(p?1)?2 ?a, then there exists a C4-factorization of K.
Using the frames of M(B), we can produce the minimum number of inefficient C4-factors
in K required by the necessary condition. All other inefficient C4-factors in our constructions
23
contain only mixed edges, and occur only when ?1 < a(p ? 1)?2 ? 1. If a C4-factor of K
contains only mixed edges, we call it a mixed-C4-factor.
Recall that we are now assuming that p = 4. For each i ? Zb and j ? Z4, let Bi,j =
Bi?{j}. For each j ? Z4, let M(j) be the complete multipartite graph with parts {Bi,j | i ?
Zb}, and let Md,k(j) be the natural isomorphic copy of the C4-factor Md,k on the vertex set
(Za \(Bd ?{0}))?{j}.
For each d ? Zb and k ? Z2, we form four inefficient C4-factors of Kprime = K(a,4;3,2) on
the vertex set Za ?Z4 as follows (reducing sums in the second subscript modulo 4):
pi2k+1(d) = {((4d+ 1,j +k),(0,j +k),(4d+ 4,j +k),(0,j +k + 1)) | j ? {0,2}}
? ((4d+ 2,k),(4d+ 3,k),(4d+ 2,k + 2),(4d+ 3,k + 2))
? {((4d+ 1,j +k),(4d+ 3,j +k),(4d+ 2,j +k),(4d+ 4,j +k)) | j ? {1,3}}
? {Md,k(j) | j ? Z4}, and
pi2k+2(d) = {((4d+ 1,j +k),(0,j +k),(4d+ 4,j +k),(0,j +k ?1)) | j ? {0,2}}
? ((4d+ 2,k),(4d+ 3,k),(4d+ 2,k + 2),(4d+ 3,k + 2))
? {((4d+ 1,j +k),(4d+ 2,j +k),(4d+ 4,j +k),(4d+ 3,j +k)) | j ? {k + 1,k + 3}}
? {Md,k(j) | j ? Z4}.
Let P? = {pi2j+1(i),pi2j+2(i) | i ? Zb,j ? Z2} be the set of these 4b inefficient C4-factors.
Let E(P?) be the set of edges of the sets of 4-cycles in P?. Let K? be the graph induced
by the edge-set E(P?); then K? is a subgraph of Kprime. For each j ? Z4, let W(j) be the pure
24
12
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
0
Figure 5.2: Example of an inefficient C4-factor.
edges in Kprime\E(K?) induced by the vertex set Za ?{j} (see Figure 5.3). In K?, clearly each
vertex has degree 8b since its edges can be partitioned into 4b C4-factors. More specifically,
for each j ? Z4 the pure degree of v in K? is
d(v) =
??
?
??
4b = a?1 if v = (0,j), and
8b?2 = 2(a?1) otherwise
(1)
and the mixed degree of v is
d(v) =
?
??
??
4b = a?1 if v = (0,j), and
2 otherwise.
(2)
We would like to supplement P? with some efficient C4-factors that equalize the pure
and mixed degrees of all the vertices in K? to (a?1)(a?2) and a?1 = 4b respectively while
using precisely the mixed edges of the broken differences; that is, broken in the sense that
some edges of these differences are already used in E(P?). Let A be the multiset of mixed
edges of differences {4i + 1,4i + 4 | i ? Zb} in which each mixed edge of those differences
occurs twice. So all the mixed edges in E(P?) are in A.
25
(2,j)
K4,4 between each BiK4,4
K4,4
(1,j)
(4i + 1,j)
(4i + 2,j)
(4i + 3,j)
(4i + 4,j)
(0,j)
(4,j)
(3,j)
Figure 5.3: W(j)
To equalize the pure and mixed degree of the vertices will also require using the re-
maining edges in Kprime \ E(K?) and an additional (a ? 5)Ka on the vertex set Za ? {j} for
each j ? Z4; the following three paragraphs indicate why one might expect this approach
to be possible. It is worth reiterating now that the number of inefficient C4-factors we have
already constructed was carefully chosen so that if ?1 is as large as condition (3) allows, then
all remaining C4-factors must be efficient. It is also worth noting that this is why we require
?1 ? (a?5) + 3 = (a?2) in this proof.
Notice that for each j ? Z4, the remaining pure edges in the jth part in K \ E(K?),
namely the edges in W(j), consist of the 8b(b ? 1) edges of the complete multipartite
graph M(B) and the 16b edges in the 4-cycles C(i,j) = {((0,j),(4i+1,j),(4i+ 4,j),(4i+
3,j)),((0,j),(4i+2,j),(4i+4,j),(4i+3,j)),((0,j),(4i+2,j),(4i+1,j),(4i+4,j)),((0,j),(4i+
2,j),(4i+ 1,j),(4i+ 3,j))} for each i ? Zb.
26
In order to raise the mixed degree of the a?1 vertices v ? {(1,j),...,(a?1,j) | j ? Z4}
from 2 (see (2)) to a ? 1 = 4b in the most efficient fashion (that is, to be used in efficient
C4-factors), each such v must be in 12(a ? 3) C4-factors in which v is the only vertex in
the jth part that is in a mixed edge 4-cycle. (Notice that (0,j) is excluded since it already
has mixed degree a?1 = 4b.) So the number of C4-factors needed to to accomplish this is
1
2(a?1)(a?3). Clearly if we proceed in this way then the mixed degree of v = (0,j) is not
raised for all j ? Z4 since each C4-factor is required to be efficient.
Since in each of these C4-factors v = (0,j) must be incident with only pure edges,
(0,j) must be incident with (a ? 1)(a ? 3) pure edges. In W(j), (0,j) is incident with
8b = 2(a ? 1) pure edges. So (a ? 1)(a ? 5) more pure edges incident with (0,j) are
needed. This can be achieved by adding (a?5)Ka with vertex set Za ?{j} to W(j). So let
W+(j) = W(j)?(a?5)Ka.
As a check on this construction, one might ask the following questions. With how
many pure edges must v ? {(1,j),...,(a ? 1,j) | j ? Z4} be incident in order to complete
the C4-factors that raise the mixed degree of v to a ? 1? Among the previously described
1
2(a ? 1)(a ? 3) C4-factors, each of the a ? 1 choices for v must be incident with no pure
edges in exactly 12(a?3) of the C4-factors, implying v must be incident with a?3 fewer pure
edges than (0,j). With how many pure edges are vertices v ? {(1,j),...,(a?1,j) | j ? Z4}
incident in W+(j)? They are each incident with (a?2)(a?3) pure edges, which is exactly
a?3 fewer than (a?1)(a?3).
We next partition the edges in uniontextj?Z4 W+(j) together with a set, M+, of 12(a?1)(a?3)
mixed 4-cycles into efficient C4-factors. The edges in uniontextj?Z4 W+(j) are partitioned into sets
that induce pure near C4-factors in Lemma 5.3. The interested reader can skip to there now,
but it also can be saved for later reading.
The precise set, M+, of 12(a?1)(a?3) mixed 4-cycles used are described now. Notice
that the only requirements we need to enforce are that each vertex (i,j) with i ? Za \{0}
and j ? Z4 occurs in exactly 12(a ? 3) of these mixed 4-cycles, and that the edges they
27
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
Figure 5.4: C with a = 13
contain all come from the edges of differences broken when forming P?. Then each of the
1
2(a?3) mixed 4-cycles on the vertex set say {(i(j),j) | j ? Z4} can be added to a pure near
C4-factor with deficiency (i(j),j) for each j ? Z4 to form a C4-factor of K.
The mixed edges of the broken differences that have already been used in the 4b inef-
ficient C4-factors in P?, and hence contained in A, can be described by the following two
multisets:
(1) E(C), where C = {((0,j),(4i+ 1,j + 1),(0,j + 2),(4i + 1,j + 3)),((0,j),(4i+ 4,j +
1),(0,j + 2),(4i+ 4,j + 3)) | i ? Zb,j ? Z2}, and
(2) D = {{(4i + 2,j),(4i + 3,j + 2)},{(4i+ 2,j),(4i + 3,j + 2)},{(4i+ 3,j),(4i+ 2,j +
2)},{(4i+ 3,j),(4i+ 2,j + 2)} | i ? Zb,j ? Z2}.
Then in the subgraph induced by E(C),
d(v) =
?
???
??
???
?
4b if v = (0,j),
2 if v ? {(4i+ 1,j),(4i+ 4,j) | i ? Zb,j ? Z4}, and
0 otherwise,
28
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
Figure 5.5: D with a = 13
and in the subgraph induced by D
d(v) =
?
??
??
2 if v ? {(4i+ 2,j),(4i+ 3,j) | i ? Zb,j ? Z4}, and
0 otherwise.
We now define three sets of 4-cycles, R1,R2, and L such that each mixed edge in A will
be used exactly once in E(C) ? D ?E(R1) ? E(R2) ?E(L). The edges in these three sets
of cycles will be recombined with the near C4-factors of W+(j) into 4-cycles that can be
partitioned into 4b mixed C4-factors and 12(a?3) efficient C4-factors of K.
In forming R1, we need to avoid the edges in C already used in the inefficent C4-factors;
this is done by disallowing values of i and j such that i+j = 0.
(1) R1 = {((i,0),(i+j,1),(i,2),(i+j,3)) | i ? Za\{0},j ? {4x+1,4x+4 | x ? Zb},i+j negationslash=
0}.
In forming R2, we need to avoid the edges in D already used in the inefficent C4-factors;
this is reflected in the values of (i,j) disallowed in the following set.
29
(2) R2 = {((i,0),(i + j,2),(i,1),(i + j,3)),((i,0),(i + j,2),(i,3),(i + j,1)) | i ? Za,j ?
{?1,1},(i,j) /? {(4x+2,1),(4x+3,?1) | x ? Zb}}?{((4x+2,j),(4x+3,j+1),(4x+
2,j + 2),(4x+ 3,j + 3)) | x ? Zb,j ? Z2}, and
(3) L = {((i,0),(i + j,2),(i,1),(i + j,3)),((i,0),(i + j,2),(i,3),(i + j,1)) | i ? Za,j ?
{4x+ 1,4x+ 4 | x ? Zb}\{?1,1}}.
Each of the 2b ? 2 values of j in L produce two mixed C4-factors of K, so this forms
4b? 4 of the 4b mixed C4-factors claimed to exist. It is worth noting again that the edges
in E(C)?D?E(R1)?E(R2)?E(L) use all the mixed edges in A exactly once as Table 5.1
indicates.
Difference Incident with 0 Between levels Between parts Otherwise
4x+ 2 and 4x+ 3 j and j + 1
?1,1 C,R2 R1,R2 R1,R2 R1,R2
4x + 1,x negationslash= 0 C,L No such edges exist R,L L,L
4x+ 4,x negationslash= b C,L No such edges exist R,L L,L
Table 5.1: Locations of Mixed Edges in A
The edges of R = R1?R2 will now be partitioned in a different way into two sets. First
notice the degree of each vertex in the subgraph induced by the edges of E(R1) and E(R2).
In the subgraph induced by E(R1),
d(v) =
?
???
??
???
??
0 if v = (0,j),
a?3 if v ? {(4i+ 1,j),(4i+ 4,j) | i ? Zb,j ? Z4}, and
a?1 if v ? {(4i+ 2,j),(4i+ 3,j) | i ? Zb,j ? Z4},
and in the subgraph induced by E(R2),
d(v) =
?
??
??
6 if v ? {(4i+ 2,j),(4i+ 3,j) | i ? Zb,j ? Z4}, and
8 otherwise.
30
We remove a 2-regular subgraph on the vertex set {(4i+2,j),(4i+3,j) | i ? Zb,j ? Z4}
of the subgraph induced by E(R1) and add it to the subgraph induced by E(R2) in such a
way that we have
(1) a graph R? on the vertex set (Za \{0})?Z4 that is (a?3)-regular and whose edges
can be partitioned into 12(a?3) 4-cycles, and
(2) a graphR?2 on the vertex setZa?Z4 that is 8-regularand whose edges can be partitioned
into 4-cycles, which can be partitioned into four mixed C4-factors.
Let R?1 be the graph induced by E(R1). To form R? from R?1, first remove the mixed
edges that occur in the following subset of 4-cycles in R1: R1,1 = {((4i+2,0),(4x+2,1),(4i+
2,2),(4x+2,3)),((4i+3,0),(4x+3,1),(4i+3,2),(4x+3,3))| i,x ? Zb,i negationslash= x}. The degree of
each vertex in the subgraph, R?1,1, induced by E(R1,1) is 2(b?1) = 2(14(a?1)?1) = 12(a?1)?2.
Notice that each 4-cycle in R1,1 is a 4-cycle in R1.
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
Figure 5.6: The 4-cycles of R1,1 incident with vertices {4i+2 | i ? Zb}; the other half of R1,1
is formed by moving each cycle ?down? one level in each part.
Observe the degree of each vertex in R?1 ?R?1,1 is
31
d(v) =
?
???
??
???
?
0 if v = (0,j),
a?3 if v ? {(4i+ 1,j),(4i+ 4,j) | i ? Zb,j ? Z4}, and
a?1?2(b?1) if v ? {(4i+ 2,j),(4i+ 3,j) | i ? Zb,j ? Z4}.
Therefore, we must add back to R?1 ? R?1,1 a 2(b ? 2)-regular subgraph, T?1, of R?1,1 on the
vertex set v ? {(4i+ 2,j),(4i+ 3,j) | i ? Zb,j ? Z4} to complete the formation of R?.
Let [x]b denote the integer m ? Zb with m ? x (mod b). We now form two sets of
4-cycles, T1 and T2, whose edges partition E(R1,1). The set of 4-cycles in T1 is constructed
based on the parity of b:
Case 1: b is odd
T1 = {((4[i?k]b + 2,0),(4i+2,1),(4[i+k]b +2,2),(4i+2,3)),((4[i?k]b + 3,0),(4i+
3,1),(4[i+k]b + 3,2),(4i+ 3,3)) | i ? Zb, k ? 2,...,b?1}.
Case 2: b is even
T1 = {((4[i+k]b+2,0),(4i+2,1),(4[i+k+1]b+2,2),(4i+2,3)),((4[i+k]b+3,0),(4i+
3,1),(4[i+k +1]b +3,2),(4i+3,3)) | i ? Zb, k ? 2,...,b?1, k is even}?{((4[i+k?2]b +
2,0),(4i+ 2,1),(4[i+k ?1]b + 2,2),(4i+ 2,3)),((4[i+k ?2]b +3,0),(4i+ 3,1),(4[i+k ?
1]b + 3,2),(4i+ 3,3)) | i ? Zb, k ? 2,...,b?1, k is odd}.
The set T2 does not depend on the parity of b:
T2 = {((4i+2,1),(4[i?k]b +2,0),(4i+2,3),(4[i+k]b +2,2)),((4i+3,1),(4[i?k]b +
3,0),(4i+ 3,3),(4[i+k]b + 3,2)) | i ? Zb, k = 1}.
Notice that the subgraph, T?1, induced by E(T1) is 2(b ? 2)-regular on the vertices
{4i+2,4i+3 | i ? Zb}. Add the edges of T1 to the graph R?1 ?R?1,1 to form R?. Then in R?
each vertex v has degree:
d(v) =
??
???
?
???
??
0 if v = (0,j),
a?3 if v ? {(4i+ 1,j),(4i+ 4,j) | i ? Zb,j ? Z4}, and
a?3 if v ? {(4i+ 2,j),(4i+ 3,j) | i ? Zb,j ? Z4}.
So let R? = R?1 ? R?1,1 + T?1. The edges of R? consist of the edges of the 4-cycles in
R1 \R1,1 and the edges in the 4-cycles of T1; therefore, the edges of R? can be partitioned
32
16
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
13
14
15
(a) T1 with k = 2.
16
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
13
14
15
(b) T1 with k = 3
Figure 5.7: The 4-cycles of T1 incident with vertices {4i+2 | i ? Zb}; the other half of T1 is
formed by moving each cycle ?down? one level in each part.
into 4-cycles. Let M+ = (R1 \R1,1)?T1 be the set of these 4-cycles that partition the edges
of R?.
Notice that the graph, T?2 induced by E(T2) is 2-regular on the vertices {4i+2,4i+3 | i ?
Zb}. Let R?2 be the graph induced by E(R2) ? E(T2), which is 8-regular on the vertex set
Za ?Z4. R?2 can be partitioned into the following four C4-factors:
1. Begin with R2,1 = {((i,0),(i + 1,2),(i,1),(i + 1,3)) | i ? Za}, which is a C4-factor.
The edges in cycles in R2,1 that are not in edges in cycles in R2 are precisely the edges
in S?1 = {{(4x + 2,0),(4x + 3,2)},{(4x + 2,1),(4x + 3,3)} | x ? Zb}. Remove the
edges in S?1 from the cycles in R2,1 and replace them with the edges in the subset of
T2: S+1 = {{(4x + 2,1),(4[x ? 1]b + 2,0)},{(4x + 3,3),(4[x + 1]b + 3,2)} | x ? Zb}.
Then the edges of pi1 = (R2,1 \S?1 )?S+1 induce a mixed C4-factor.
33
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
Figure 5.8: T2 with a = 13
2. Begin with R2,2 = {((i,0),(i + 1,2),(i,3),(i + 1,1)) | i ? Za}, which is a C4-factor.
The edges in cycles in R2,2 that are not in edges in cycles in R2 are precisely the edges
in S?2 = {{(4x + 2,0),(4x + 3,2)},{(4x + 2,3),(4x + 3,1)} | x ? Zb}. Remove the
edges in S?2 from the cycles in R2,2 and replace them with the edges in the subset of
T2: S+2 = {{(4x + 2,0),(4[x + 1]b + 2,3)},{(4x + 3,1),(4[x + 1]b + 3,2)} | x ? Zb}.
Then the edges of pi2 = (R2,2 \S?2 )?S+2 induce a mixed C4-factor.
3. Begin with R2,3 = {((i,0),(i ? 1,2),(i,1),(i ? 1,3)) | i ? Za}, which is a C4-factor.
The edges in cycles in R2,3 that are not in edges in cycles in R2 are precisely the edges
in S?3 = {{(4x + 2,2),(4x + 3,0)},{(4x + 2,3),(4x + 3,1)} | x ? Zb}. Remove the
edges in S?3 from the cycles in R2,3 and replace them with the edges in the subset of
T2: S+3 = {{(4x + 2,3),(4[x + 1]b + 2,2)},{(4x + 3,0),(4[x + 1]b + 3,1)} | x ? Zb}.
Then the edges of pi3 = (R2,3 \S?3 )?S+3 induce a mixed C4-factor.
4. Begin with R2,4 = {((i,0),(i ? 1,2),(i,3),(i ? 1,3)) | i ? Za}, which is a C4-factor.
The edges in cycles in R2,4 that are not in edges in cycles in R2 are precisely the edges
34
in S?4 = {{(4x + 2,1),(4x + 3,3)},{(4x + 2,2),(4x + 3,0)} | x ? Zb}. Remove the
edges in S?4 from the cycles in R2,4 and replace them with the edges in the subset of
T2: S+4 = {{(4x + 2,1),(4[x + 1]b + 2,2)},{(4x + 3,0),(4[x + 1]b + 3,3)} | x ? Zb}.
Then the edges of pi4 = (R2,4 \S?4 )?S+4 induce a mixed C4-factor.
We can now supplement the C4-factors of P? in order to equalize the pure and mixed
degrees of the vertices on the vertex set Za ?Z4 while using mixed edges in A. Notice that:
by Lemma 5.3, each vertex (i,j) with i negationslash= 0 is deficient in a?32 pure near C4-factors; and
since R? is (a?3)-regular, each such vertex is in a?32 mixed 4-cycles in M+. For each mixed
4-cycle m ? M+, let pi+(m) be the efficient C4-factor on the vertex set Za ?Z4 comprised of
a near C4-factor of W+(j), with deficiency being the vertex in m that is in Za?{j} for each
j ? Z4, and the mixed 4-cycle m ? M+. Let P+ = {pi+(m) | m ? M+} be set of efficient
C4-factors induced by the graph with edge-set E(W+(j)) +E(M+) for each j ? Z4.
Notice that now the subgraph induced by E(P?) + E(P+) of K is 16b2-regular on
the vertex set Za ? Z4, which can be partitioned into C4-factors of K. This gives a C4-
factorization, P, of K(a,4;(a?2),0)+(E(C)?D?E(R?1)). So it remains to partition the
edges of K(a,4;?1 ?(a?2),0) +K(a,4;0,?2)?(E(C)?D ?E(R?1)) into C4-factors.
Since ?1 ?(a?2) is even, it turns out that we can adapt the construction in Theorem
3.1. By Condition 3 with p = 4, ?1 ? 3a?2 ?1, so ?1?(a?2)2 ? 3a?22 ? (a?1)2 . Once we produce
3a?2
2 ?
(a?1)
2 mixed C4-factors from the remaining mixed edges, then we produce the needed
C4-factorization.
Let Aprime be the subset of all the mixed edges formed by removing 2 copies of each of the
edges joining vertices x levels apart for each x ? {4i + 1,4i + 4 | i ? Zb}. The mixed edges
of Aprime may be partitioned into mixed C4-factors, P(s,j), of K as defined in Theorem 3.1.
The number of such C4-factors is |Aprime|ap = 3
parenleftBig
a+1
2 +
a(?2?2)
2
parenrightBig
. The edges of L and R?2 can be
partitioned into a ? 5 + 4 = a? 1 mixed C4-factors. So combining both of these produces
35
3
parenleftBig
a+1
2 +
a(?2?2)
2
parenrightBig
+(a?1) = 3a?22 ? (a?1)2 mixed C4-factors, say P(m) for m ? Z(3a?2
2 ?
(a?1)
2 )
as required.
Now we can partition the edges of K(a,4;?1 ? (a ? 2),0) + K(a,4;0,?2) ? (E(C) ?
D ? E(R?)) into C4-factors as follows. Since ?1 ? (a ? 2) is even, we can produce a near
C4-factorization, Cj = {cj(1),...,cj(a2(?1 ? (a ? 2)))} on the vertex set Za ? {j} for each
j ? Z4 consisting of a2(?1 ? (a ? 2)) near C4-factors. By Condition 3, ?1 ? 3a?2 ? 1, so
?1?(a?2)
2 ?
3a?2
2 ?
(a?1)
2 , so for 1 ? i ?
?1?(a?2)
2 and for each cycle c ? P(i), we can extend c
to a C4-factor by adding it to four near C4-factors, one from each Cj, j ? Z4 that are each
vertex disjoint from c.
Thus, we have a C4-factorization of K(a,4;?1 ? (a ? 2),0) + K(a,4;0,?2) ? (E(C) ?
D ?E(R?)); therefore, we have a C4-factorization of K(a,4;?1,?2).
The following lemma is used in the proof of Theorem 5.1, so all notation is adopted
from there. Although the parameter j could be omitted in this lemma, it retained so the
notation here matches exactly with the notation of Theorem 5.1.
Lemma 5.3 Let a ? 13 be odd, j ? Z4. Then W+(j) = W(j)?(a?5)Ka can be decomposed
into 12(a?1)(a?3) near C4-factors such that each v ? {(1,j),...,(a?1,j)} is deficient exactly
1
2(a?3) times and v = (0,j) is never deficient.
Proof Notice that for each i ? Zb and j ? Z4, the 4-cycles in C(i,j) exhaust all the edges
in Bi,j and all the edges joining vertices in Bi,j to (0,j) in the graph W(j).
Let C1(i,j) be a 4-cycle system of (a ?5)K5 defined on the vertex set Bi,j ?{0} that
contains a set, C0(i,j), of 12(a?5) copies of the 4-cycle ((4i+1,j),(4i+2,j),(4i+3,j),(4i+
4,j)). This can be done by taking 12(a?5) copies of a 4-cycle system of 2K5, in which case:
each 4-cycle in C1(i,j)\C0(i,j) contains the vertex (0,j).
36
We must use (a?4) copies of a frame of M(B) to complete the decomposition; let Md,k
be defined as before.
For each i ? Zb, pair all but two of the 4-cycles in (C1(i,j)\C0(i,j))?C(i,j) with the
4-cycles in a C4-factor, Md,k, to form a near C4-factor of W+(j) (See Figure 5.9). This is
possible since |C1(i,j)|?|C0(i,j)|+|C(i,j)|?2 = 52(a?5)? 12(a?5) + 4?2 = 2(a?4),
which is the number of C4-factors on the vertex set (Za \(Bi ?{0}))?{j} in (a?4) copies
of the frame of M(B).
(4x + 1,j) (4i + 4, j)
(4i + 3, j)
(4i + 2, j)
(4i + 1, j)
(d,j)
(0,j)
(1, j)
(2, j) (3,j)
(4x + 2,j)
(4x + 4,j)
(4x + 3,j)
Figure 5.9: Near C4-factor of W+(j)
For each i ? Zb, form 2 C4-factors of W+(j) consiting of the following 4-cycles (See
Figure 5.10):
(a) one of the two remaining 4-cycles in (C1(i,j)\C0(i,j))?C(i,j), and
(b) for each d ? Zb \{i}, one of the 4-cycles in C0(d,j).
Notice that the number of 4-cycles used in (b) in each block Bi,j is 2(b?1) = |C0(d,j)|.
The total number of C4-factors produced this way is 2b = 12(a?1).
Notice that 12(a?1)(a?4)+ 12(a?1) = 12(a?1)(a?3) as required, and that each vertex
is deficient exactly once in the 4-cycles in the 2K5-4-cycle-decompostion so that each vertex
in a 4-cycle in C0(i,j) is deficient exactly 12(a?5) times. Also, each vertex is deficient once
37
(4x + 4, j)
(d,j)
(4i + 1,j)
(4i + 2,j)
(4i + 3,j)
(4i + 4,j)
(0, j)
(3, j)(2, j)
(1, j)
(4x + 3, j)
(4x + 2, j)
(4x + 1, j)
Figure 5.10: Near C4-factor of W+(j)
in C(i,j); therefore, in total, each vertex is deficient 12(a?5)+1 = 12(a?3) times, and v = 0
is never deficient.
38
Bibliography
[1] R.C. Bose and T. Shimamoto, Classification and analysis of partially balanced incom-
plete block designs with two associate classes, Journal of the American Statistical Asso-
ciation, 47 (1952), 151?184.
[2] E.J. Billington and C.A. Rodger, Resolvable 4-cycle group divisible designs with two
associate classes: part size even, Discrete Math, 308 (2008), 303?307.
[3] J. Burling and K. Heinrich, Near 2-factorizations of 2K2n+1: cycles of even length,
Graphs and Combinatorics, 5 (1989), 213?221.
[4] H. L. Fu, C. A. Rodger, and D. G. Sarvate, The existence of group divisible designs with
first and second associates, having block size 3, Ars Combin., 54 (2000), 33?50.
[5] H. L. Fu and C. A. Rodger, 4-cycle group-divisible designs with two associate classes,
Combin. Probab. Comput., 10 (2001), 317?343.
[6] H. L. Fu and C. A. Rodger, Group divisible designs with two associate classes: n = 2
or m = 2, J. Combin. Theory, 83 (1998), 94?117.
[7] S. Hamm and K. Heinrich, Resolvable and near-resolvable decompositions of DKv into
oriented 4-cycles, Aequationes Mathematicae, 44 (1992), 304?316.
39