Let us begin with a few basic definitions.
Our first goal in proving these two results is to determine bounds on the value of n in terms of m. In , it is shown that for m and n odd, it is sufficient to consider values of m and nwith . For m and n even, we begin by showing, as in , it is sufficient to consider only values of n in the range of .
PROOF.Suppose that Kn - I can be decomposed into m-cycles whenever and . Let m and n be positive even integers such that . Write n=qm+r for integers q and rwith . Observe that implies that as well. Partition the vertex set of Kn-I into q-1 sets of m vertices and one set of m+r vertices. Each set of vertices induces a subgraph isomorphic to Km or Km+r, and the edges between any two sets induce a subgraph isomorphic to Km,mor Km,m+r. In , Sotteau proved that and , where Cm denotes the cycle of length m. In , Walecki gives a decomposition of Km into m-cycles and a 1-factor. Since , the edges of Km+r can be decomposed into m-cycles and a 1-factor by supposition. This completes the proof.
The conditions of Theorem 1.1 have some surprising consequences, as we now shall see.
PROOF.First, implies that n(n-2)/2 is an odd multiple of m, say for some positive odd integer . Next since n and n-2 are both even, it follows that 4 divides n or n-2 and thus 8 divides n(n-2). Therefore, 4 divides n(n-2)/2 and since is odd, we have that 4 divides m as well.
We now show that r is congruent to 0 or 2 modulo 8. First, since is odd and 4 divides m, it follows that m divides
r(r - 2)/2 evenly.
say r =
8k+4 for some nonnegative integer k. Then
Next suppose that
say r = 8k+6 for some
nonnegative integer k. Thus
We shall use Cayley graphs, in particular, circulant graphs, for the proofs of Theorems 1.1 and 1.2. Accordingly, we define them now.
Equivalently, for a positive integer n, let satisfy implies that . Then the circulant graph X(n;S) is that graph whose vertices are with an edge between uiand uj if and only if . We will often write -s for n-swhen n is understood.
Many of our decompositions arise from the action of a permutation on a fixed subgraph. The next definition makes this precise.
Note that may not be defined for all subgraphs H of G since is not necessarily an automorphism.