4-cycle Systems of Line Graphs of Complete Multipartite Graphs
Except where reference is made to the work of others, the work described in this thesis is
my own or was done in collaboration with my advisory committee. This thesis does not
include proprietary or classified information.
Nidhi Sehgal
Certificate of Approval:
Dean G Hoffman
Professor
Mathematics and Statistics
Chris A Rodger, Chair
Professor
Mathematics and Statistics
Charles C Lindner
Professor
Mathematics and Statistics
George T. Flowers
Interim Dean
Graduate School
4-cycle Systems of Line Graphs of Complete Multipartite Graphs
Nidhi Sehgal
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulfillment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
August 9, 2008
4-cycle Systems of Line Graphs of Complete Multipartite Graphs
Nidhi Sehgal
Permission is granted to Auburn University to make copies of this thesis 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
Nidhi Sehgal was born on January 27th 1984, in a small town named Jallandhar, in
North India. She grew up in the coastal city of Mumbai on the West coast of India. She
completed her high school education at Conossa Convent, Mumbai. She then went on to
pursue her Bachelor of Science at St. Xavier?s College in Mumbai. She studied at five
educational institutions due to the nature of her father?s profession. This exposed her to
the flavor of India and she learnt from such a diverse experience. Then she came to Auburn
University, to pursue her doctoral studies in Mathematics, at the Mathematics department
of the Auburn University.
Nidhi has also learnt Indian Classical dance (Bharatnattyam) for a period of eight
years. She is interested in learning various art forms and travelling. She also loves to teach
and enjoys cooking in her free time.
iv
Thesis Abstract
4-cycle Systems of Line Graphs of Complete Multipartite Graphs
Nidhi Sehgal
Master of Science, August 9, 2008
(B.S., St. Xavier?s College, Mumbai University, 2005)
29 Typed Pages
Directed by Chris A Rodger
Here we investigate the necessary and sufficient conditions for the existence of 4 - cycle
systems of the line graphs of complete multipartite graphs.
v
Acknowledgments
The author is greatly indebted to her Master?s advisor Dr. Chris A. Rodger for his
valuable guidance and inpiration. She would like to thank him for his patient endurance and
support in times of dificulties without which it would be very difficult for her to complete
this work. Also, she would like to thank her committee members Dr. Dean Hoffman and
Dr. Charles C Lindner for their support. She is thankful to her grandfather, parents, sister-
in-law and brother for their understanding and moral support. Finally she also expresses
her gratitude towards her friends who have always been here for her.
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
I dedicate this work to maa and papa for their unflagging support.
viii
Table of Contents
List of Figures x
1 Introduction 1
1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Necessary Conditions 4
3 all parts even all parts odd: odd number of parts 7
4 All parts odd:even number of parts 10
4.1 Line Graphs of Kn ?Ku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 4-cycle system of L(K(1,1,...,1,8x + 1)), p negationslash= 6 . . . . . . . . . . . . . . . . 14
4.3 4-cycle system of L(K(1,1,...,1,8x + 1)), p = 6 . . . . . . . . . . . . . . . . 16
5 Conclusion 18
Bibliography 19
ix
List of Figures
3.1 4-cycle system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.1 F(1): 1 factor of K8x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 F(2): 1 factor of K8x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 F(3): 1-factor of K8x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.4 F(4): 1-factor of K8x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
x
Chapter 1
Introduction
1.1 Definitions
An m-cycle system of a graph G is a set of m-cycles, the edges in which partition the
edge set of G. The line graph of a graph G = (V,E) is the graph L(G) = (E,E1) where
E1 is the set of edges that join two vertices if and only if the corresponding edges in G
are adjacent. The complete multipartite graph K(a1,a2,...,ap) is the graph with vertex
set partitioned into parts {V1,V2,...,Vp}, with |Vi| = ai, in which two vertices in E are
adjacent if and only if they are in different parts. By solving this problem we investigate
the existence of 4-cycle systems of L(K(a1,a2,...,ap)).
1.2 History
There is a long history of problems in this area. In a more general context, Dudeney [3]
posed the following problem of seating n people at a dinner table on consecutive evenings so
that no person was ever to have the same pair of neighbors more than once. Any solution to
this problem is equivalent to finding a set of hamilton cycles of Kn with the property that
each 2-path in Kn occurs in exactly one hamilton cycle. This problem was solved when n is
even by Kobayashi, Kiyasu-Zen?iti and Nakamura[7], and some results exist when n is odd.
And this set S of 4-cycles is known as the Dudeney set. This result was extended further
by looking at the case when each pair of people is a neighbor twice. Which was equal to
1
finding a set of hamilton cycles of Kn such that each two path in Kn occurs in exactly two
hamilton cycles. And this was solved by Midori, Mutoh, Kiyasu-Zen?iti and Nakamura[9].
It is quite conceivable that the restaurant has many tables of a small size, say m, instead
of just one big table. So it is natural to solve the related problem of finding a set of 2-factors
in Kn, each cycle in each 2-factor having length m, such that each 2-path in Kn occurs in
exactly one m-cycle. This problem was solved by Kobayashi and Nakamura when k = 4
[8]. Notice that in any solution to such a problem, taking the line graph of each 4-cycle
produces a 4-cycle system of L(Kn). In [6], Henrich and Nonay removed the requirement
that the set of 4-cycles be resolvable (partitionable into 2-factors), finding necessary and
sufficient conditions for the existence of a set of 4-cycles such that each 2-path is in exactly
one 4-cycle; this provides a 4-cycle system of L(Kn) with the property that every 4-cycle
in L(Kn) corresponds to a 4-cycle in Kn.
In the same spirit Colby and Rodger[2] found necessary and sufficient conditions for the
existence of a 4-cycle system of L(Kn); when n ? 1 (mod 8) no solutions can correspond to
the existence of set of 4-cycles in Kn such that each 2-path in Kn is in exactly one 4-cycle.
The reader may be interested in a related problem posed by Dudeney [3].Twelve meme-
bers of a club arranged to play bridge of eleven evenings, but no player was ever to have the
same partner more than once or the same opponent more than twice. And the question was
to find a scheme of seating them at three tables every evening. By dropping the require-
ment that each player partner each other player atmost once, the solution was equivalent
to finding a set S of 4-cycles of K12 with the property that each 2-path in K12 occurs in
exactly two 4-cycles. And taking the line graph of each 4-cycle in S produces a 4-cycle
system of 2L(K12).
2
In this paper, we extend these results in the literature by investigating the existence of
a 4-cycle system of K(a1,a2,...,ap).
1.3 Notation
Throughout this paper, letG = K(a1,a2,...,ap). For 1 ? i ? pletVi = {vi,1,vi,2,...,vi,ai}.
So the vertex set of L(G) is {{vi,x,vj,y} | 1 ? x ? ai,1 ? y ? aj,1 ? i < j ? p}. Define
n =summationtext1?i?p ai to be the number of vertices in G. It will be useful to define hatwidestaiaj = n?ai?aj.
3
Chapter 2
Necessary Conditions
In this chapter we investigate some neat necessary conditions which we conjecture are
sufficient.
Lemma 2.1 If there exists a 4-cycle system of L(G) then
1. ai ? aj (mod 2) for 1 ? i < j ? p, and
2. If ai is odd for 1 ? i ? p then,
(a) p ? 1(mod 8) if p is odd, and
(b) p ? n(mod 8) if p is even.
Proof. The degree of each vertex in L(G) is clearly
d({vi,x,vj,y}) = ai +aj ?2 + 2hatwidestaiaj
since in G there are aj ?1 + hatwidestaiaj edges incident with vi,x and ai ?1+ hatwidestaiaj edges incident
with vj,y. Since we are assuming that a 4-cycle system of L(G) exists, each vertex in L(G)
must have even degree. Therefore, we conclude that ai ? aj (mod 2) and so condition (1)
is necessary.
Now suppose that ai is odd for 1 ? i ? p. We consider the cases where p is odd and
even in turn.
Case (1) If p is odd then clearly n is odd, being the sum of an odd number of odd
numbers. Since there exists a 4-cycle system of L(G), the number of edges in L(G) must
4
be divisible by 4. Each vertex in Vi in G is incident with n ? ai edges. By considering,
adjacent pairs of edges at each vertex in G in turn it follows that
|E(L(G))| =
psummationdisplay
i=1
(ai(n?ai)(n?ai ?1))/2.
So, 8 must divide
2|E(L(G))| =
psummationtext
i=1
(ain2)?2
psummationtext
i=1
(na2i) +
psummationtext
i=1
(a3i) +
psummationtext
i=1
(a2i)?
psummationtext
i=1
(nai)
= n3 ?(2n?1)
psummationtext
i=1
(a2i) +
psummationtext
i=1
(a3i)?n2. (?)
Notice that, since ai is odd we can write
ai = 8z + l for some l ? {1,3,5,7}
so, a2i = 64z2 + 16zl +l2,
so, a2i ? 1 (mod 8)
This also implies that a3i = a2iai ? ai (mod 8). Similarly, since n is also odd we can see
that n2 ? 1(mod 8) and n3 ? n (mod 8). Thus from (*), we can say that mod 8:
0 ? 2|E(L(G))| ? (n?(2n?1)p+n?1) = ((2n?1)(1?p)).
So clearly p ? 1 (mod 8). Hence condition (2a) is necessary.
Case (2) Now supose that p is even and therefore, n is also even. Clearly n3 ? 0 (mod
8).
Again we know that 2|E(L(G))| is divisible by 8 and so, from (*) we have mod 8:
5
0 ? 2|E(L(G))|
? (0?(2n?1)p+n?n2)
? (?(2n?1)p?n)
? (p?n)
which implies that p ? n (mod 8), thus proving that condition (2b) is necessary.
6
Chapter 3
all parts even
all parts odd: odd number of parts
In this chapter, we first show that the necessary conditions in Lemma 2.1 are sufficient
when all vertices in G have even degree. Then we deal with the case when all parts are odd
and there is an odd number of parts.
We begin with some useful decompositions. In [10] Sajna proved the necessary and
sufficient conditions for the even length cycle decomposition of Kn when n is odd. Also,
in [11] Sotteau proved a result regarding even length cycle decompositions of the complete
graph Kx,y These results were a more general solution to the following lemma, which is easy
to obtain for 4-cycles.
Lemma 3.1 There exists a 4-cycle system of:
1. Kn if and only if n ? 1 (mod 8), and
2. Of the complete bipartite graph Kx,y if and only if x and y are even.
In [1] Cavenagh and Billington investigated the necessary and sufficient conditions for
the existence of an edge-disjoint decomposition of any complete multipartite graph into
4-cycles. The next result is again part of a more general result, and again follows quite
readily from Lemma 3.1.
Theorem 3.1 [1] There exists a 4-cycle system of G if and only if
1. All parts have even size, or
7
2. All parts have odd size and p ? 1 (mod 8).
The last result we need now is well known, but easy to prove here. Let K ?F be the
graph formed from the graph K by removing the edges in F.
Lemma 3.2 There exists a 4-cycle system of Kn ?F for any even n and any 1-factor F.
Proof. Let n = 2x. Let the vertex set of Kn be {1,2,...,x}?{1,2}. The following
4-cycles form the required 4-cycle system:
{((a,1),(b,1),(a,2),(b,2)) | 1 ? a < b ? x}.
Figure 3.1: 4-cycle system
We are now ready to consider 4-cycle systems of L(G).
Theorem 3.2 There exists a 4-cycle system of L(G) if
1. ai is even for 1 ? i ? p, or
8
2. ai is odd for 1 ? i ? p and p ? 1(mod 8).
Proof. The edges of L(G) can be partitioned into sets that induce complete graphs,
namely the complete graphs K(vi,x) with vertex set {{vi,x,vj,y} | 1 ? y ? aj and 1 ? j ?
p,j negationslash= i} for each vertex vi,x in V(G). So the edges in K(vi,x) correspond to all the 2-paths
in G with middle vertex vi,x.
By Theorem 3.1, there exists a 4-cycle system B of G. Consider the set of 4-cycles S
in L(G) formed by taking the line graph of each 4-cycle in B. For each vertex vi,x in V(G),
the edges in K(vi,x) contained in 4-cycles in S form a 1-factor F(vi,x) of K(vi,x) (to see
this, observe that the 4-cycles in P pair the edges incident with vi,x in V(G), and each such
pair produces an edge in K(vi,x) which is vertex-disjoint from the other such pairs).
Also, each such complete graph has even order, so by Lemma 3.2 there exists a 4-cycle
system T(vi,x) of K(vi,x)?F(vi,x).
So the union of the T(vi,x) over all the vertices vi,x in V(G) together with the 4-cycles
in S produce the required 4-cycle system.
9
Chapter 4
All parts odd:even number of parts
4.1 Line Graphs of Kn ?Ku
In this chapter we make progress in tackling the difficult last case, solving a problem
that is of interest in its own right. Much progress solving existence problems for graph
designs has been made by using decompositions of complete graphs with holes; that is, of
Kn ? Ku. Such decompositions are now of interest in their own right. This is a graph in
the family we are considering in this paper, namely the graph G with ap = u, and ai = 1
for 1 ? i ? p?1, and p = n?u+1. We begin with a result by Henrich and Nonay referred
to in the introduction. Throughout this chapter we deal with the case where ai is odd for
1 ? i ? p and p is even.
Theorem 4.1 [6] Let p be even. There exists a 4-cycle system of L(Kp).
We shall also use some of the results by Fu, Fu and Rodger regarding 4-cycle systems
of Kn - E(F) and 2Kn - E(F) for all 2 regular subgraphs F.
Theorem 4.2 [4, 5] There exists a 4-cycle system of Kz ?P for any graph P of maximum
degree at most 3 if and only if
1. z is odd,
2. the number of edges in Kz ?P is divisible by 4, and
3. if z = 8x+1 then P is not one of two exceptional graphs, both of which are 3-regular.
10
We will use this result several times, including the following corollary. Let Cz denote
a cycle of length z.
Corollary 4.1 There exists a 4-cycle system of Kz ?P if:
1. z ? 1 (mod 8) and P = ?,
2. z ? 3 (mod 8) and P = C3,
3. z ? 5 (mod 8), z negationslash= 5, and P = C6, and
4. z ? 7 (mod 8) and P = C5.
Our final preparatory result is needed just for the case when p = 6. Form the graph
G?H from G?H by joining each vertex in G to each vertex in H.
Lemma 4.1 There exists a set F = {F(1),...,F(4)} of four 1-factors in K8x for which
there exists a 4-cycle system of (K8x ?F)?K1.
Proof. Let the vertex set be (Z4 ?Z2 ?Zx)?{v}. The required cycle system can be
formed by taking:
1. F(k) = {{(j,0,i),(j +k,1,i)} | j ? Z4,i ? Zx} for each k ? {1,2,3},
2. F(4) = {{(j,k,i),(j + 2,k,i)} | j,k ? Z2,i ? Zx},
3. B(1) = {((0,0,i),(1,0,i),(2,0,i),(3,0,i)),(v,(j,0,i),(j,1,i),(j + 1,1,i)) | j ? Z4,
i ? Zx}, and
4. A 4-cycle system B(y,z) of K8,8 with bipartition {{Z4 ?Z2 ?{y}},{Z4 ?Z2 ?{z}}
for 0 ? y < z < x (see Lemma 3.1).
11
Figure 4.1: F(1): 1 factor of K8x
Figure 4.2: F(2): 1 factor of K8x
12
Figure 4.3: F(3): 1-factor of K8x
Figure 4.4: F(4): 1-factor of K8x
13
We are now ready to find 4-cycle systems of L(Kn?Ku), which we state in the following
form. By Lemma 2.1, u ? 1 (mod 8) is a necessary condition when p is even. The case
where p is odd is handled in the previous chapter.
4.2 4-cycle system of L(K(1,1,...,1,8x + 1)), p negationslash= 6
Theorem 4.3 There exists a 4-cycle system of L(G) if p is even, ai = 1 for 1 ? i ? p?1
and ap = 8x+ 1.
Proof. Let Vj = {t(j)} for 1 ? j ? p ? 1 and let Vp = {t(0),s(i) | 1 ? i ? 8x}. For
each vertex w ? V(G), let K(w) be the complete subgraph of L(G) induced by the vertex
set {{w,wprime} | wprime ? V(G) \ {w}}. So K(w) contains p ? 1 vertices if w ? Vp, and K(w)
contains p + 8x ? 1 vertices otherwise. For 1 ? j ? p ? 1 it will also be useful to define
Kprime(t(j)) to be the subgraph of K(t(j)) induced by the vertices in {{t(j),s(i)} | 1 ? i ? 8x}.
If p = 2 then L(G) is isomorphic to K8x+1, and if x = 0 then L(G) is isomorphic to
K1, so the result follows from Lemma 2.1.
Now assume that x ? 1 and p ? 4. We will handle the case p = 6 last, so for now
assume that p negationslash= 6. Let F = {F(i) | 1 ? i ? 3} be a set of 3 edge disjoint 1-factors in K8x
defined on the vertex set {1,2,...,8x}. The construction contains 5 types of 4-cycles.
Type 1. Let B(1) be a 4-cycle system of L(Kp) in which Kp is defined on the vertex
set {t(j) | 0 ? j ? p?1}. This exists by Theorem 4.1.
Type 2. For 1 ? i ? 8x let B(2,i) be a 4-cycle system of K(s(i)) ? C(s(i)), where
C(s(i)) is the cycle ({s(i),t(1)},{s(i),t(2)},...,{s(i),t(?)}), and where ? = 0,3,6 or 5
14
when p ? 1 ? 1,3,5 or 7 (mod 8) respectively. Such a 4-cycle system exists by Corollary
4.1. Notice that since p negationslash= 6, p?1 ? ?, so K(s(i))?C(s(i)) is well defined.
Type 3. If ? > 0 then define the following 4-cycle systems. For 1 ? i ? 8x, al-
ternately color the edges of C(s(i)) with 1 and 2, except if ? is odd then the last edge
{{s(i),t(1)},{s(i),t(?)}} is colored 3; so the same proper edge-coloring is used on each of
the 8x cycles. For each edge {{s(i),t(j)},{s(i),t(j+1)}} (reducing j+1 mod ?) in C(s(i))
colored k, form the 4-cycle ({s(i),t(j)},{s(i),t(j+1)},{s(i1),t(j+1)},{s(i1),t(j)}), where
{i,i1} is the edge incident with vertex i in F(k). (This same 4-cycle is defined again when
i1 is used instead of i, but we only use it once, of course, in the following union.) Let B(3)
be the union of all such 4-cycles. Note that the edges in the 4-cycles in B(3) contain:
1. All the edges in C(s(i)) for 1 ? i ? 8x, and
2. The edges in a 2-factor R(t(j)) of Kprime(t(j)) for 1 ? j ? ?.
The second property holds since, when j ? ?, for each vertex {t(j),s(i)} in Kprime(t(j)), the two
4-cycles containing the edges {{s(i),t(j?1)},{s(i),t(j)}}, and {{s(i),t(j)},{s(i),t(j+1)}}
(reducing sums mod?) colored sayaandbalso contain the 2 edges{{t(j),s(i)},{t(j),s(ia)}},
and {{t(j),s(i)},{t(j),s(ib)}} where {i,ia} and {i,ib} are edges in F(a) and F(b) respec-
tively. So by this explanation, in fact R(t(j)) is isomorphic to F(a) ? F(b). If j > ? or if
p?1 ? 1 (mod 8) (this is the case where ? = 0) then define R(t(j)) = ?.
Type 4. For 1 ? j ? p ? 1, let B(4,j) contain the 4-cycles in a 4-cycle system
of K8x+1 ? R(t(j)) defined on the vertex set V(Kprime(t(j))) ? {{t(j),t(0)}}. This exists by
Theorem 4.2 since:
1. Each vertex has degree 8x or 8x?2 which is even,
15
2. The number of edges is (8x+1)4x if R(t(j)) = ? and is (8x+1)4x?8x = (8x?1)4x
otherwise, so is divisible by 4, and
3. R(t(j)) for 1 ? j ? ? is not one of the exceptional graphs since it is 2-regular.
Type 5. For 1 ? j ? p ? 1 let B(5,j) be a 4-cycle system of the complete bipar-
tite graph Kp?2,8x with bipartition of the vertex set {{{t(j),t(z)} | 1 ? z ? p ? 1,z negationslash=
j},V(Kprime(t(j)))}. This exists by condition (2) of Lemma 3.1.
Then
B(1)?(?1?i?8xB(2,i))?B(3)?(?1?j?p?1B(4,j))?(?1?j?p?1B(5,j))
provides the required 4-cycle system.
4.3 4-cycle system of L(K(1,1,...,1,8x + 1)), p = 6
Finally, suppose that p = 6. The difficulty here is that the Type 2 4-cycles must be
different because it is impossible to fit a 6-cycle in a graph with only 5 vertices. This can be
overcome by the use of 4 1-factors in Kprime(t(1)), for example. Nevertheless, the construction
is very similar, so a brief description follows, again defining the five types of 4-cycles in turn.
If the same set of cycles is used, we simply state that. In this case, let {F(1),...,F(4)} be
a copy of the 4 1-factors defined in Lemma 4.1 on the vertex set {1,2,...,8x}.
Type 1. Same as before.
16
Type 2. Let B(2) = {({s(i),t(2)},{s(i),t(4)},{s(i),t(3)},{s(i),t(5)}) | 1 ? i ? 8x}.
Let C(s(i)) be the set of 6 edges occurring in no 4-cycle in B(2) (these edges induce two
copies of K3 with one vertex in common).
Type 3. For 1 ? i ? x, properly color the edges of C(s(i)) with the 4 colors in
{1,2,3,4}. For each edge {{s(i),v1},{s(i),v2}} in C(s(i)) colored k, form the 4-cycle
({s(i),t(j)},{s(i),t(j +1)},{s(i1),t(j +1)},{s(i1),t(j)}), where {i,i1} is the edge incident
with vertex i in F(k). These 4-cycles use the edges forming:
1. a 4-factor R(t(1)) isomorphic to ?1?k?4F(k) in Kprime(t(1)), and
2. for 2 ? j ? 5 a 2-factor R(t(j)) in Kprime(f(j)), each being isomorphic to the union of
two of these four 1-factors.
Type 4. For 1 ? j ? p ? 1, let B(4,j) contain the 4-cycles in a 4-cycle system of
K8x+1 ? R(t(j)) defined on the vertex set V(Kprime(t(j))) ? {{t(j),t(0)}}. This exists by
Lemma 4.1 if j = 1 and by Theorem 4.2 otherwise.
Type 5. Same as before.
17
Chapter 5
Conclusion
By pooling all the results in this thesis we see that there exists a 4-cycle system of the
line graph of G for the following cases:
1. All parts are even.
2. All parts are odd and
(a) p ? 1 (mod 8), when p is odd
(b) ai = 1 for 1 ? i ? p?1 and ap = 8x +1, when p is even,
Finally, we conjecture the following:
Conjecture 5.1 There exists a 4-cycle system of the line graph of G for the following case:
1. All parts are odd and p is even.
18
Bibliography
[1] N. J. Cavenagh and E. J. Billington, Decomposition of complete multipartite graphs
into cycles of even length, Graphs Combin., 16 (2000), 49?65.
[2] M. Colby and C.A. Rodger, Cycle Decompositions of the Line Graph of Kn, J. Combin.
Theory (A), 62 (1993), 158?161.
[3] H. E. Dudeney, Amusements in Mathematics, Dover, New York, 1959.
[4] C. M. Fu, H. L. Fu, C. A. Rodger and T. Smith, All graphs with maximum degree 3
whose complements have a 4-cycle decomposition, Discrete Math., to appear.
[5] H. L. Fu and C. A. Rodger, Four-cycle systems with two-regular leaves, Graphs Com-
bin., 17 (2001), 457?461.
[6] K. Henrich and G. Nonay, Exact coverings of 2-paths by 4-cycles, J. Combin. Theory
(A), 45 (1987), 50?61.
[7] M. Kobayashi, Kiyasu-Zen?iti and G. Nakamura, A solution of Dudeney?s round table
problem for an even number of people, J. Combin. Theory (A), 63 (1993), 26?42.
[8] M. Kobayashi and G. Nakamura, Resolvable coverings of 2-paths by 4-cycles. J. Com-
bin. Theory (A), 60 (1992), 295?297.
[9] Midori, N. Mutoh, Kiyasu-Zen?iti and G. Nakamura, Double coverings of 2-paths by
hamilton cycles. J. Combin. Des., 10 (2002), no. 3, 195?206.
[10] M. Sajna, Cycle decompositions III. Complete graphs and fixed length cycles, J. Com-
bin. Des., 10 (2002), 27?78.
[11] D. Sotteau, Decomposition of Km,n(K?m,n) into cycles (circuits) of length 2k, J. Combin.
Theory (B), 30 (1981), 75?81.
[12] D. Hoffman, David Pike, 4-Cycle decompositions of the cartesian product of two com-
plete graphs, Journal of Combin. Math. and Combin. Computing 28 (1998) 215-226.
19