Definitions and Preliminaries

Let us begin with a few basic definitions.

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

Definition 2.2   We write $G = H_1 \oplus H_2$ if G is the edge-disjoint union of the subgraphs H₁ and H₂. If $G= H_1 \oplus H_2 \oplus \cdots \oplus H_k$, where $H_1 \cong H_2 \cong \ldots \cong H_k \cong H$, then the graph G can be decomposed into subgraphs isomorphic to H and we say that G is H-decomposable. We also shall write $H\;\vert\;G$.

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 $m \le n \le 3m$. 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 $m \le n < 2m$.

Lemma 2.3   Let m and n be positive even integers satisfying $4\leq m\leq n$. If K_n - I can be decomposed into cycles of length m for all n in the range of $m \le n < 2m$ with $n(n-2)\equiv 0({\rm mod}\ 2m)$, then K_n - I can be decomposed into cycles of length m for all $n \ge m$ with $n(n-2)\equiv 0({\rm mod}\ 2m)$.

PROOF.Suppose that K_n - I can be decomposed into m-cycles whenever $n(n-2)\equiv 0({\rm mod}\ 2m)$ and $m \le n < 2m$. Let m and n be positive even integers such that $n(n-2)\equiv 0({\rm mod}\ 2m)$. Write n=qm+r for integers q and rwith $0\le r<m$. Observe that $n(n-2)\equiv 0({\rm mod}\ 2m)$ implies that $r(r-2)\equiv 0({\rm mod}\ 2m)$ as well. Partition the vertex set of K_n-I into q-1 sets of m vertices and one set of m+r vertices. Each set of vertices induces a subgraph isomorphic to K_m or K_m+r, and the edges between any two sets induce a subgraph isomorphic to K_m,mor K_m,m+r. In [10], Sotteau proved that $C_m\;\vert\;K_{m,m}$ and $C_m\;\vert\;K_{m,m+r}$, where C_m denotes the cycle of length m. In [9], Walecki gives a decomposition of K_m into m-cycles and a 1-factor. Since $(m+r)(m+r-2)\equiv 0({\rm mod}\ 2m)$, the edges of K_m+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 $n(n-2)\equiv 2m({\rm mod}\ 4m)$, then the following hold:

$m \equiv 0 ({\rm mod}\ 4)$ and $r \equiv 0 ({\rm mod}\ 8)$ or $r \equiv 2 ({\rm mod}\ 8)$.

PROOF.First, $n(n-2)\equiv 2m({\rm mod}\ 4m)$ implies that n(n-2)/2 is an odd multiple of m, say $m\ell = n(n-2)/2$ for some positive odd integer $\ell$. 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 $\ell$ 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 $\ell$is odd and 4 divides m, it follows that m divides r(r - 2)/2 evenly. Suppose that $r \equiv 4 ({\rm mod}\ 8)$, say r = 8k+4 for some nonnegative integer k. Then

$$\frac{r(r - 2)}{2} = \frac{(8k+4)(8k+2)}{2} = 32k^2 + 24k + 4 = 4(8k^2 + 6k + 1),$$

or

$$\frac{r(r - 2)}{8}= 8k^2 + 6k + 1.$$

Now $m \;\vert\; r(r - 2)/2$ evenly, say mt = r(r - 2)/2 for some positive even integer t. Since $4\;\vert\; m$, we have that

$$\frac{m}{4}\ t = \frac{r(r - 2)}{8} = 8k^2 + 6k + 1,$$

producing a contradiction. Thus $r \not\equiv 4 ({\rm mod}\ 8)$.

Next suppose that $r \equiv 6 ({\rm mod}\ 8)$, say r = 8k+6 for some nonnegative integer k. Thus

$$\frac{r(r - 2)}{2} = \frac{(8k+6)(8k+4)}{2} = 32k^2 + 40k + 12 = 4(8k^2 + 10k + 3),$$

or

$$\frac{r(r - 2)}{8}= 8k^2 + 10k + 3.$$

As before, let mt = r(r - 2)/2 for some positive even integer t. Since $4\;\vert\; m$, we have that

$$\frac{m}{4}\ t = \frac{r(r - 2)}{8} = 8k^2 + 10k + 3,$$

producing a contradiction. Thus $r\not\equiv 6 ({\rm mod}\ 8)$. Hence $r \equiv 0 ({\rm mod}\ 8)$ or $r \equiv 2 ({\rm mod}\ 8)$.

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 $\Gamma$ satisfying

1.

$1\not\in S$, where 1 denotes the identity of $\Gamma$, and

2.

S=S^-1, that is, $s\in S$ implies that $s^{-1}\in S$.

A subset S satisfying the above conditions is called a Cayley subset. The Cayley graph $X(\Gamma;S)$ is defined to be that graph whose vertices are the elements of $\Gamma$ and there is an edge between vertices g and h if and only if h=gs for some $s\in S$. We call S the connection set and say that $X(\Gamma;S)$ is a Cayley graph on the group $\Gamma$.

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

Equivalently, for a positive integer n, let $S\subseteq\{1,2,\ldots,n-1\}$ satisfy $s\in S$ implies that $n-s\in S$. Then the circulant graph X(n;S) is that graph whose vertices are $u_0,u_1,\ldots,u_{n-1}$ with an edge between u_iand u_j if and only if $j-i\in S$. 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 $\rho$ be a permutation of the vertex set V of a graph G. For any subset U of V, $\rho$ acts as a function from U to V by considering the restriction of $\rho$ to U. If H is a subgraph of G with vertex set U, then $\rho(H)$ is a subgraph of G provided that for each edge $xy\in E(H)$, $\rho(x)\rho(y)\in E(G)$. In this case, $\rho(H)$ has vertex set $\rho(U)$ and edge set $\{\rho(x)\rho(y): xy\in E(H)\}$.

Note that $\rho(H)$ may not be defined for all subgraphs H of G since $\rho$ is not necessarily an automorphism.

Definition 2.8   If G and H are vertex-disjoint graphs, then the join of G and H, denoted $G\bowtie H$, 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 $P = v_1, v_2, v_3, \ldots, v_n$. 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.