Path and Cycle Decompositions
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 classified information.
Chandra Dinavahi
Certificate of Approval:
Curt Lindner
Distinguished University Professor
Mathematics and Statistics
Chris Rodger, Chair
Scharnagel Professor
Mathematics and Statistics
Dean Hoffman
Professor
Mathematics and Statistics
George T. Flowers
Interim Dean
Graduate School
Path and Cycle Decompositions
Chandra Dinavahi
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
August 9, 2008
Path and Cycle Decompositions
Chandra Dinavahi
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
Chandramouli Dinavahi, son of Venkatarao and Ramanamma, was born on Septenber
29, 1977. He entered Hyderabad Central University in 1998 and received Master of Sci-
ence degree (Mathematics and Computing) in 2000. He completed his graduate study and
received a Master of Science degree in Mathematics from Texas A&M University, College
Station, in January 2004. In August 2004, he entered the Graduate School at Auburn Uni-
versity, Auburn, Alabama for a Doctor of Philosophy in Mathematics. In December 2005,
he Wed Anupama.
iv
Dissertation Abstract
Path and Cycle Decompositions
Chandra Dinavahi
Doctor of Philosophy, August 9, 2008
(M.S., Texas AM University?College Station, 2003)
(M.S.C., University of Hyderabad, 2001)
60 Typed Pages
Directed by Chris Rodger
A G-design is a partition of edge set of Kv in which each element induces a copy of
G. The existence of G-designs with the additional property that they contain no proper
subsystems has been previously settled when G ? {K3,K4 ? e} by Rodger and Spicer.
In this dissertation, we first solved the problem of G-designs with no subsystems where
G = P3, considering the problem for both designs and maximum packings with non-empty
leaves. We then completely settled the problem for the general case of Pm-designs which
contain no proper subsystems for every value of m and v.
We also solved another problem. A 4-cycle system is said to be diagonally switchable
if each 4-cycle can be replaced by another 4-cycle obtained by replacing one pair of non-
adjacent edges of the original 4-cycle by its diagonals so that the transformed set of 4-cycles
forms another 4-cycle system. The existence of diagonally switchable 4-cycle system of Kv
has already been solved [1]. In this paper we give an alternative proof of this result and use
the method to prove a new result for Kv ?I, where I is any one factor of Kv.
v
Acknowledgments
I would like to express my sincere gratitude to my advisor Dr. Chris Rodger for
giving me an opportunity to work with him, without whose consistent support, insightful
suggestions and warm encouragement this work would have been impossible. I would also
like to extend my thanks to Dr. Lindner, Dr. Hoffman, Dr. Johnson whose lectures have
increased my depth and breadth of mathematical knowledge. I would also like to thank
Dr.Govil whose encouragement always increased my confidence.
Finally, I?d like to thank my family. My father extended his passion for education to
me while my mother was a constant source of support. I am grateful to my brother, sister
and brother in-law for their encouragement and enthusiasm. I am especially grateful to
my wife, for her patience, encouragement and for helping me in keeping my life in proper
perspective and balance.
Special thanks to my fellow graduate students and friends who made my stay at Auburn
as such a fun.
vi
Style manual or journal used Journal of Approximation Theory (together with the style
known as ?aums?). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (specifically LATEX)
together with the departmental style-file aums.sty.
vii
Table of Contents
List of Figures ix
1 Introduction 1
2 Maximum Packings of Kv with copies of P3 which contain no proper
subsystems 3
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.1 Case A: v = 3k. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 Case B: v = 3k +1. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.3 Case C: v = 3k +2. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.4 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Decomposition of a Kv into copies of Pm which contain no proper sub-
systems 12
3.1 Notation and Basic Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 The Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Decomposition of a Kv and Kv ? I into diagonally switchable 4-cycle
systems 37
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3 Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3.1 Case A: v = 24s+1,s ? 4. . . . . . . . . . . . . . . . . . . . . . . . 41
4.3.2 Case B: v = 24s+9,s ? 5. . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.3 Case C: v = 24s+17,s ? 6. . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.4 The Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Decompositions of Kv ?I . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Bibliography 50
viii
List of Figures
2.1 Example-1: P3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 The 3k Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 The 3k +1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 P1(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1 Example of C0 in K7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Example of Euler tour on K7 . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Example with v = 7 and m = 3 . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Example with m = 7 and general v . . . . . . . . . . . . . . . . . . . . . . . 22
3.5 Example with m = 7 and general v . . . . . . . . . . . . . . . . . . . . . . . 25
3.6 Example with m = 8 and general v . . . . . . . . . . . . . . . . . . . . . . . 26
3.7 Example with m = 8 and general v . . . . . . . . . . . . . . . . . . . . . . . 30
3.8 Example with m = 8 and general v . . . . . . . . . . . . . . . . . . . . . . . 34
4.1 Diagonal Switches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 4-cycle system of K12 ?I . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3 DS4CS(K12 ?I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
ix
Chapter 1
Introduction
For any two graphs G and H, a G-decomposition of H is an ordered pair T = (V,D),
where V is the vertex set of H and D is a partition of the edge set of H, each element of
which induces a copy of G. For any graph G and any set L of edges in Kv, a G-packing
with a leave L of order v is an ordered pair T = (V,B), where V is the vertex set of Kv and
B is a partition of the edge set of Kv ? L, each element of which induces a copy of G. A
G-packing of order v with leave L is said to be maximum if there is no G-packing of order v
with leave Lprime such that |Lprime| < |L|. A proper subsystem of T is an ordered pair S = (V prime,Bprime)
where V prime ? V, Bprime ? B and (V prime,Bprime) is a G-design of Kvprime for |V| > |V prime| = vprime > 1. A
G-packing with L = ? is said to be a G-design.
When considering graph decompositions the most natural question is to find the set
of values of v for which there exists a decomposition of Kv into edge-disjoint copies of a
fixed graph G. This set of values is called as the spectrum of G-decompositions of Kv. This
question has been settled for many G, for example, where G is: Kv for v ? {3,4} [10, 12], a
star [19], a path [18], any graph with no more than four vertices [3], or a connected graph
with no more than five edges [9], a cycle [11, 2, 16]. For an up to date survey see [6].
Another question considered in the literature concerns the existence of G-designs which
contain no proper subsystems. That is, for which values of v is it possible to find a G-design
(V,C) of order v such that there does not exist a G-design (W,D) where W ? V and D ? C.
Doyen [8] settled this question for Steiner triple systems (that is,when G = K3). Rodger
and Spicer solved this problem when G = K4 ?e [15]. The reader may also be interested
1
to note that the related problem for Steiner quadruple systems has been considered, but is
still unsolved [14].
The main result in this dissertation is to solve the problem of G-designs with no proper
subsystems for the particular case where G = P3, considering the problem for both designs
and for maximum packings with non-empty leaves. We then solve the problem for the
general case in which G = Pm, a simple path with m edges, and H = Kv for every value of
m and v.
A second problem is also solved. AC4-decomposition ofGis also known in the literature
as a 4-cycle system of order G. A C4-decomposition of Kv is said to be a 4-cycle system of
order v and is denoted by 4CS(v). Such a decomposition exists if and only if v ? 1 (mod 8)
[13]. In this dissertation we consider a class of 4-cycle systems with diagonally switchable
property. A set of 4-cycles is said to be diagonally switchable if each 4-cycle can be replaced
by another 4-cycle obtained by replacing one pair of non-adjacent edges of the original 4-
cycle by its diagonals. In this dissertation we solve the problem of a C4-decomposition of a
graph G with the property of being diagonally switchable, where G is Kv or Kv?I. Here, I
is any one factor of Kv. A 1-factor I of a complete graph is a spanning one regular subgraph
of Kv. Note that in order to have a 1-factor v has to be even.
The decomposition of the complete graph Kv into diagonally switchable 4-cycles has
already been solved [1], but we have come up with another construction. This construction
not only solves the case for Kv in a more efficient way, but is also powerful enough to easily
solve the case for Kv ?I.
2
Chapter 2
Maximum Packings of Kv with copies of P3
which contain no proper subsystems
2.1 Introduction
We now turn our attention to decompositions of Kv with copies of P3 which contain
no proper subsystems. We will consider this problem for both designs and for maximum
packings with non-empty leaves. The constructions used here are of interest in their own
right, being neat modifications of the Bose construction for Steiner triple systems.
Before proceeding to the constructions, we need some definitions and notation. Let
(a,b,c,d) denote the 3-path induced by the edge set {{a,b}, {b,c}, {c,d}} (see figure 2.1).
cc
b
ad
Figure 2.1: Example-1: P3
Suppose (V,B) is a P3-packing of order v and suppose (V prime,Bprime) is a subsystem of (V,B).
Notice that if P1 = (a,b,c,d) ? Bprime then {a,c} ? V prime; so if P2 is the 3-path containing the
edge {a,c} then any subsystem containing P1 must also contain all the vertices in P2. We
denote this fact by writing P1 ? P2. We also write P1 ? {a,c} to denote the fact that any
3
subsystem containing P1 must contain the vertices in {a,c} and we will write {a,b} ? P1
to note that the edge {a,b} is in P1.
2.2 Constructions
We consider three cases in turn, depending on the congruence of v (mod 3). In all the
following constructions, in any ordered pair reduce arithmetic operations modulo k in the
first component and modulo 3 in the second component.
2.2.1 Case A: v = 3k.
We begin with a construction of a P3-design.
The 3k Construction. Let V = Zk ?{1,2,3} and G be a copy of K3k defined on the
vertex set V and define a collection B of copies of P3 as follows (see figure 2.2).
(1) Type 1: for each x ? Zk, let
P1(x) = ((x+1,2),(x,1),(x,3),(x,2)) ? B.
(2) Type 2: for {x,y} ? Zk, x negationslash= y, let
P2(x,y) = ((x+1,2),(y,1),(x,1),(y +1,2)) ? B.
(3) Type 3: for 0 ? x < y ? k ?1 and for 3 ? i ? 4, let
Pi(x,y) = ((x,i),(y,i?1),(x,i?1),(y,i)) ? B.
In this case every maximum packing has empty leave, so a P3-design is required. We
now show this is what The 3k Construction produces.
4
01
2
K-2
K-1
P
1
P
2
P
3
P
4
Figure 2.2: The 3k Construction
Proposition 2.2.1. The 3k Construction produces a P3-design of order 3k.
Proof. The total number of paths in aP3-design of orderv = 3k is
parenleftbiggv
2
parenrightbigg
/3 = k(3k?1)/2.
We begin by counting the number of paths in B.
The number of Type 1 paths is clearly k. For 2 ? i ? 4, Pi(x,y) contains k(k ? 1)/2
choices for x and y. Therefore |B| = k +3k(k ?1)/2 = k(3k ?1)/2 as required.
Now it remains to show that each edge e in E(K3k) occurs in some P3 in B. If
e = {(x,i),(y,i)} with x,y ? Zk, x negationslash= y and 1 ? i ? 3, then e occurs in Pi+1(x,y). If
e = {(x,i),(x,j)}where 1 ? i < j ? 3 then e occurs in P2(x?1,x) if i = 1 and j = 2 and
otherwise it occurs in P1(x). If e = {(x,i),(y,i + 1)} where 1 ? i ? 3 and {x,y} ? Zk,
x negationslash= y, then e occurs in
(i) Pi+1(x,y) if 2 ? i ? 3,
(ii) P2(x,y ?1) if i = 1 and y negationslash= x+1, and
(iii) P1(x) otherwise.
5
Proposition 2.2.2. The P3-design (V,B) of order v = 3k constructed using The 3k Con-
struction contains no proper subsystems.
Proof. Suppose (V prime,Bprime) is a subsystem of (V,B). We consider each possible copy of
P3 in Bprime by considering three cases in turn, eventually showing that in fact V prime = V.
Case 1: The subsystem contains P1(x) for some x ? Zk. Notice that
P1(x) ? {(x,2),(x+1,2)} ? P3(x,x+1) ? {(x+1,2),(x+1,3)} ? P1(x+1). There-
fore, if P1(x) ? Bprime for some x ? Zk then P1(x) ? Bprime for all x ? Zk. Since
uniondisplay
x?Zk
V(P1(x)) = V
it follows that V prime = V.
Case 2: The subsystem contains Pi(x,y) for some i ? {3,4} and some x,y ? Zk with
x < y. Then Pi(x,y) ? {(y,i?1),(y,i)} ? P1(y). So by Case 1, V prime = V.
Case 3: The subsystem contains P2(x,y) for some x,y ? Zk with x < y. Then
P2(x,y) ? {(x+1,2),(y +1,2)} ? P3(x+1,y +1). So by Case 2, V prime = V.
Therefore since V prime negationslash= ?, V prime = V. So (V,B) contains no proper subsystems.
2.2.2 Case B: v = 3k +1.
We begin with a construction of a P3-design.
The 3k + 1 Construction. Let V = {{?} ? (Zk ? {1,2,3})} and G be a copy of
K3k+1 defined on the vertex set V and define a collection B of copies of P3 as follows (see
figure 2.3).
(1) Type 1: for each x ? Zk, let
P1,1(x) = (?,(x,2),(x,3),(x,1))
P1,2(x) = ((x,3),?,(x,1),(x+1,2)).
P1(x) = {P1,i(x) | 1 ? i ? 2} and P1(x) ? B.
(2) Type 2: for {x,y} ? Zk, x negationslash= y, let
P2(x,y) = ((x+1,2),(y,1),(x,1),(y +1,2)) ? B.
6
(3) Type 3: for 0 ? x < y ? k ?1 and for 3 ? i ? 4, let
Pi(x,y) = ((x,i),(y,i?1),(x,i?1),(y,i)) ? B.
In this case every maximum packing has empty leave, so a P3-design is required. The
following result shows this is what The 3k +1 Construction produces.
01
2
K-2
K-1
P
11
P
2
P
3
P
4
P
12
Figure 2.3: The 3k +1 Construction
For those familiar with modifications of the Bose construction for Steiner triple systems
to produce P3-designs, one would expect to see subsystems on the vertex set {{?}?(Zk ?
{1,2,3})}. As the following shows, such subsystems are destroyed by a bijection mapping
the edge{(x,1),(y,2)} to {(x,1),(y+1)} (seeP1,2). This has the dual effect of keeping paths
intact and creates no subsystems in the process, as the following shows.
Proposition 2.2.3. The 3k +1 Construction produces a P3-design of order 3k +1.
Proof. The total number of paths in a P3-design of order 3k+1 is
parenleftbiggv
2
parenrightbigg
/3 = k(3k+1)/2.
We begin by counting the number of paths in B.
The number of Type 1 paths is clearly 2k. For 2 ? i ? 4, Pi(x,y) contains k(k ?1)/2
choices for x and y. Therefore |B| = 2k +3k(k ?1)/2 = k(3k +1)/2 as required.
7
Now it remains to show that each edge e in E(K3k+1) occurs in some P3 in B. If
e = {(x,i),(y,i)} with x,y ? Zk, x negationslash= y and 1 ? i ? 3, then e occurs in Pi+1(x,y). If
e = {(x,i),(x,j)} where 1 ? i < j ? 3 then e occurs in P2(x?1,x) if i = 1 and j = 2 and
otherwise it occurs in P1,1(x). If e = {?,(x,i)} where1 ? i ? 3 then e occurs in P1(x). If
e = {(x,i),(y,i+1)} where 1 ? i ? 3 and {x,y} ? Zk, x negationslash= y, then e occurs in
(i) Pi+1(x,y) if 2 ? i ? 3,
(ii) P2(x,y ?1) if i = 1 and y negationslash= x+1, and
(iii) P1,2(x) otherwise.
Proposition 2.2.4. The P3-design (V,B) of order v = 3k+1 constructed using The 3k+1
Construction contains no proper subsystems.
Proof. Suppose (V prime,Bprime) is a subsystem of (V,B). We consider each possible copy of
P3 in Bprime by considering four cases in turn, eventually showing that in fact V prime = V.
Case 1: The subsystem contains P1,1(x) for some x ? Zk. Notice that
P1,1(x) ? {(?,(x,1)} ? P1,2(x) ? {?,(x + 1,2))} ? P1,1(x + 1). Therefore, if
P1,1(x) ? Bprime for some x ? Zk then P1,1(x) ? Bprime for all x ? Zk. Since
uniondisplay
x?Zk
V(P1,1(x)) = V, it
follows that V prime = V.
Case2: The subsystem contains P1,2(x) for some x ? Zk. Notice that
P1,2(x) ? {(x,1),(x,3)} ? P1,1(x). So by Case 1, V prime = V.
Case 3: The subsystem contains Pi(x,y) for some i ? {3,4} and some x,y ? Zk with
x < y. Then Pi(x,y) ? {(x,i?1),(x,i)} ? P1,1(x). So by Case 1, V prime = V.
Case 4: The subsystem contains P2(x,y) for some x,y ? Zk with x < y. Then
P2(x,y) ? {(x+1,2),(y +1,2)} ? P3(x+1,y +1). So by Case 3, V prime = V.
8
Since V prime negationslash= ?, V prime = V. So (V,B) contains no proper subsystems.
2.2.3 Case C: v = 3k +2.
We begin with a construction of a P3-design.
The 3k + 2 Construction. Let V = {{?1,?2}?(Zk ?{1,2,3})} and G be a copy
of K3k+2 defined on the vertex set V and define a collection B of copies of P3 as follows.
(1) Type 1: for each x ? Zk, let
P1,1(x) = (?2,(x,3),?1,(x,1))
P1,2(x) = ((x,2),?2,(x,1),(x+1,2))
P1,3(x) = (?1,(x,2),(x,3),(x,1)).
P1(x) = {P1,i(x) | 1 ? i ? 3} and P1(x) ? B (see figure 2.4).
P
11
P
12
?
1
?
2
P
13
Figure 2.4: P1(x)
(2) Type 2: for {x,y} ? Zk, x negationslash= y, let
P2(x,y) = ((x+1,2),(y,1),(x,1),(y +1,2)) ? B.
(3) Type 3: for 0 ? x < y ? k ?1 and for 3 ? i ? 4, let
Pi(x,y) = ((x,i),(y,i?1),(x,(i?1),(y,i))) ? B.
In this case every maximum packing has leave L of size 1. The following result shows
this is what The 3k +2 Construction produces.
9
Proposition 2.2.5. The 3k+2 Construction produces a P3-packing of order 3k+2 with a
leave L = {?1,?2} of size 1.
Proof. The total number of paths in a maximum P3-packing of order 3k+2 with leave
of size 1 is
parenleftbiggv
2
parenrightbigg
/3?1 = 3(k2 +k)/2. We begin by counting the number of paths in B.
The number of Type 1 paths is clearly 3k. For 2 ? i ? 4, in defining Pi(x,y) contains
k(k?1)/2 choices for x and y. Therefore |B| = 3k+3k(k?1)/2 = 3(k2 +k)/2 as required.
Now it remains to show that each edge e in E(K3k+2)?{?1,?2} occurs in some P3
in B. If e = {(x,i),(y,i)} with x,y ? Zk, x negationslash= y and 1 ? i ? 3, then e occurs in Pi+1(x,y).
If e = {?1,(x,i)} or {?2,(x,i)} with x ? Zk, 1 ? i ? 3, then e occurs in P1(x). If
e = {(x,i),(x,j)} with x ? Zk, 1 ? i ? j ? 3 and i negationslash= 1,j negationslash= 2 then e occurs in P1,3(x)
otherwise occurs in P2(x?1,x). If e = {(x,i),(y,i+1)} where 1 ? i ? 3 and {x,y} ? Zk,
x negationslash= y then e occurs in
(i) Pi+1(x,y) if 2 ? i ? 3,
(ii) P2(x,y ?1) if i = 1 and y negationslash= x+1, and
(iii) P1,2(x) otherwise.
Proposition 2.2.6. The maximum P3-packing (V,B) of order v = 3k+2 constructed using
The 3k +2 Construction contains no proper subsystems.
Proof. Suppose (V prime,Bprime) is a subsystem of (V,B). We consider each possible copy of
P3 in Bprime by considering five cases in turn, eventually showing that in fact V prime = V.
Case 1: The subsystem contains P1,1(x) for some x ? Zk. Notice that
P1,1(x) ? {?2,(x,1)} ? P1,2(x) ? {?1,(x+1,2)} ? P1,1(x+1).
10
Therefore, if P1,1(x) ? Bprime for some x ? Zk then P1,i(x) ? Bprime for all x ? Zk where
1 ? i ? 2. Since
uniondisplay
x?Zk
uniondisplay
1?i?2
V(P1,i(x)) = V, it follows that V prime = V.
Case 2: The subsystem contains P1,2(x) for some x ? Zk. Notice that
P1,2(x) ? {(x,2),(x + 1,2)} ? P3(x,x + 1) ? {?2,(x,3))} ? P1,1(x). So by Case 1,
V prime = V.
Case 3: The subsystem contains P1,3(x) for some x ? Zk. Notice that
P1,3(x) ? {?1,(x,1))} ? P1,1(x). So by Case 1, V prime = V.
Case 4: The subsystem contains P2(x,y) for some x,y ? Zk with x < y. Then
P2(x,y) ? {(x,1),(x+1,2)} ? P1,2(x). So by Case 2, V prime = V.
Case 5: The subsystem contains Pi(x,y) for some i ? {3,4} and some x,y ? Zk with
x < y. Then Pi(x,y) ? {(x,i?1)(x,i)} ? P1,3(x). So by Case 1, V prime = V.
Therefore since V prime negationslash= ?, V prime = V. So (V,B) contains no proper subsystems.
2.2.4 Remarks
The constructions described in this section can easily be adapted to construct Pm-
designs for odd values of m and specific, and a related construction will produce Pm-designs
when m is even. These constructions are likely to produce a framework for constructing
Pm-designs with no subsystems for all values of v and m, providing the small values of v
can be settled. The results in Chapter 3 abandon this approach since it seems that solving
the problem for small values of v can be extended to a method that works for all v.
11
Chapter 3
Decomposition of a Kv into copies of Pm
which contain no proper subsystems
In this chapter we solve the G-design problem with no subsystems for the case G = Pm,
a simple path with m edges, for every value of m. The existence of Pm-decompositions of
Kv was solved by Tarsi [18], by proving the following result.
Theorem 3.1 ([18]). A necessary and sufficient condition for the existence of a decompo-
sition of a complete multigraph ?Kv into edge disjoint simple paths of length m is
v = 1, or
?v(v ?1) ? 0 (mod 2m) and v ? m+1.
(3.1)
The approach used in proving the result involves both modifications of Tarsi?s con-
structions and in some cases to come up with a completely new construction to make sure
that the Pm-designs have no subsystems. We have created new techniques to check for
subsystems in our constructions. These proof techniques can be easily applied to check for
subsystems in many G-designs. The following section contains the basic ideas and notation
which will be used throughout the rest of the chapter.
3.1 Notation and Basic Ideas
For any G-decomposition T = (V,C), it will be useful to let E(T) denote the edges
occurring in
uniondisplay
c?C
c; in particular, if S = (W,D) is a subsystem of T, then E(S) = E(Kvprime),
12
where vprime = |W|. In the following constructions, the set of vertices of Kv will be either
V = Zv or Zv?1?{?}. Let v = |V| and ? = |E(T)| denote the total number of vertices and
edges respectively. Let the trail T = {{x0,x1},{x1,x2},...,{xn?1,xn}} (not all vertices
need be distinct) be denoted by (x0,x1,...,xn), and if T is a path P then let the cycle
P + {x0,xn} also be denoted by (x0,x1,...,xn); it will be clear from the context which
structure is being used. For each trail T = (x0,x1,...,xn) on the vertex set Zz or Zz ?{?}
(so z = v or v ? 1 respectively), let T + i be the trail (x0 + i,x1 + i,...,xn + i), where
each sum is reduced modulo z if xj negationslash= ?, and where ? + i is defined to be ?. If T1 =
(x0,x1,...,xn) and T2 = (y0,y1,...,yn) are two trails with xn = y0, then denote the
concatenation of T1 and T2 by T1 + T2 = (x0,x1,...,xn = y0,y1,...,yn). If x negationslash= ? and
y negationslash= ? are two elements of Zz for some z ? {v,v ?1}, then the edge {x,y} is said to be of
difference k if k = min{|y ? x|,z ? |y ? x|}. The set of all differences will be denoted by
Dv = {1,2,...,floorleftv/2floorright}.
One of the basic ingredients used in the constructions is the trail
C(v,k) = (0,k +1,1,k +2,...,k ?1,v ?1,k,0), (3.2)
where k ? Dv and k < (v ? 3)/2. Notice that C(v,k) has length 2v and contains all the
edges of differences k and k +1.
ForanytrailT = (v1,v2,...,vk)andk ? m, letT/mbe the setofm-trails{(vi,...,vi+m) |
i ? {zm + 1 | 0 ? z ? floorleftk ?1/mfloorright?1}}. Notice that the edges in T/m partition all but at
most the last m?1 of the edges in T. Our aim is to pick T carefully so that each element
in T/m is a path. For any trail T = (v1,v2,...,vk), if vi and vj are the first occurrences of
a and b respectively in T then let S(T,a,b) denote the subtrail (vi,vi+1,...,vj) of T. For
x,y ? Zz with x negationslash= y, let I(x,y) be the path (x,x + 1,x + 2,...,y) consisting entirely of
edges of difference 1 reducing the sums modulo z.
13
In order to prove that a given G-decomposition (V,C) does not have a subsystem
(W,D), the argument here is usually based on the observation that if {x,y} ? W, then
there exists a path c ? C containing the edge {x,y}, implying that V(c) ? W. This obser-
vation is denoted by {x,y} ? V(c). Often a specific vertex ? ? V(c) is of specific interest,
so we similarly write {x,y} ? ? to indicate that since {x,y} ? W it follows that ? ? W.
A common technique used here to show that a Pm-design has no subsystems when v is even
is to focus on the pairs of vertices joined by an edge of difference v/2, showing that either
the edge {u,u + v/2} ? {u + 1,u + v/2 + 1} or {u,u + v/2} ? {u ? 1,u + v/2 ? 1}; in
either case we say that the next half difference is also in the subsystem.
3.2 Preliminary Results
In order to prove the main result we first make the following useful observations.
Lemma 3.2. If m ? 2v/3 then every Pm-decomposition of Kv has no subsystems.
Proof. Suppose S = (W,D) is a subsystem of the Pm-decomposition (V,C) of Kv.
Then since D contains a path |W| ? m + 1. Consider an edge {x,y}, where x ? W and
y ? V ?W. Since S is a subsystem, each edge in the path P that contains the edge {x,y}
has at least one end in V ?W. Therefore | V ?W |? ceilingleftm/2ceilingright. So |V| = |W|+|V ?W| ?
m+1+m/2 = 3m/2+1 ? |V|+1, a contradiction. Hence the Pm-decomposition contains
no subsystems.
We now prove a lemma that is used regularly in later constructions. It considers the
concatenation of various copies of C(v,k) (see Equation 3.2).
14
Lemma 3.3. Suppose that i,j ? Dv with v/2 > j > i, and that j ?i is odd. Let T be the
trail formed by the concatenation C(v,i) + C(v,i + 2) + ??? + C(v,j ? 1). If T contains a
cycle C induced by consecutive vertices, then the length of C is at least 2i+1.
Proof. We prove the result by showing that if T contains x consecutive edges that form
a cycle C then x ? 2i+1.
Looking at the structure of C(v,i), any cycle consisting only of edges in C(v,i) has
length 2i + 2. If C contains edges from both C(v,l) and C(v,l + 2) then C must contain
precisely the first 2l edges in C(v,l+2) together with the edge {0,l} in C(v,l), so has length
2l+1. Since l ? i, we can conclude that the length of the smallest cycle in T is 2i+1.
Corollary 3.4. Suppose that i,j ? Dv with v/2 > j > i, and that j?i is odd. Let T be the
trail formed by the concatenation C(v,i)+C(v,i+2)+???+C(v,j?1). If m ? 2i then all
trails in T/m are paths.
Proof. From Lemma 3.3 it follows that each cycle formed by the consecutive vertices
in T has length at least 2i + 1. Since m ? 2i, we can conclude that all trails in T/m are
paths.
Next we consider a similar concatenation.
Corollary 3.5. Suppose that i,j ? Dv with v/2 > j > i, that j?i is odd, and that x ? Zz.
Let T be the trail formed by the concatenation I(x,0)+C(v,i)+C(v,i+2)+???+C(v,j?1).
If
m ?
?
??
??
min{v +x?2i?2,2i} when x ? i+1,and
min{v +x?1,2i} otherwise
then all trails in T/m are paths.
Proof. Let C be any cycle formed by the consecutive vertices in T. If C consists only
of edges in I(x,0)+C(v,i) then C must contain precisely the v?x edges in I(x,0) together
15
with the first 2x ? 2i ? 1 edges of C(v,i) if x ? i + 1 and the first 2x edges of C(v,i)
otherwise. If C contains edges from both C(v,l) and C(v,l + 2) then from Lemma 3.3 it
follows that the length of the C must be 2i+1.
Thus we can conclude that whenever
m <
??
?
??
min{v +x?2i?1,2i+1} when x ? i+1,and
min{v +x,2i+1} otherwise ,
all trails in T/m are paths.
3.3 The Main Result
Now we state and prove the main theorem.
Theorem 3.6. Let m ? 3. There exists a Pm-decomposition (V,C) of Kv containing no
subsystems if and only if either
v = 1, or m divides
parenleftbiggv
2
parenrightbigg
and v ? m+1. (3.3)
Proof. The necessary condition follows from two observations that if Kv contains at
least one edge (so v > 1) then C must contain at least one path and so |V| ? m + 1; and
since each of the
parenleftbiggv
2
parenrightbigg
edges in Kv occurs in exactly one path and each path contains exactly
m edges.
In order to prove the sufficiency we now consider two cases depending on whether v is
odd or even, each case considering various subcases in turn. In view of Theorem 3.1 and
Lemma 3.2, if m ? 2v/3 then Pm-decompositions exist and clearly have no subsystems; so
we can assume that m < 2v/3. In particular, since v ? m+1 ? 4 it follows that m ? v?2.
Case A: v is odd.
16
Let C0 = (v0,v1,v2,...,vv) be a hamiltonian cycle defined by
vi=
??
?
??
? if i ? {0,v}, and
(?1)iceilingleft(i?1)/2ceilingright otherwise,
where each sum is reduced modulo v (see figure 3.1). Let Ci = C0+i for each i ? Zv?1. Then
clearly Ci = Ci+(v?1)/2 for i ? Z(v?1)/2. Also note that {Ci | i ? Z(v?1)/2} is the standard
hamiltonian decomposition of Kv. Form an Euler tour (e1,e2,...,e?) by the concatenation
C0 + C1 + ??? + C(v?3)/2 (see figure 3.2). For each i ? Zv(v?1)/2m, let pii be the trail
induced by {eim+1,eim+2,...,e(i+1)m} (see figure 3.3). Then (V,C) = (Zv?1 ? {?},{pii |
i ? Zv(v?1)/2m}) is a Pm-decomposition of Kv. Suppose S = (W,D) is any subsystem
in this Pm-decomposition of Kv. Now we consider various possibilities, arriving at the
contradiction W = V in each case.
0
?
1
2
4
3
5
Figure 3.1: Example of C0 in K7
17
0
?
1 2
4
3
5
Figure 3.2: Example of Euler tour on K7
0
?
1
2
4
3
5
Figure 3.3: Example with v = 7 and m = 3
18
Case 1: Suppose {?,i} ? E(S) for some i.
We will show that {?,i} ? i + 1. By repeating this argument we can conclude that
W = V.
Since m ? 3 and Ci = (?,i,i + 1,...,i + (v ? 1)/2 + 1,i + (v ? 1)/2,?), clearly
{?,i} ? i+1 except possibly if
(a) {?,i} is the last edge of some pij and i < (v ?1)/2, or
(b) {?,i} is the first edge of some pij and i ? (v ?1)/2.
We now consider each exceptional case in turn.
Case 1a: Suppose {?,i} is the last edge of some pij and i < (v ?1)/2.
Since m ? 3, in this case pij = (...,i+(v ?1)/2,i?1+(v ?1)/2,?,i), so clearly
{?,i} ? i+(v ?1)/2. (3.4)
Then for some k, {?,i+(v ?1)/2} is in the path pij+k = (...,i+(v ?1)/2,?,i+1,...)
or in the path pij+k = (...,i+(v ?1)/2,?) in C.
In the first case Equation 3.4 implies that V(pij+k) ? W, so i+1 ? W as required.
Otherwise E(Ci) ? {?,i} =
kuniondisplay
l=1
E(pij+l). So |V| ? 1 = |E(Ci) ? {?,i}| is divisible
by m. So this case only arises when |V| ? 1 (mod m). So since pij+k = (...,i + 1 + (v ?
1)/2,i + (v ? 1)/2,?), we have {?,i} ? {?,i + (v ? 1)/2} ? i + 1 + (v ? 1)/2. Then,
since |V| ? 1 (mod m), it follows that E(Ci+1)?{?,i+1+(v?1)/2} =
2kuniondisplay
l=k+1
E(pij+l) and
so pij+(2k+1) = (i+1+(v?1)/2,?,i+2,...) implying that {?,i} ? i+2. But {i,i+2}
is in pij+(k+1) = (?,i+1,i+2,i,...). Hence {?,i} ? i+1, so i+1 ? W as required.
Case 1b: Suppose {?,i} is the first edge of some pij and i ? (v ?1)/2.
19
Since m ? 3, in this case pij = (i,?,i?(v?1)/2+1,i?(v?1)/2+2,...), so clearly
{?,i} ? i?(v ?1)/2+2. (3.5)
Then for some k, {?,i?(v?1)/2+2}is in the path pij+k = (??? ,i+1,?,i?(v?1)/2+2,...)
or in the path pij+k = (?,i? (v ? 1)/2 + 2,i? (v ? 1)/2 + 3,...) in C. So in either case
Equation 3.5 implies that
V(pij+k) ? W (3.6)
In the first case Equation 3.6 immediately implies that i+1 ? W as required.
Otherwise E(Ci+1 = Ci?(v?1)/2+1) + {?,i} =
k?1uniondisplay
l=0
E(pij+l). So |V| + 1 = |E(Ci+1) +
{?,i}| is divisible by m. So this case only arises when |V| + 1 ? 0 (mod m). Therefore
pij+(2k?1) = (...,i+2,?,i?(v?1)/2+3). By Equation 3.6, {?,i?(v?1)/2+3} ? W,
which implies that V(pij+2k?1) ? W. Therefore i+ 2 ? W. Finally, notice that pij+(k?1) =
(...,i,i+2,i+1,?). Hence {i,i+2} ? {i+1} and so i+1 ? W as required.
Case 2: Suppose {i,i+1} ? E(S) for some i negationslash= ?.
We will show that {i,i + 1} ? {?,j} for some j. Then the result follows by Case 1.
Since the edge {i,i+1} is either immediately precedes or follows {?,i} in some Cx, clearly
{i,i+1} ? {?,i} except possibly if
(a) {i,i+1} is the first edge of some pij and i < (v ?1)/2, or
(b) {i,i+1} is the last edge of some pij and i ? (v ?1)/2.
Observe that in both the exceptional cases {i,i+1} ? i?1, since pij = (i,i+1,i?1,...)
or pij = (...,i?1,i+1,i) respectively. So for all x,
either {x,x+1} ? {?,x}, or {x,x+1} ? {x,x?1}. (3.7)
20
But, since C0 = (?,0,1,...) implies {0,1} ? {?,0}, recursively applying the observation
3.7 implies that for all i {i,i+1} ? {?,j} for some j (since at worst j = 0).
Case 3: Suppose {i,i+j} ? E(S) for some i negationslash= ?,j > 1.
Notice that if {i,i+j} is in some path pij then pij contains at least one of the vertices
i ? 1,i + 1,i + j ? 1 or i + j + 1. In any of these cases {i,i + j} ? {k,k + 1} for some
k ? {i?1,i,i+j ?1,i+j}. So the result follows by Case 2.
Case B: v is even.
We will solve this case by considering different subcases in turn depending on the length
of the path.
Case 1: m = v ?2.
By Lemma 3.2 and from the fact that m ? 3, we can conclude that Pm-decompositions
of Kv contain no subsystems.
Case 2: m = v ?3.
Since m < 2v/3 and in this case m = v ? 3, it follows that v < 9. By the necessary
condition that m must divide
parenleftbiggv
2
parenrightbigg
, the only situation that needs to be solved is when
v = 6 and m = 3. If v = 6, let Z(3) be the zigzag path defined by (0,2,5,3). So
(V,C) = (Z6,{{Z(3)+i | i ? Z3}?(0,1,2,3)?(3,4,5,0)}) is a P3-decomposition of K6.
Suppose S = (W,D) is any subsystem in this P3-decomposition. Let pij ? D be any
path of length 3. Suppose pij = Z(3) + i for some i ? Z3. Each path Z(3) + i contains
the edge {k,k +3} of half difference for some k. Since k and k +3 have different parity, it
follows that Z(3)+i contains both k +1 and k +4. So W must contain the vertices of the
next half difference, which implies that Z(3)+(i+1) ? D. By repeating this argument we
can conclude that V({Z(3)+i|i ? Z3}) = W = V.
21
Suppose pij = (0,1,2,3) or (3,4,5,0). In either of these cases pij ? {0,3} ? Z(3)+1 ?
D. Then the result follows by the above argument.
Case 3: m ? v ?4 and v ?m ? 3 (mod 4).
Without loss of generality we can assume m ? v ? 7, because v ? m negationslash? 3 (mod 4)
when m > v ? 7. Observe that in this case m is odd (since v is even in Case B and
v ?m ? 3 (mod 4)).
Let Z(m) be the zigzag path (v0,v1,...,vm) defined by
vi=
??
?
??
(?1)i+1ceilingleft(i+1)/2ceilingright for 0 ? i ? floorleftm/2floorright,and
vm?i +v/2 otherwise ,
where each sum is reduced modulo v. Notice that the set of m-paths Z = {Z(m) + i | i ?
Zv/2} partitions all the edges of differences in {2,3,...,ceilingleftm/2ceilingright}?{v/2} (see figure 3.4).
0
1
V-1
V+2/2
V/2
V-2/2
2
V-2
V+4/2
V
-4/2
Figure 3.4: Example with m = 7 and general v
Let T = (v1,v2,...,vk) be the trail formed by the concatenation I(m,0)+C(v,ceilingleftm/2ceilingright+
1) + C(v,ceilingleftm/2ceilingright + 3) + ??? + C(v,v/2 ? 2). Apply Corollary 3.5 to T using x = m and
i = ceilingleftm/2ceilingright+1 = (m+3)/2. Notice that in this case, if m ? 5 then x = m ? (m+5)/2 = i+1
and the condition of the Corollary 3.5 is met, and otherwise m = 3 in which case x = m ? i,
22
so clearly m ? min{2i,v+x}. Thus we can conclude that all trails in T/m are paths. Note
that in Case 3 v ? m ? 3 (mod 4), so ceilingleftm/2ceilingright + 1 ? v/2 ? 2(mod 2). So T/m is a set of
m-paths which partitions all the edges of differences in {ceilingleftm/2ceilingright+1,ceilingleftm/2ceilingright+2,...,v/2?1}
and the v?m edges of difference 1 from the vertex m forward to the vertex 0. So (V,C) =
(Zv,{Z ?T/m?I(0,m)}) is a Pm-decomposition of Kv.
Suppose S = (W,D) is any subsystem in this Pm-decomposition of Kv. Let pij ? D be
any path of length m. Now we consider various possibilities, arriving at the contradiction
W = V in each case.
Case 3a: Suppose that pij = Z(m)+i for some i ? Zv/2.
Each path Z(m)+i contains the edge {k,k +v/2} of half difference for some k
Suppose m ? 5. Then Z(m)+i contains both k+1 and k+v/2+1 (if m ? 1 (mod 4))
or both k ?1 and k +v/2?1 (if m ? 3 (mod 4)). So W must contain one pair of vertices
in the next half difference, which implies that either Z(m)+(i+1) or Z(m)+(i?1) ? D.
By repeating this argument we can conclude that V(Z) = W = V.
Suppose m = 3. Then Z(m)+i ? {k?2,k+v/2?2} ? Z(m)+i?2. So recursively
it follows that X = {k ? 2i,k + v/2 ? 2i | i ? Zv/2} ? W. Since v ? m ? 3 (mod 4) and
m = 3, it follows that v/2 is odd so k and k + v/2 have different parity. So X = V; so
W = V.
Case 3b: Suppose that pij ? I(0,m)?T/m ? D.
We will show that pij ? Z(m)+i ? D for some i, then the result follows from Case 3a.
Suppose m ? 5. Every pij ? I(0,m) ? T/m contains a pair of vertices {k,k + 2} for
some k, and the edge {k,k +2} ? Z(m)+i for some i. So Z(m)+i ? D as required.
Suppose m = 3. Then one of the following occurs.
(i) pij contains the edge {k,k +2}. So, as above, Z(m)+i ? D for some i.
23
(i) pij = (k,k+l,k+1,k+l+1) is contained in a C trail. In this case the edge {k,k+1} is
in some pin that must contain either k?1 or k+2. So S contains an edge of difference
2 (either {k,k +2} or {k ?1,k +1}). So S contains an edge in Z(m)+i for some i.
(ii) pij = (k,0,k+3,1) straddles two C trails. In this case the edge {0,1} ? I(0,3). So S
contains the edge {0,2} ? Z(m)+1.
Hence the result follows by Case 3a.
Case 4: m ? v ?4 and v ?m ? 1 (mod 4).
Without loss of generality we can assume m ? v ? 5, because v ? m negationslash? 1 (mod 4)
when m > v ? 5. Observe that in this case m is odd (since v is even in Case B and
v ?m ? 1 (mod 4)).
Let Z1(m) be the zigzag path (v0,v1,...,vm) defined by
vi=
??
?
??
(?1)i+1ceilinglefti/2ceilingright for 0 ? i ? floorleftm/2floorright,and
vm?i +v/2 otherwise ,
where each sum is reduced modulo v. Notice that the set of m-paths Z1 = {Z1(m)+i | i ?
Zv/2} partitions all the edges of differences in {1,2,...,floorleftm/2floorright}?{v/2} (see figure 3.5).
Let T = (v1,v2,...,vk) be the trail formed by the concatenation C(v,floorleftm/2floorright + 1) +
C(v,floorleftm/2floorright+3)+???+C(v,v/2?2); note that in Case 4 v?m ? 1 (mod 4), so floorleftm/2floorright+1 ?
v/2 ? 2 (mod 2). Using i = floorleftm/2floorright + 1 = (m + 1)/2, clearly m ? 2i, so Corollary 3.4 can
be applied to T to conclude that all trails in T/m are paths. So T/m is a set of m-paths
which partitions all the edges of differences in {floorleftm/2floorright + 1,floorleftm/2floorright + 2,...,v/2 ? 1}. So
(V,C) = (Zv,{Z1 ?T/m}) is a Pm-decomposition of Kv.
Suppose S = (W,D) is any subsystem in this Pm-decomposition. Let pij ? D be any
path of length m. Then either pij = Z1(m) + i for some i ? Zv/2 or pij ? T/m. We will
show that W = V in both these cases.
24
0
1
V-1
V+2/2
V/2
V-2/2
2
V-2
V+4/2
V
-4/2
Figure 3.5: Example with m = 7 and general v
Suppose that pij = Z1(m) + i for some i ? Zv/2. Each path Z1(m) + i contains the
edge {k,k+v/2} of half difference for some k. Since m ? 3, Z1(m)+i contains both k+1
and k +v/2 + 1 (if m ? 1 (mod 4)) or both k ?1 and k +v/2?1 (if m ? 3 (mod 4)). So
W must contain one pair of vertices in the next half difference, which implies that either
Z1(m)+(i+1) or Z1(m)+(i?1) ? D. By repeating this argument we can conclude that
V(Z1) = W = V.
If pij ? T/m, then since m ? 3, pij = (k,k + l,k + 1,k + 1 + l,...) for some k and
for some l, which implies that the edge {k,k + 1} is in some Z1(m) +i ? D. So the result
follows by the previous argument.
Case 5: m ? v ?4 and v ?m ? 2 (mod 4).
We will solve this case by considering two subcases in turn. Without loss of generality
we can assume m ? v ? 6, because v ? m negationslash? 2 (mod 4) when m > v ? 6. Observe that in
this case m is even (since v is even in Case B and v ?m ? 2 (mod 4)).
Case 5a: m ? v/2.
Let Z2(m) be the zigzag path (v0,v1,...,vm) define by
25
vi=
?
????
??
????
??
(?1)i+1ceilingleft(i+1)/2ceilingright for 0 ? i ? m/2?1,
vm?(i+1) +v/2 for m/2 ? i ? m?1,and
vm?1 +1 for i = m,
where each sum is reduced modulo v. Notice that the set of m-paths Z2 = {Z2(m)?i | i ?
Zv/2} partitions all the edges of differences in {2,3,...,m/2}?{v/2} and the v/2 edges of
difference 1 in I(0,v/2) (see figure 3.6).
0
1
V-1
V+2/2
V/2
V-2/2
2
V-2
V+4/2
V
-4/2
Figure 3.6: Example with m = 8 and general v
Let T = (v1,v2,...,vk) be the trail formed by the concatenation I(v/2,0)+C(v,m/2+
1) + C(v,m/2 + 3) + ??? + C(v,v/2 ? 2). Apply Corollary 3.5 to T using x = v/2 and
i = m/2 + 1; notice that in Case 5a m ? v/2, so x = v/2 ? m/2 + 2 = i + 1 and
m ? min{2i,v + x ? 2i ? 2} since m ? 4. So clearly the condition of the Corollary 3.5
is met. Thus we can conclude that all trails in T/m are paths. Note that in Case 5
v ? m ? 2 (mod 4), so m/2 + 1 ? v/2 ? 2(mod 2). So T/m is a set of m-paths which
partitions all the edges of differences in {m/2+1,m/2+2,...,v/2?1} and the v/2 edges
of difference 1 in I(v/2,0). So (V,C) = (Zv,{Z2 ?T/m}) is a Pm-decomposition of Kv.
26
Suppose S = (W,D) is any subsystem in this Pm-decomposition. Let pij ? D be any
path of length m. Then either pij = Z2(m) ? i for some i ? Zv/2 or pij ? T/m. We will
show that W = V in both these cases.
Case 5a(i): Suppose that pij = Z2(m)?i for some i ? Zv/2.
Each path Z2(m)?i contains the edge {k,k +v/2} of half difference for some k.
Suppose m ? 6. Then Z2(m)?i contains both k+1 and k+v/2+1 (if m ? 2 (mod 4))
or both k ?1 and k +v/2?1 (if m ? 0 (mod 4)). So W must contain one pair of vertices
in the next half difference, which implies that either Z2(m)?(i?1) or Z2(m)?(i+1) ? D.
By repeating this argument we can conclude that V(Z2) = W = V.
Suppose m = 4. Then Z2(m)?i ? {k?2,k+v/2?2} ? Z2(m)?i?2. So recursively
it follows that X = {k ? 2i,k + v/2 ? 2i | i ? Zv/2} ? W. Since v ? m ? 2 (mod 4) and
m = 4 it follows that v/2 is odd so k and k + v/2 have different parity. So X = V; so
W = V.
Case 5a(ii): Suppose that pij ? T/m ? D.
Since m ? 4, every pij ? T/m contains a pair of vertices {k,k + 2} for some k; since
{k,k +2} ? E(Z2(m)?i), it follows that Z2(m)?i ? D for some i. So pij ? Z(m)?i for
some i, so the result follows by Case 5a(i).
Case 5b: v/2 < m < 2v/3.
First observe that in this case m ? 6, since when m = 4 there is no even v which
satisfies v/2 < 4 < 2v/3. Recall that S(T,a,b) was defined to be a subtrail of T from a to
b.
Let D1 = I(m,0) + S(C(v,m/2 + 1),0,m ? v/2); it is easy to check D1 is a path of
length m. Denote by Tl, the final segment from m?v/2 to 0 remaining of C(v,m/2 + 1);
then note that |E(Tl)| = 3v ?2m > m. Let T = (v1,v2,...,vk) be the trail formed by the
concatenation I(0,m?v/2)+Tl +C(v,m/2+3)+???+C(v,v/2?2). Note that in Case
27
5 v ? m ? 2 (mod 4), so m/2 + 3 ? v/2 ? 2(mod 2), so T has all the edges of differences
m/2 + 1,...,v/2 ? 1, and v/2 edges of difference 1 from the vertex m forward (through
0) to m ? v/2. We now show that trails in T/m are paths by showing that if T contains
consecutive vertices that form a cycle C then it has length more than m; so let C be a cycle
formed by the consecutive vertices in T. Since |E(Tl)| > m, we need only consider 3 cases.
(i) Suppose C consists only of edges in I(0,m?v/2)+Tl. If C is in Tl then since Tl is a
subgraph of C(v,m/2+1) we can use Lemma 3.3 to conclude that the length of C is
greater than m. If C contains edges from the path I(0,m?v/2) then note that the
first vertex to be repeated in T is either (m?v/2)+m/2+2 or 0. The number of edges
between first two appearances of 3m/2?v/2+2 in T is m+4 > m; and the number of
edges between first two appearances of 0 in T is (2v?m?4)?(2m?v)+(m?v/2) =
5v/2?2m?4 > m since m < 2v/3 and v > 8. So the length of C is greater than m.
(ii) If C is in Tl +C(v,m/2+3)+???+C(v,v/2?2) then C is in C(v,m/2+1)+???+
C(v,v/2 ? 2). So we can use Lemma 3.3 to conclude that the length of C is greater
than m.
Therefore, by the above observations, it follows that, D1 ? T/m is a set of m-paths
which partitions all the edges of differences in {m/2+1,m/2+2,...,v/2?1} and the v/2
edges of difference 1 from the vertex m forward (through 0) to m?v/2.
Let Z3(m?1) be the zigzag path (v0,v1,...,vm?1) of length m?1 defined by
vi=
??
?
??
(?1)i+1ceilingleft(i+1)/2ceilingright for 0 ? i ? m/2?1,and
vm?(i+1) +v/2 for m/2 ? i ? m?1.
Observe that the paths in D1 ? T/m include v/2 edges of difference 1, one in L(x) =
{(x,x + 1),(x + v/2,x + v/2 + 1)} for each x ? Zv/2. Thus the set L of the remaining
v/2 edges of difference 1 also has exactly one edge in L(x) for each x ? Zv/2; so to each
28
path in {Z3(m? 1) + i | i ? Zv/2} we can add one edge from L to form the set M of v/2
simple m-paths. Notice that the set of m-paths M partitions all the edges of differences in
{2,3,...,m/2} ?{v/2} and the remaining v/2 edges in I(m ? v/2,m) of difference 1. So
(V,C) = (Zv,{M ?D1 ?T/m}) is a Pm-decomposition of Kv.
Suppose S = (W,D) is any subsystem in this Pm-decomposition. Let pij ? D be any
path of length m. Now we consider various possibilities for pij, arriving at the contradiction
W = V in each case.
Suppose that pij ? M. Each path pij ? M contains the edge {k,k + v/2} of half
difference for some k. Since m ? 6, pij also contains both k + 1 and k + v/2 + 1 (if
m ? 2 (mod 4)) or both k ? 1 and k + v/2 ? 1 (if m ? 0 (mod 4)). So W must contain
one pair of vertices in the next half difference. By repeating the argument we can conclude
that V(M) = W = V.
Suppose that pij ? D1 ? T/m. Since m ? 6, every pij ? D1 ? T/m contains a pair
of vertices {k,k + 2} for some k, which implies that D contains the path pii ? M which
contains the edge {k,k +2}. Then the result follows by the previous argument.
Case 6: m ? v ?4 and v ?m ? 0 (mod 4).
We will solve this case by considering three subcases in turn. Observe that in this case m
is even (since v is even in Case B and v ?m ? 0 (mod 4)).
Case 6a: m < v/2.
Let Z4(m) be the tailed zigzag path (v0,v1,...,vm) defined by
vi=
?
????
??
????
??
(?1)iceilingleft(i+2)/2ceilingright for 0 ? i ? m/2?1,
vm?(i+1) +v/2 for m/2 ? i ? m?1,and
vm?1 ?1 = v/2 for i = m,
29
where each sum is reduced modulo v. Notice that the set of m-paths Z4 = {Z4(m)?i | i ?
Zv/2} partitions all the edges of differences in {3,4,...,m/2+1}?{v/2} and the v/2 edges
of difference 1 in I(1,v/2+1) (see figure 3.7).
0
1
V-1
V+2/2
V/2
V-2/2
2
V-2
V+4/2
V-4/2
V-3
V-6/2
Figure 3.7: Example with m = 8 and general v
Let C2(x) = (x,x + 2,x + 4,...,x) be the trail (it is a cycle) of length v/2. Let
T = (v1,v2,...,vk) be the trail formed by the concatenation C2(v/2+1)+{v/2+1,v/2+
2} + C2(v/2 + 2) + I(v/2 + 2,1) + {C(v,m/2 + 2) + 1} + ??? + {C(v,v/2 ? 2) + 1}; note
that in Case 6 v?m ? 0 (mod 4), so m/2+2 ? v/2?2 (mod 2). So T has all the edges of
difference 2, of differences m/2+2,...,v/2?1, and the edges in I(1,v/2+1). If T contains
consecutive vertices that form a cycle C then we now show that the length of C is more
than m by considering the following 3 cases.
(i) Suppose C consists only of edges in C2(v/2+1)+{v/2+1,v/2+2}+C2(v/2+2)+
I(v/2+2,1). Observe that the least number of edges between two appearances of any
vertex in C2(v/2 + 1) +{v/2 + 1,v/2 + 2}+C2(v/2 + 2) +I(v/2 + 2,1) is clearly at
least v/2. Since m < v/2, it follows that the length of C is greater than m.
30
(ii) Suppose C is in I(v/2 + 2,1) + {C(v,m/2 + 2) + 1}. Since C(v,m/2 + 2) + 1 is
isomorphic to C(v,m/2 + 2), we can apply Lemma 3.3 to conclude that any cycle
consisting only of edges in C(v,m/2 + 2) + 1 has length m + 6. If C contains edges
from the path I(v/2 + 2,1) then since the second vertex in C(v,m/2 + 2) + 1 is less
than v/2 + 1 (all differences in T are at most v/2) which is not in I(v/2 + 2,1), it
follows that the length of C is greater than v/2 > m.
(iii) Suppose C is in {C(v,m/2 + 2) + 1}+???+ C{(v,v/2?2) + 1}. Then observe that
C(v,m/2 +j) + 1 is isomorphic to C(v,m/2 +j) for all j, so we can use Lemma 3.3
to conclude that the length of C is greater than m.
Therefore, by the above observations, T/m partitions into paths of length m all the
edges of differences in {m/2 + 2,...,v/2 ? 1} ? {2} and the v/2 edges of difference 1 in
I(v/2+1,1). So (V,C) = (Zv,{Z4 ?T/m}) is a Pm-decomposition of Kv.
Suppose S = (W,D) is any subsystem in this Pm-decomposition. Let pij ? D be any
path of length m. Then either pij = Z4(m) ? i for some i ? Zv/2 or pij ? T/m. We will
show that W = V in both these cases.
Case 6a(i): Suppose that pij = Z4(m)?i for some i ? Zv/2.
Each path Z4(m)?i contains the edge {k,k +v/2} of half difference for some k.
Suppose m ? 6. Then Z4(m)?i contains both k+1 and k+v/2+1 (if m ? 0 (mod 4))
or both k ?1 and k +v/2?1 (if m ? 2 (mod 4)). So W must contain one pair of vertices
in the next half difference which implies that either Z4(m)?(i+1) or Z4(m)?(i?1) ? D.
By repeating this argument we can conclude that V(Z4) = W = V.
Suppose m = 4 (so, being Case 6, v ? m ? 0 (mod 4)). Then Z4(m)?i ? {k+3,k+
v/2 + 3} ? Z4(m) ? i + 3. So recursively it follows that X = {k + 3i,k + v/2 + 3i | i ?
Zv/2} ? W. So X = V = W unless v ? 0 (mod 3).
31
Hence the only case that remains to be solved is when m = 4 and v ? 0 (mod 3) (so
actually v ? 0 (mod 12), since in this case v ? 0 (mod 4) as well). So finally suppose that
v ? 0 (mod 12) and m = 4. Notice that in this exceptional case,
for any x ? V,{x,x+v/2} ? {x+3,x+3+v/2}. (3.8)
So if {x,x + v/2} ? W then we can recursively apply Equation 3.8 to {x,x + v/2} to see
that {y ? V | y ? x (mod 3)} ? W. In particular, since {k,k + v/2} ? W, it follows
that A = {a ? V | a ? k (mod 3)} ? W. But since each path containing an edge of half
difference joining vertices in A also contains an edge of difference 1, we in fact know that
Aprime = {b ? V | b ? k ? 1 (mod 3),1 ? b ? v/2} ? W. Then observe that if b ? 4 and
b ? Aprime then {b,b ? 3} ? {b ? 3,b ? 3 + v/2}. So by applying Equation 3.8 recursively to
{b?3,b?3+v/2}, where b ? Aprime and b ? 4 we will get that B = {b ? V | b ? k?1 (mod 3)} ?
W. So {k,k+v/2} ? {a | a ? k or k?1 (mod 3)}. In particular {k?1,k+v/2?1} ? W,
so similarly {k?1,k+v/2?1} ? {a | a ? k?1 or k?2 (mod 3)}. Hence W = V in this
case.
Case 6a(ii): Suppose that pij ? T/m.
Now we consider various possibilities for pij. If pij contains two vertices that are joined
by an edge that occurs in Z4(m) ? i for some i, then the result follows from Case 6a(i).
Notice that if m ? 4 then each edge of difference 3 occurs in Z4(m) ?i for some i, and if
m ? 6 then each edge of difference 4 occurs in Z4(m)?i for some i.
Suppose m ? 6. Every pij ? T/m contains the vertices in {x,x + 3} or {x,x + 4} for
some x. So every subsystem S containing pij contains an edge of difference 3 or 4; so S
contains an edge in Z4(m)?i for some i.
Suppose m = 4. Then one of the following occurs.
32
(i) pij = (...,k,k + 2,k + 4,...). In this case the edge {k,k + 4} is in a path that must
contain either k?1 or k+5. So S contains an edge of difference 3 (either {k?1,k+2}
or {k +2,k +5}), so S contains Z4(m)?i for some i.
(ii) pij contains 3 consecutive edges in I(v/2 + 2,1). In this case pij contains a pair
of vertices distance 3 apart, so S contains an edge of difference 3. So S contains
Z4(m)?i for some i.
(iii) pij contains edges in I(v/2+2,1)+C(v,m/2+2)+1. In view of the Case(ii) we can
assume that pij contains at most 2 edges from I(v/2 + 2,1). So S contains an edge
of difference 2 or 3. If S contains an edge of difference 2 then S contains a path that
was just considered in Case(i). If S contains an edge of difference 3, then S contains
Z4(m)?i for some i.
(iv) pij = (k,k+l,k+1,k+l+1,k+2). In this case the edge {k,k+2} is in a path that
was just considered in Case(i). So S contains Z4(m)?i for some i.
Case 6b: v/2 ? m < 3v/4, and m ? v ?8.
First define the sub zigzag path (vprime0,vprime1,...,vprimem/2?1) of length m/2?1 by
vprimei = (?1)i+1ceilingleft(i+1)/2ceilingright for 0 ? i ? m/2?1.
Then let Z5(m) be the zigzag path (v0,v1,...,vm) defined by
vi=
?
????
??
????
??
vprime(m/2?1)?i for 0 ? i ? m/2?1,
vm/2?1 +1 for i = m/2,and
vm?i +v/2 for m/2+1 ? i ? m,
where each sum is reduced modulo v. Notice that the set of m-paths Z5 = {Z5(m) ? i |
i ? Zv/2} partitions all the edges of differences in {2,3,...,m/2}, v/2 edges of difference
v/2?1, and the v/2 edges of difference 1 in I(v/2,0) (see figure 3.8).
33
0
1
V-1
V+2/2
V/2
V-2/2
2
V-2
V+4/2
V
-4/2
Figure 3.8: Example with m = 8 and general v
Let A be the trail defined by (0,v/2,1,v/2 + 1,2,...,v ? 1,v/2) of length v which
covers the edges of difference v/2 and remaining edges of difference v/2 ? 1. Notice that
the only vertex appearing more than once in A is v/2 which appears twice.
If m > v/2 then let C = S(A,0,v ? m) + I(v ? m,v/2). C is a trail of length
3v/2?m > m. Let Tl be the final segment of A after the subtrail S(A,0,v ?m) has been
removed. Observe that the length of Tl is 2m?v. Clearly B = I(0,v?m)+Tl is an m-path.
Note that if m = v/2 then let B = I(0,v/2) and C = A.
In either case, let F be the subtrail of C containing the last m edges and let E be the
subtrail of C formed by removing F. F is an m-path because the only vertex repeated in
C is v/2 which appears as both the second and the last vertex. Note that
E=
??
?
??
S(C,0,(3v/2?2m)/2) if 3v/2?2m is even,and
S(C,0,v/2+floorleft(3v/2?2m)/2floorright) otherwise.
Let T = (v1,v2,...,vk) be the trail formed by the concatenation C(v,m/2 + 1) +
C(v,m/2 + 3) + ??? + C(v,v/2 ? 3) + E. Again we show that the trails in T/m are paths
by showing that each cycle C in T has length more than m; so let C be a cycle in T.
34
(i) Suppose C consists only of edges in C(v,m/2+1)+C(v,m/2+3)+???+C(v,v/2?3)
then by Lemma 3.3 we can conclude that the length of C is greater than m.
(ii) C contains edges from both C(v,v/2 ? 3) and E. First observe that, since m ?
max{4,v/2} and since m ? v?8, it follows that v ? 16. Hence 3v/4?m < v/2?3 <
v/2+floorleft(3v/2?2m)/2floorright. The first vertex to be repeated in C(v,v/2?3)+E is v/2?3
and the number of edges between it?s appearances is v ?5(> m), which implies that
the length of C is greater than m.
Therefore, by the above observations, we can conclude that all trails in T/m are paths.
Note that in Case 5 v?m ? 2 (mod 4), so m/2+3 ? v/2?3 (mod 2). So T/m?B?F is a
set of m-paths which partitions all the edges of differences in {m/2+1,m/2+2,...,v/2?
2}?{v/2}, the remaining v/2 edges of difference v/2?1, and the v/2 edges of difference 1
in I(0,v/2). So (V,C) = (Zv,{Z5 ?B ?F ?T/m}) is a Pm-decomposition of Kv.
Suppose S = (W,D) is any subsystem in this Pm-decomposition. Let pij ? D be any
path of length m. We will now consider various possibilities for pij and show that W = V
in each possibility. First observe that since v ? 16, m ? v/2 implies that m ? 8.
Suppose that pij = Z5(m)?i for some i ? Zv/2.
Each Z5(m)?i contains the edge {k,k+(v/2?1)} for some k. Therefore pij contains
both k ?1 and k ?1 + (v/2?1). So W must contain the edge {k ?1,k ?1 + (v/2?1)},
which implies that Z5(m)?(i+1) ? D. By repeating this argument we can conclude that
V(Z5) = W = V.
Suppose that pij ? B ?F ?T/m.
Every pij ? B?F ?T/m contains a pair of vertices {k,k+2} for some k, which implies
that the edge {k,k + 2} is in some Z5(m) ? i for some i. Hence the result follows by the
previous argument.
Case 6c: v/2 ? m ? 2v/3,m > v ?8.
35
Without loss of generality we can assume that m = v?4, because v?m ? 0 (mod 4) in
Case 6. By Lemma 3.2 m ? 2v/3, so in this case v/2 ? v?4 ? 2v/3, implying 8 ? v ? 12.
Since v is even and m has to divide
parenleftbiggv
2
parenrightbigg
, this implies that the only exceptional case that
needs to be solved is when v = 8 and m = 4.
So finally suppose that v = 8 and m = 4. Then let (V,C) = (Z7?{?},{Z6+i | i ? Z7})
is a P4- decomposition of K8 where Z6 = (?,0,6,1,5). This decomposition contains no
subsystems because whenever {?,x} is in any subsystem, {?,x} ? x+1 for some x ? Z7,
which implies that whenever Z6 + i is in any subsystem Z6 + (i + 1) is also in the same
subsystem. By repeating this argument we can conclude that V({Z6 +i | i ? Z7}) = V.
36
Chapter 4
Decomposition of a Kv and Kv ?I into
diagonally switchable 4-cycle systems
In this chapter we solve the problem of decomposing a complete graph Kv and Kv?F,
where F is any one factor, into 4-cycles having the property of being diagonally switchable.
4.1 Introduction
A C4-decomposition of G is also known as a 4-cycle system of order G. A C4-
decomposition of Kv is said to be a 4-cycle system of order v and is denoted by 4CS(v). It
is already known that the spectrum of 4CS(v) is precisely the set of all v ? 1 (mod 8) [13].
In this chapter we consider a class of 4-cycle systems with diagonally switchable property.
In order to define diagonally switchable property, first let (a,b,c,d) denote the 4-cycle
induced by the edge set {{a,b},{b,c},{c,d},{d,a}}. The 4-cycle (a,b,c,d) is said to have
diagonals {a,c} and {b,d}. Using the four points a,b,c,d two more new 4-cycles (a,c,b,d)
and (a,b,d,c) can be constructed by replacing, respectively, each pair of non-adjacent edges
of the original 4-cycle (a,b,c,d) by its diagonals. We will call such transformations diagonal
switches (see figure 4.1).
A 4-cycle system (V,F) of G is said to be diagonally switchable if each element of I
can be replaced by one of its diagonal switches to get a new set of 4-cycles ?F such that
(V, ?F) is an another 4-cycle system of G (we use ?F throughout the rest of the chapter to
denote the set of 4-cycles formed from I after performing diagonal switches, which produce
another 4-cycle system).
37
ab
c
d
ab
c
d
ab
c
d
b c
a
d
a
d
Figure 4.1: Diagonal Switches
A 4-cycle system (V,F) of Kv in which F is diagonally switchable is denoted by
DS4CS(v). A pair of 4-cycles (a,b,c,d) and (aprime,bprime,cprime,dprime) is said to have a double-diamond
configuration D if they have a common diagonal. In order DS4CS(v) to exist, no two
4-cycles in the original 4CS(v) can share a diagonal as all diagonals of the original 4-cycle
system become edges of the transformed system. So diagonally switchable 4-cycle decompo-
sitions must be double-diamond avoiding decompositions. Configurations in 4-cycle systems
were studied by Bryant, Grannell, Griggs and Ma?caj; among other results they proved the
following theorem [5].
Theorem 4.1. There exists a double-diamond-avoiding 4CS(v) for all v ? 1 (mod 8).
The existence spectrum of DS4CS(v)s was determined by Adams, Bryant, Grannell
and Griggs [1]. In this chapter we give an alternative proof of their result. This construction
not only solves the case for Kv in a more efficient way, but is also powerful enough to easily
prove a new result, considering the case for Kv ? F, where F is any 1-factor of Kv. The
constructions used here are recursive in nature, requiring fewer special cases than the proof
in [1]. The basic building blocks in our constructions are holey self-orthogonal latin squares
38
or holey SOLS. The method is then applied to the releated problem of finding 4-cycle systems
of Kv ?F with the diagonally switchable property using self-orthogonal latin squares.
A self-orthogonal latin square of order v, or SOLS(v) is a latin square of order v which
is orthogonal to its transpose. It is well known [4] that an SOLS(v) exists for all values of
v, v negationslash= 2, 3, or 6.
Let V be a set and H = {H1,H2,...,Hk} be a set of nonempty subsets which partitions
the set V. A holey SOLS or HSOLS of type hn11 hn22 ...hnkk is an ordered pair L = (V,?) of
order |V| = v =
summationdisplay
1?i?k
nihi in which:
(1) every cell of L is either empty or contains a symbol of V;
(2) every symbol of V occurs at most once in any row or column of L;
(3) the subarrays Hi ? Hi are empty for 1? i ? k (these subarrays are referred to as
holes);
(4) the symbol x ? V occurs in a row or column y if and only if (x,y) ? (V ? V) \
?ki=1(Hi ?Hi);
(5) the superposition of L with its transpose yields every ordered pair in (V ? V) \
?ki=1(Hi ?Hi).
We briefly denote a holey SOLS of type hn11 hn22 ...hnkk by HSOLS(hn11 hn22 ...hnkk ). Finding
necessary and sufficient conditions for the existence of HSOLS(hn11 hn22 ...hnkk ) is still an
open problem. For the purposes of our proof the following results are sufficient.
Theorem 4.2.
(1) For h ? 2, there exists an HSOLS(hn) if and only if n ? 4 [17] .
(2) Suppose that n, u are positive integers and u negationslash= 12. Then there exists an HSOLS(12nu1)
if and only if n ? 4 and n ? 1+u/6 (Theorem7.1 in [20]).
39
4.2 Preliminary Results
We begin with a result from [1], where each system referred to in the following result is
constructed explicitly (they also constructed systems of order 177 and 209 but these special
cases are not needed in the constructions presented here).
Lemma 4.3. [1] For all v ? 1 (mod 8) with 25 ? v ? 137, v negationslash= {97,121,129}, there exists
a DS4CS(v).
The following result was known to the authors of [1] but was accidentally omitted in
[1].
Lemma 4.4. There does not exist a diagonally switchable 4-cycle system of order 9.
Proof. First note that, there are only 8 non-isomorphic 4CS(9)s [7], of which seven have
double-diamond configurations. In view of the discussion in the introduction, there is, there-
fore only one candidate for being diagonally switchable, namely (V,F) = (Z9,{(0,1,5,2)+i |
i ? Z9}), where each sum is reduced modulo 9.
Observe that F contains the 4-cycles (0, 1, 5, 2), (5, 6, 1, 7) and (8, 0, 4, 1). No matter
how (8, 0, 4, 1) is switched, the resulting 4-cycle contains the edge {0, 1}. So (0, 1, 5, 2)
must be switched to (0, 5, 1, 2) (not switched to (0, 5, 2, 1)). But this 4-cycle contains the
edge {5, 1} and hence when the 4-cycle (5, 6, 1, 7) is switched, the edge {5, 1} is covered
twice. Hence there does not exist a DS4CS(9).
4.3 Constructions
We consider three cases in turn, v ? 1 (mod 24) and v ? 97, v ? 9 (mod 24) and
v ? 129, and v ? 17 (mod 24) and v ? 161.
40
4.3.1 Case A: v = 24s+1,s ? 4.
We begin with a construction of a 4CS(v). To deal with this case we need HSOLS(12s)
s ? 4, which is known to exist (see Theorem 4.2).
The 24s + 1 Construction. Let s ? 4. Let V = {{?}? (Z12s ?{1,2})} and let G
be a copy of K24s+1 defined on the vertex set V. Let (Z12s,?) be a HSOLS(12s) having the
hole set H = {Hi | i ? Zs} where Hi = {12i,12i+1,...,12i+11}. Define a collection F of
copies of 4-cycles as follows.
(1) Type 1: For each i ? Zs, let
Si = ({?}?(Hi ?{1,2}),Fi) be a DS4CS(25) (see Lemma 4.3).
Let Fi ? F.
(2) Type 2: For each {a,b} ? Z12s, {a,b} negationslash? Hi and for each i ? Zs, let
((a,1),(b,1),(a?b,2),(b?a,2)) ? F.
Proposition 4.3.1. The 24s+1 Construction produces a diagonally switchable 4CS(24s+
1).
Proof. The total number of 4-cycles in a 4-cycle system of order v = 24s+1 is parenleftbigv2parenrightbig/4 =
3s(24s+1). We begin by counting the number of 4-cycles in F.
The number of Type 1 4-cycles is clearly summationtexti?Zs75|Fi| = 75s. For each {a,b} ? Z12s,
{a,b} negationslash? Hi there are parenleftbig12s2 parenrightbig?sparenleftbig122parenrightbig= 72s(s?1) choices for a and b. Therefore |F| = 75s +
72s(s?1) = 3s(24s+1) as required.
To see (V,F) is a 4-cycle system, it remains to show that each edge e in E(K24s+1)
occurs in some 4-cycle in F. If e = {?,(x,j)} or {(x,1),(y,1)}, or {(x,1),(y,2)} where
{x,y} ? Hi for i ? Zs and 1 ? j ? 2 then e occurs in a Type 1 cycle. Now suppose
{x,y} negationslash? Hi for i ? Zs. Clearly {(x,1),(y,1)} occurs in a Type-2 cycle. If e = {(x,1),(y,2)}
41
then e occurs in the Type 2 cycle ((x,1),(b,1),(x?b,2),(b?x,2)) where b is chosen to satisfy
b?x = y. If e = {(x,2),(y,2)} then e occurs in the Type 2 cycle ((a,1),(b,1),(a?b,2),(b?
a,2)) where a and b are chosen by the self-orthogonal property (5) to satisfy a?b = x and
b?a = y.
To see that (V,F) is diagonally switchable, observe that by replacing Fi with ?Fi for
each i ? Zs, and replacing each 4-cycle ((a,1),(b,1),(a?b,2),(b?a,2)) by ((a,1),(b,1),(b?
a,2),(a ? b,2)) for each {a,b} ? Z12s, {a,b} negationslash? Hi for i ? Zs, we get a new set of 4-cycles
?F which can be seen to form another 4-cycle system of K24s+1 using essentially the same
proof that showed (V,F) is a 4-cycle system.
4.3.2 Case B: v = 24s+9,s ? 5.
We beginwithaconstructionofa4CS(v). Todealwiththis caseweneedHSOLS(12s?1161)
s?1 ? 4, which is known to exist (see Theorem 4.2).
The 24s+9 Construction. Let s ? 5. Let V = {{?}?(Z12s+4?{1,2})} and let G be
a copy of K24s+9 defined on the vertex set V. Let (Z12s+4,?) be a HSOLS(12s?1161) s?1 ?
4 having the hole set H = {Hi | i ? Zs} where Hs?1 = {12s ? 12,12s ? 11,...,12s + 3}
and Hi = {12i,12i + 1,...,12i + 11} for each i ? Zs?1. Define a collection F of copies of
4-cycles as follows.
(1) Type 1: Let Ss?1 = ({?}?(Hs?1 ?{1,2}),Fs?1) be a DS4CS(33), and
for each i ? Zs?1, let Si = ({?}?(Hi?{1,2}),Fi) be a DS4CS(25)(see Lemma 4.3).
Let Fi ? F for each i ? Zs.
(2) Type 2: For each {a,b} ? Z12s+4, {a,b} negationslash? Hi and for each i ? Zs, let
((a,1),(b,1),(a?b,2),(b?a,2)) ? F.
42
Proposition 4.3.2. The 24s+9 Construction produces a diagonally switchable 4CS(24s+
9).
Proof. The total number of 4-cycles in a 4-cycle system of order v = 24s+9 is parenleftbigv2parenrightbig/4 =
(3s+1)(24s+9). We begin by counting the number of 4-cycles in F.
The number of Type 1 4-cycles is clearly summationtexti?Zs?175|Fi| + |Fs?1| = 75(s ? 1)+132 =
75s+57. For each {a,b} ? Z12s+4, {a,b} negationslash? Hi there are parenleftbig12s+42 parenrightbig? (s ? 1)parenleftbig122parenrightbig?parenleftbig162parenrightbig =
72s2 ? 24s ? 48 choices for a and b. Therefore |F| = 75s+57+ 72s2 - 24s - 48 = (3s+1)
(24s+9) as required.
To see (V,F) is a 4-cycle system, it remains to show that each edge e in E(K24s+9)
occurs in some 4-cycle in F. If e = {?,(x,j)} or {(x,1),(y,1)}, or {(x,1),(y,2)} where
{x,y} ? Hi for i ? Zs and 1 ? j ? 2 then e occurs in a Type 1 cycle. Now suppose
{x,y} negationslash? Hi for i ? Zs. Clearly {(x,1),(y,1)} occurs in a Type-2 cycle. If e = {(x,1),(y,2)}
then e occurs in the Type 2 cycle ((x,1),(b,1),(x?b,2),(b?x,2)) where b is chosen to satisfy
b?x = y. If e = {(x,2),(y,2)} then e occurs in the Type 2 cycle ((a,1),(b,1),(a?b,2),(b?
a,2)) where a and b are chosen by the self-orthogonal property (5) to satisfy a?b = x and
b?a = y.
To see that (V,F) is diagonally switchable, observe that by replacing Fi with ?Fi for
each i ? Zs, and replacing each 4-cycle ((a,1),(b,1),(a?b,2),(b?a,2)) by ((a,1),(b,1),(b?
a,2),(a?b,2)) for each {a,b} ? Z12s+4, {a,b} negationslash? Hi for i ? Zs, we get a new set of 4-cycles
?F which can be seen to form another 4-cycle system of K24s+9 using essentially the same
proof that showed (V,F) is a 4-cycle system.
4.3.3 Case C: v = 24s+17,s ? 6.
We beginwithaconstructionofa4CS(v). Todealwiththis caseweneedHSOLS(12s?1201)
s?1 ? 5, which is known to exist [20].
43
The 24s + 17 Construction. Let s ? 6. Let V = {{?}?(Z12s+8 ?{1,2})} and let
G be a copy of K24s+17 defined on the vertex set V. Let (Z12s+8,?) be a HSOLS(12s?1201)
s?1 ? 5 having the hole set H = {Hi | i ? Zs} where Hs?1 = {12s?12,12s?11,...,12s+7}
and Hi = {12i,12i + 1,...,12i + 11} for each i ? Zs?1. Define a collection F of copies of
4-cycles as follows.
(1) Type 1: Let Ss?1 = ({?}?(Hs?1 ?{1,2}),Fs?1) be a DS4CS(41), and
for each i ? Zs?1, let Si = ({?}?(Hi?{1,2}),Fi) be a DS4CS(25)(see Lemma 4.3).
Let Fi ? F for each i ? Zs.
(2) Type 2: For each {a,b} ? Z12s+8, {a,b} negationslash? Hi and for each i ? Zs, let
((a,1),(b,1),(a?b,2),(b?a,2)) ? F.
Proposition 4.3.3. The 24s+17 Construction produces a diagonally switchable 4CS(24s+
17).
Proof. The total number of 4-cycles in a 4-cycle system of order v = 24s + 17 is
parenleftbigv
2
parenrightbig/4 = (3s+2)(24s+17). We begin by counting the number of 4-cycles in F.
The number of Type 1 4-cycles is clearly summationtexti?Zs?175Fi + |Fs?1| = 75(s ? 1)+205 =
75s+130. For each {a,b} ? Z12s+8, {a,b} negationslash? Hi there are parenleftbig12s+82 parenrightbig? (s ? 1)parenleftbig122parenrightbig?parenleftbig202parenrightbig =
72s2+24s?96 choices for a and b. Therefore |F| = 75s+130+ 72s2+ 24s-96 = 72s2+99s+34
= (3s+2) (24s+17) as required.
To see (V,F) is a 4-cycle system, it remains to show that each edge e in E(K24s+17)
occurs in some 4-cycle in F. If e = {?,(x,j)} or {(x,1),(y,1)}, or {(x,1),(y,2)} where
{x,y} ? Hi for i ? Zs and 1 ? j ? 2 then e occurs in a Type 1 cycle. Now suppose
{x,y} negationslash? Hi for i ? Zs. Clearly {(x,1),(y,1)} occurs in a Type-2 cycle. If e = {(x,1),(y,2)}
then e occurs in the Type 2 cycle ((x,1),(b,1),(x?b,2),(b?x,2)) where b is chosen to satisfy
b?x = y. If e = {(x,2),(y,2)} then e occurs in the Type 2 cycle ((a,1),(b,1),(a?b,2),(b?
44
a,2)) where a and b are chosen by the self-orthogonal property (5) to satisfy a?b = x and
b?a = y.
To see that (V,F) is diagonally switchable, observe that by replacing Fi with ?Fi for
each i ? Zs, replacing, and replacing each 4-cycle ((a,1),(b,1),(a ? b,2),(b ? a,2)) by
((a,1),(b,1),(b ? a,2),(a ? b,2)) for each {a,b} ? Z12s+8, {a,b} negationslash? Hi for i ? Zs, we get a
new set of 4-cycles ?F which can be seen to form another 4-cycle system of K24s+17 using
essentially the same proof that showed (V,F) is a 4-cycle system.
4.3.4 The Main Result
Now we will state and prove the main theorem
Theorem 4.5. There exists a diagonally switchable 4-cycle system of order v (DS4CS(v))
if and only if v ? 1 (mod 8),v ? 17, with the possible exception of v = 17.
Proof. In view of Lemmas 4.3 and 4.4, we can assume v ?145 or v ? {97, 121, 129}.
Let v = 24s + h where h ? {1,9,17}. If h = 1 then use s ? 4, which implies that
v ? 1 (mod 24) and v ? 97 which is covered by Case A. If h = 9 then use s ? 5, which
implies that v ? 9 (mod 24) and v ? 129 which is covered by Case B. If h = 17 then use
s ? 6, which implies that v ? 17 (mod 24) and v ? 161, which is covered by Case C.
4.4 Decompositions of Kv ?I
Now we will use the same proof technique to decompose Kv ?I into diagonally switch-
able 4-cycles, where I is any 1-factor of Kv. The basic building blocks in our constructions
are self-orthogonal latin squares or SOLS.
Theorem 4.6. There exists a 4-cycle system of Kv ? I having the diagonally switchable
property if and only if v is even and v negationslash? {4,6}.
45
Proof. To prove the necessary condition first note that in order to have a 1-factor v
has to be even. Secondly observe that any 4-cycle in K4?I is going to cover both the edges
of the 1-factor after the diagonal switch. Hence K4?I cannot have a diagonally switchable
4-cycle system.
Now consider K6 ? I where I is any 1-factor of K6. Let I = {{a,b},{c,d},{e,f}}
be any 1-factor of K6. Let (V,F) be any diagonally switchable 4-cycle system of K6 ? I.
Clearly a and b cannot be in the same 4-cycle in F, since {a,b} cannot be an edge in any
4-cycle nor in any of their diagonal switches. Similarly c,d and e,f cannot be in the same
4-cycle. Now consider the 4-cycle containing the edge {e,d}, by the above observation that
4-cycle cannot have c and f as it?s vertices. Therefore it should contain the edge {a,b}, a
contradiction. Hence K6 ?I has no diagonally switchable 4-cycle system.
In order to prove the sufficiency we now consider two cases.
Case A: v = 12.
In the following construction, in any ordered pair reduce arithmetic operations modulo
5 in the second component. Let V = {{?1,?2} ? (Z5 ? {1,2})} and let G be a copy
of K12 ? I defined on the vertex set V where I = {{(i,1),(i,2)} | i ? Z5} and define a
collection F of copies of 4-cycles as follows (see figure 4.2).
(1) Type 1: for each i ? Z5, let
C1(i) = ((i,1),(i+1,1),(i+4,1),(i+2,2)) ? F.
(2) Type 2: for each i ? Z5, let
C2(i) = (?1,(i+1,2),(i+2,2),(i+3,1)) ? F.
(3) Type 3: for each i ? Z5, let
C3(i) = (?2,(i+1,2),(i+3,2),(i+2,1)) ? F.
46
(0,1
)
(1,1
)
(1,2
)
(0,2
)
(2,1
)
(3,1
)
(4,1
)
(4,2
)
(3,2
)
(2,2
)
?
1
?
2
C
1
(i)
C
2
(i)
C
3
(i)
Figure 4.2: 4-cycle system of K12 ?I
Now we prove that this construction produces a 4-cycle system of K12 ?I. We begin
by counting the number of 4-cycles in F. There are five 4-cycles of each type. The total
number of 4-cycles in a 4-cycle system of K12?I is (parenleftbig122parenrightbig?6)/4 = 15. Hence |F| = 3.5 = 15
as required.
To see (V,F) is a 4-cycle system, it remains to show that each edge e in E(K12 ? I)
occurs in some 4-cycle in F. If e = {?i,(x,j)} with x ? Z5 and 1 ? i,j ? 2 then e
occurs in some Ci+1(k). If e = {(x,1),(y,1)} with x,y ? Z5 then e occurs in some C1(k).
If e = {(x,1),(x + 2,2)} with x ? Z5 then e occurs in C1(x). If e = {(x,1),(x + 1,2)}
with x ? Z5 then e occurs in C3(x ? 2). If e = {(x,2),(x + 1,1)} with x ? Z5 then e
occurs in C2(x ? 2). If e = {(x,2),(x + 2,1)} with x ? Z5 then e occurs in C1(x ? 2). If
e = {(x,2),(x + 1,2)} with x ? Z5 then e occurs in C2(x ? 1). If e = {(x,2),(x + 2,2)}
with x ? Z5 then e occurs in C3(x?1).
To prove (V,F) is diagonally switchable, observe that no two 4-cycles in F share a
diagonal. Now by replacing each C1(i) = ((i,1),(i + 1,1),(i + 4,1),(i + 2,2)) ? C with
Cprime1(i) = ((i,1),(i+4,1),(i+1,1),(i+2,2)), and replacing each C2(i) = (?1,(i+1,2),(i+
47
2,2),(i + 3,1)) ? C with Cprime2(i) = (?1,(i + 2,2),(i + 1,2),(i + 3,1)), and each C3(i) =
(?2,(i+1,2),(i+3,2),(i+2,1)) ? C with Cprime3(i) = (?2,(i+3,2),(i+1,2),(i+2,1)), we
get a new set of 4-cycles ?F (see figure 4.3).
It is easy to check that (V, ?F) forms another 4-cycle system.
(0,1
)
(1,1
)
(1,2
)
(0,2
)
(2,1
)
(3,1
)
(4,1
)
(4,2
)
(3,2
)
(2,2
)
?
1
?
2
C?
1
(i)
C?
2
(i)
C?
3
(i)
Figure 4.3: DS4CS(K12 ?I)
Case B: v negationslash= 4, 6, 12
Let V = Zv/2 ?{1,2} and let G be a copy of Kv ?I defined on the vertex set V where
I = {{(i,1),(i,2)} | i ? Zv/2}. Let (Zv/2,?) be a SOLS(v/2) (this is known to exist since
v is even and v negationslash= 4, 6, 12). Define a collection F of copies of 4-cycles as follows. For each
{a,b} ? Zv/2, let ((a,1),(b,1),(a?b,2),(b?a,2)) ? F.
Now we prove that this construction produces a 4-cycle system of Kv ? I. The total
number of 4-cycles in a 4-cycle system of Kv ?I is (parenleftbigv2parenrightbig?(v/2))/4 = v(v?2)/8. We begin
by counting the number of 4-cycles in F.
48
For each {a,b} ? Zv/2, there are parenleftbigv/22 parenrightbig choices for a and b. Therefore |F| = v(v ?2)/8
as required. Using the same argument as in the proof of Proposition 4.3.3, it is easy to see
that each edge e of Kv ?I is in a 4-cycle in F.
Tosee (V,F)is diagonallyswitchable, observethatbyreplacingeach4-cycle ((a,1),(b,1),(a?
b,2),(b?a,2)) by ((a,1),(b,1),(b?a,2),(a?b,2)) for each {a,b} ? Zv/2, we get a new set
of 4-cycles ?F which can be easily seen to form another 4-cycle system of Kv/2 ?I.
49
Bibliography
[1] Peter Adams, Darryn Bryant, Mike Grannell and Terry Griggs, Diagonally switchable
4-cycle systems, Australasian Journal of Combinatorics, Volume 34 (2006), 145-152.
[2] B. Alspach and H. Gavlas, Cycle Decompositions of Kn and Kn ?I, Journal of Com-
binatorial Theory, Series B 81, 77-99 (2001).
[3] J. C. Bermond and J. Sch?onheim, G-decompositions of Kn, where G has four vertices
or less, Discrete Math. 19 (1977), 113-120.
[4] R. K. Brayton, D. Coppersmith and A. J. Hoffman, Self-Orthogonal latin squares, Coll.
Int. Th. Comb., Rome, 1973, Atti del Convegni Lincei No. 17, 1976, 509-517.
[5] D. E. Bryant, M. J. Grannell, T. S. Griggs and M. Ma?caj, Configurations in 4-cycle
systems, Graphs Combin. 20 (2004), 161-179.
[6] C. J. Colbourn and J. H. Dinitz (eds), Handbook of Combinatorial Designs, 2nd edition,
Chapman and Hall/CRC, 2007, 477-486.
[7] I. J. Dejter, P. I. Rivera-Vega and A. Rosa, Invarients for 2-Factoizations and Cycle
Systems, JCMCC 16 (1994), 129-152.
[8] J. Doyen, Sur la structure de certains syst`emes triple de Steiner, Math. Z. 111 (1969),
289-300.
[9] S. I. El-Zanati and C. A. Rodger, Blocking sets in G-designs. Ars Combin. 35 (1993),
237?251.
[10] H. Hanani, On Quadruple Systems, Canad. J. Math. 12 (1960), 145-157.
[11] D. G. Hoffman, C. C. Lindner, and C. A. Rodger, On the construction of odd cycle
systems, J. Graph Th. 13 (1989), 417-426.
[12] Rev. T. P. Kirkman, ?On a problem in combinatorics?, Camb. and Dublin Math. J. 2
(1847), 191-204.
[13] C. C. Lindner and C. A. Rodger, Decompositions into cycles II: cycle systems, Con-
temporary Design Theory: A Collection of Surveys (J. Dinitz and D. Stinson eds),
Wiley, 1992.
[14] E. Mendelsohn and K.T.Phelps, Simple Steiner quadruple systems, Ann. Discrete
Math. 15 (1982), 293-304.
50
[15] C. A. Rodger and E. Spicer, Minimum coverings, J. Combin. Des., 8 (2000), 22-34.
[16] M. ?Sajna, Cycle decompositions. III. Complete graphs and fixed length cycles, J. Com-
bin. Des. 10 (2002), no. 1, 27?78.
[17] D. R. Stinson and L. Zhu, On the existence of certain SOLS with holes, J. Combin,
Math. Combin. Computing 15 (1994), 33-45.
[18] Michael Tarsi, Decomposition of a complete multigraph into simple paths: Nonbalanced
Handcuffed Designs, Journal of Combinatorial Theory, Series A 34, 60-70 (1983).
[19] Michael Tarsi, Decompositions of complete multigraphs into stars, Discrete Math. 26
(1979), 273-278.
[20] Y. Xu, H. Zhang and L. Zhu, Existence of frame SOLS of type anb1, Discrete Math.
250 (2002), 211-230.
51