# Definitions and Preliminaries

Let us begin with a few basic definitions.

Definition 2.1   The complete graph on n vertices is denoted by Kn, and Kn - Idenotes the complete graph on n vertices with a 1-factor I removed.

Definition 2.2   We write if G is the edge-disjoint union of the subgraphs H1 and H2. If , where , then the graph G can be decomposed into subgraphs isomorphic to H and we say that G is H-decomposable. We also shall write .

Our first goal in proving these two results is to determine bounds on the value of n in terms of m. In [7], 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 [1], it is sufficient to consider only values of n in the range of .

Lemma 2.3   Let m and n be positive even integers satisfying . If Kn - I can be decomposed into cycles of length m for all n in the range of with , then Kn - I can be decomposed into cycles of length m for all with .

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 [10], Sotteau proved that and , where Cm denotes the cycle of length m. In [9], 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.

Lemma 2.4   If m, n, and r are positive even integers such that n = m + r and , then the following hold:
and or .

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. Suppose that , say r = 8k+4 for some nonnegative integer k. Then

or

Now evenly, say mt = r(r - 2)/2 for some positive even integer t. Since , we have that

Next suppose that , say r = 8k+6 for some nonnegative integer k. Thus

or

As before, let mt = r(r - 2)/2 for some positive even integer t. Since , we have that

producing a contradiction. Thus . Hence or .

We shall use Cayley graphs, in particular, circulant graphs, for the proofs of Theorems 1.1 and 1.2. Accordingly, we define them now.

Definition 2.5   Let S be a subset of a finite group satisfying
1.
, where 1 denotes the identity of , and
2.
S=S-1, that is, implies that .
A subset S satisfying the above conditions is called a Cayley subset. The Cayley graph is defined to be that graph whose vertices are the elements of and there is an edge between vertices g and h if and only if h=gs for some . We call S the connection set and say that is a Cayley graph on the group .

Definition 2.6   A Cayley graph is called a circulant graph when is a cyclic group. For a cyclic group of order n, we will write X(n; S) for .

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.

Definition 2.7   Let be a permutation of the vertex set V of a graph G. For any subset U of V, acts as a function from U to V by considering the restriction of to U. If H is a subgraph of G with vertex set U, then is a subgraph of G provided that for each edge , . In this case, has vertex set and edge set .

Note that may not be defined for all subgraphs H of G since is not necessarily an automorphism.

Definition 2.8   If G and H are vertex-disjoint graphs, then the join of G and H, denoted , is that graph obtained by taking the union of G and Htogether with all possible edges having one end in G and the other end in H.

Definition 2.9   Let P be a path, say . The odd vertices of Pare those vertices that are encountered first, third, fifth, etc., that is, those vertices of P with an odd subscript, and the even vertices of P are those vertices that are encountered second, fourth, sixth, etc., that is, those vertices of P with an even subscript.

Brian &
2000-01-20