On the directed Oberwolfach problem
for complete symmetric equipartite digraphs
and uniform-length cycles

Nevena Francetić and Mateja Šajna¹¹1Email: [email protected]. Phone: +1-613-562-5800 ext. 3522. Mailing address: Department of Mathematics and Statistics, University of Ottawa, 150 Louis-Pasteur Private, Ottawa, ON, K1N 6N5,Canada.
University of Ottawa

Abstract

We examine the necessary and sufficient conditions for a complete symmetric equipartite digraph $K_{n[m]}^{\ast}$ with $n$ parts of size $m$ to admit a resolvable decomposition into directed cycles of length $t$ . We show that the obvious necessary conditions are sufficient for $m,n,t\geq 2$ in each of the following four cases: (i) $m(n-1)$ is even; (ii) $\gcd(m,n)\not\in\{1,3\}$ ; (iii) $\gcd(m,n)=1$ and $4|n$ or $6|n$ ; and (iv) $\gcd(m,n)=3$ , and if $n=6$ , then $p|m$ for a prime $p\leq 37$ .

Keywords: Complete symmetric equipartite digraph, resolvable directed cycle decomposition, directed Oberwolfach problem.

1 Introduction

The celebrated Oberwolfach problem (OP), posed by Ringel in 1967, asks whether $n$ participants at a conference can be seated at $k$ round tables of sizes $t_{1},t_{2},\ldots,t_{k}$ for several nights in row so that each participant sits next to everybody else exactly once. The assumption is that $n$ is odd and $n=t_{1}+t_{2}+\ldots+t_{k}$ . In graph-theoretic terms, OP $(t_{1},t_{2},\ldots,t_{k})$ asks whether $K_{n}$ admits a decomposition into 2-factors, each a disjoint union of cycles of lengths $t_{1},t_{2},\ldots,t_{k}$ . When $n$ is even, the complete graph minus a 1-factor, $K_{n}-I$ , is considered instead [19]. OP has been solved completely in the case that $t_{1}=t_{2}=\ldots=t_{k}$ [4, 5, 18], and in many other special cases (for example, for $k=2$ [29]; for $t_{1},t_{2},\ldots,t_{k}$ all even [10]; for $n\leq 60$ [2, 14, 15, 16, 27]; and for $n$ sufficiently large [17]), but is in general still open.

The Oberwolfach problem for the complete equipartite graph $K_{n[m]}$ with $n$ parts of size $m$ and uniform cycle lengths was completely solved by Liu, as stated below.

Theorem 1.1

[21] Let $t\geq 3$ and $n\geq 2$ . Then $K_{n[m]}$ admits a resolvable decomposition into cycles of length $t$ if and only if $t|mn$ , $m(n-1)$ is even, $t$ is even when $n=2$ , and $(m,n,t)\not\in\{(2,3,3),(6,3,3),(2,6,3),(6,2,6)\}$ .

The directed Oberwolfach problem was introduced in [12]. It asks whether $n$ participants can be seated at $k$ round tables of sizes $t_{1},t_{2},\ldots,t_{k}$ (where $n=t_{1}+t_{2}+\ldots+t_{k}$ ) for several nights in row so that each person sits to the right of everybody else exactly once. Such a seating is equivalent to a decomposition of $K_{n}^{*}$ , the complete symmetric digraph of order $n$ , into subdigraphs isomorphic to a disjoint union of directed cycles of lengths $t_{1},t_{2},\ldots,t_{k}$ . The solution to this problem for uniform cycle lengths has been completed very recently (see below), while very little is known about the non-uniform case.

Theorem 1.2

[9, 6, 1, 12, 11, 20, 28] Let $t\geq 2$ and $n\geq 2$ . Then $K_{n}^{*}$ admits a resolvable decomposition into directed cycles of length $t$ if and only if $t|n$ and $(n,t)\not\in\{(6,3),(4,4),(6,6)\}$ .

In this paper, we introduce the directed Oberwolfach problem for complete symmetric equipartite digraphs. As a scheduling problem, it asks whether the $nm$ participants at a conference, consisting of $n$ delegations of $m$ participants each, can be seated at round tables of sizes $t_{1},t_{2},\ldots,t_{k}$ (where $nm=t_{1}+t_{2}+\ldots+t_{k}$ ) so that over the course of $m(n-1)$ meals, every participant sits to the right of every participant from another delegation exactly once. Thus, we are asking about the existence of a decomposition of $K_{n[m]}^{*}$ , the complete symmetric equipartite digraph with $n$ parts of size $m$ , into subdigraphs, each a disjoint union of directed cycles of lengths $t_{1},t_{2},\ldots,t_{k}$ . Limiting our investigation to the uniform cycle length, we propose the following problem.

Problem 1.3

Determine the necessary and sufficient conditions on $m$ , $n$ , and $t$ for $K_{n[m]}^{*}$ to admit a resolvable decomposition into directed $t$ -cycles.

Apart from case $m=1$ (Theorem 1.2) and decompositions that follow directly from Theorem 1.1 (see Corollary 3.2 below), to our knowledge, the only previous contribution to Problem 1.3 is a partial solution for $t=3$ , as stated below.

Theorem 1.4

[7] The digraph $K_{n[m]}^{*}$ admits a resolvable decomposition into directed 3-cycles if and only if $3|mn$ and $(m,n)\neq(1,6)$ , with possible exceptions of the form $(m,6)$ , where $m$ is not divisible by any prime less than 17.

The main result of this paper is as follows.

Theorem 1.5

Let $m$ , $n$ , and $t$ be integers greater than 1, and let $g=\gcd(n,t)$ . Assume one of the following conditions holds.

(i)

$m(n-1)$ even; or
(ii)

$g\not\in\{1,3\}$ ; or
(iii)

$g=1$ , and $n\equiv 0\pmod{4}$ or $n\equiv 0\pmod{6}$ ; or
(iv)

$g=3$ , and if $n=6$ , then $m$ is divisible by a prime $p\leq 37$ .

Then the digraph $K_{n[m]}^{*}$ admits a resolvable decomposition into directed $t$ -cycles if and only if $t|mn$ and $t$ is even in case $n=2$ .

As we shall see, to complete Problem 1.3, it suffices to show that the obvious necessary conditions on $(m,n,t)$ are sufficient in the following two cases: (i) $(m,n,t)=(t,2p,t)$ for a prime $p\geq 5$ and odd prime $t$ ; and (ii) $(m,n,t)=(m,6,3)$ for a prime $m\geq 41$ .

This paper is organized as follows. In Section 2 we introduce the necessary terminology, and in Section 3 we solve the easiest case of Problem 1.3, that is, the case with $m(n-1)$ even. In Section 4 we present some smaller decompositions that help us address the rest of the problem. In Section 5, we solve the easy cases for $m(n-1)$ odd, and address the difficult cases in Sections 6–9. The proof of Theorem 1.5, as well as the outstanding cases of Problem 1.3, are summarized in Section 10.

2 Prerequisites

As usual, the vertex set and arc set of a directed graph (shortly digraph) $D$ will be denoted $V(D)$ and $A(D)$ , respectively. All digraphs in this paper are strict, that is, have no loops and no parallel arcs.

By $K_{n}$ , $\bar{K}_{n}$ , $K_{m,n}$ , $K_{n[m]}$ , and $C_{t}$ we denote the complete graph of order $n$ , the empty graph of order $n$ , the complete bipartite graph with parts of size $m$ and $n$ , the complete equipartite graph with $n$ parts of size $m$ , and the cycle of length $t$ ( $t$ -cycle), respectively. Analogously, by $K_{n}^{*}$ , $K_{m,n}^{*}$ , $K_{n[m]}^{*}$ , and $\vec{C}_{t}$ we denote the complete symmetric digraph of order $n$ , the complete symmetric bipartite digraph with parts of size $m$ and $n$ , the complete symmetric equipartite digraph with $n$ parts of size $m$ , and the directed cycle of length $t$ (directed $t$ -cycle), respectively. A $\vec{C}_{t}$ -factor of a digraph $D$ is a spanning subdigraph of $D$ that is a disjoint union of directed $t$ -cycles.

A decomposition of a digraph $D$ is a set $\{D_{1},\ldots,D_{k}\}$ of digraphs of $D$ such that $\{A(D_{1}),\ldots,A(D_{k})\}$ is a partition of $A(D)$ . A $D^{\prime}$ -decomposition of $D$ , where $D^{\prime}$ is a subdigraph of $D$ , is a decomposition into subdigraphs isomorphic to $D^{\prime}$ . A decomposition ${\mathcal{D}}=\{D_{1},\ldots,D_{k}\}$ of $D$ is said to be resolvable if ${\mathcal{D}}$ partitions into parallel classes, that is, sets $\{D_{i_{1}},\ldots,D_{i_{k_{i}}}\}$ such that $\{V(D_{i_{1}}),\ldots,V(D_{i_{k_{i}}})\}$ is a partition of $V(D)$ .

A $\vec{C}_{t}$ -factorization of $D$ is a decomposition of $D$ into $\vec{C}_{t}$ -factors, and it corresponds to a resolvable $\vec{C}_{t}$ -decomposition.

A decomposition, $C_{t}$ -factor, and $C_{t}$ -factorization of a graph are defined analogously.

The wreath product of digraphs $D_{1}$ and $D_{2}$ , denoted $D_{1}\wr D_{2}$ , is the digraph with vertex set $V(D_{1})\times V(D_{2})$ and arc set $A(D_{1}\wr D_{2})$ consisting precisely of all arcs of the form $\left((u_{1},u_{2}),(u_{1},v_{2})\right)$ where $(u_{2},v_{2})\in A(D_{2})$ , as well as all arcs of the form $\left((u_{1},u_{2}),(v_{1},v_{2})\right)$ where $(u_{1},v_{1})\in A(D_{1})$ .

It is not difficult to see that $K_{n}^{\ast}\wr K_{m}^{*}\cong K_{mn}^{*}$ and $K_{n}^{\ast}\wr\bar{K}_{m}\cong K_{n[m]}^{*}$ .

3 $\vec{C}_{t}$ -factorization of $K_{n[m]}^{*}$ : easy observations

Throughout this paper we shall assume that $m$ , $n$ , and $t$ are integers greater than 1. The obvious necessary conditions for the existence of a $\vec{C}_{t}$ -factorization of $K_{n}^{\ast}\wr\bar{K}_{m}$ are as follows:

(C1)

$t|mn$ , and
(C2)

$t$ is even when $n=2$ .

The following lemma, together with Theorem 1.1, will help us establish sufficiency in the case that $m(n-1)$ is even (Corollary 3.2 below).

Lemma 3.1

[12, 30] Let $t\geq 2$ be an even integer, and $\beta$ any positive integer. Then the digraph $K_{\beta\frac{t}{2},\beta\frac{t}{2}}^{\ast}$ admits a $\vec{C}_{t}$ -factorization.

Corollary 3.2

Let $m(n-1)$ be even, let $t\geq 2$ be such that $t|mn$ , and $t$ is even if $n=2$ . Then $K_{n[m]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization.

Proof. First, assume $t=2$ . The graph $K_{n[m]}$ admits a $C_{mn}$ -factorization by Theorem 1.1, and since $mn$ is even, it therefore admits a 1-factorization. Replacing each 1-factor in a 1-factorization of $K_{n[m]}$ with a $\vec{C}_{2}$ -factor results in a $\vec{C}_{2}$ -factorization of $K_{n[m]}^{\ast}$ .

Hence we may now assume $t\geq 3$ . If $(m,n,t)\not\in\{(2,3,3),(6,3,3),(2,6,3),(6,2,6)\}$ , then by Theorem 1.1, since $m(n-1)$ is even, there exists a $C_{t}$ -factorization of $K_{n[m]}$ . To obtain a $\vec{C}_{t}$ -factorization of $K_{n[m]}^{*}$ , we direct each cycle in this decomposition in both possible ways.

Theorem 1.4 guarantees existence of a $\vec{C}_{3}$ -factorization of $K_{n[m]}^{*}$ for $(m,n)\in\{(2,3),(6,3),$ $(2,6)\}$ .

Finally, let $(m,n,t)=(6,2,6)$ , so $K_{n[m]}^{*}\cong K_{6,6}^{\ast}$ . By Lemma 3.1, there exists a $\vec{C}_{6}$ -factorization of $K_{3,3}^{\ast}$ . It is easy to see that $K_{6,6}^{\ast}$ admits a resolvable decomposition into copies of $K_{3,3}^{\ast}$ . Hence $K_{6,6}^{\ast}$ admits a $\vec{C}_{6}$ -factorization. a

4 Some useful decompositions

In this section, we prove existence of some $\vec{C}_{t}$ -factorizations that will help us address Problem 1.3 in the cases not covered by Corollary 3.2.

Lemma 4.1

Let $t\geq 3$ and $p$ be an odd prime. Then the following hold.

(1)

There exists a $\vec{C}_{t}$ -factorization of $\vec{C}_{t}\wr\bar{K}_{p}$ .
(2)

There exists a $\vec{C}_{pt}$ -factorization of $\vec{C}_{t}\wr\bar{K}_{p}$ .
(3)

If $t$ is odd, then there exists a $\vec{C}_{t}$ -factorization of $\vec{C}_{t}\wr\bar{K}_{4}$ .

Proof. For any $s\in\mathbb{Z}^{+}$ , let the vertex set and arc set of $\vec{C}_{t}\wr\bar{K}_{s}$ be

V=\{x_{j,i}:j\in\mathbb{Z}_{t},i\in\mathbb{Z}_{s}\}\quad\mbox{ and }\quad A=\{(x_{j,i_{1}},x_{j+1,i_{2}}):j\in\mathbb{Z}_{t},i_{1},i_{2}\in\mathbb{Z}_{s}\},

respectively. We shall call an arc of the form $(x_{j,i},x_{j+1,i+d})$ , for $d\in\mathbb{Z}_{s}$ , an arc of $j$ -difference $d$ . Moreover, define a permutation $\rho$ on $V$ by

\rho=(x_{0,0}\,x_{0,1}\,\ldots x_{0,s-1})(x_{1,0}\,x_{1,1}\,\ldots x_{1,s-1})\ldots(x_{t-1,0}\,x_{t-1,1}\,\ldots x_{t-1,s-1}).

For Claims (1) and (2), we have $s=p$ , an odd prime, and we let $\delta=0$ for Claim (1), and $\delta=1$ for Claim (2). In both cases, as we show below, it suffices to find elements $d_{j}^{(i)}\in\mathbb{Z}_{p}$ , for $j\in\mathbb{Z}_{t}$ and $i\in\mathbb{Z}_{p}$ , such that

\sum_{j=0}^{t-1}d_{j}^{(i)}=\delta\qquad\mbox{for all }i\in\mathbb{Z}_{p},

(*)

and

d_{j}^{(0)},d_{j}^{(1)},\ldots,d_{j}^{(p-1)}\qquad\mbox{are pairwise distinct for each }j\in\mathbb{Z}_{t}.

If $t-1\not\equiv 0\pmod{p}$ , then we may choose

d_{0}^{(i)}=\ldots=d_{t-2}^{(i)}=i\qquad\mbox{ and }\qquad d_{t-1}^{(i)}=\delta-(t-1)i.

Otherwise, that is, if $t-1\equiv 0\pmod{p}$ , then $t-2\not\equiv 0\pmod{p}$ , and we choose

d_{0}^{(i)}=\ldots=d_{t-3}^{(i)}=i\qquad\mbox{ and }\qquad d_{t-2}^{(i)}=d_{t-1}^{(i)}=2^{-1}(\delta-(t-2)i).

(1)

Let $\delta=0$ and suppose we have $d_{j}^{(i)}\in\mathbb{Z}_{p}$ , for $j\in\mathbb{Z}_{t}$ and $i\in\mathbb{Z}_{p}$ , satisfying Condition $(*)$ . Fix $i\in\mathbb{Z}_{p}$ and define the following directed closed walk in $\vec{C}_{t}\wr\bar{K}_{p}$ :

$C^{(i)}=(x_{0,0},x_{1,d_{0}^{(i)}},x_{2,d_{0}^{(i)}+d_{1}^{(i)}},\ldots,x_{t-1,\sum_{j=0}^{t-2}d_{j}^{(i)}},x_{0,0}).$

It is easy to see that $C^{(i)}$ is in fact a directed $t$ -cycle. Since $\sum_{j=0}^{t-1}d_{j}^{(i)}=0$ , it contains exactly one arc of each $j$ -difference $d_{j}^{(i)}$ , for $j\in\mathbb{Z}_{t}$ .

Let $F^{(i)}=C^{(i)}\cup\rho(C^{(i)})\cup\ldots\cup\rho^{p-1}(C^{(i)})$ , and it can be verified that $F^{(i)}$ is a $\vec{C}_{t}$ -factor of $\vec{C}_{t}\wr\bar{K}_{p}$ . Moreover, the directed cycles in $F^{(i)}$ jointly contain all arcs of $j$ -difference $d_{j}^{(i)}$ , for all $j\in\mathbb{Z}_{t}$ .

Since for all $j\in\mathbb{Z}_{t}$ , we have that $d_{j}^{(0)},d_{j}^{(1)},\ldots,d_{j}^{(p-1)}$ are pairwise distinct, it follows that ${\mathcal{F}}=\{F^{(i)}:i\in\mathbb{Z}_{p}\}$ is a $\vec{C}_{t}$ -factorization of $\vec{C}_{t}\wr\bar{K}_{p}$ .

(2)

Now let $\delta=1$ and suppose we have $d_{j}^{(i)}\in\mathbb{Z}_{p}$ , for $j\in\mathbb{Z}_{t}$ and $i\in\mathbb{Z}_{p}$ , satisfying Condition $(*)$ . Fix $i\in\mathbb{Z}_{p}$ and define the following directed closed walk in $\vec{C}_{t}\wr\bar{K}_{p}$ :

$\displaystyle C^{(i)}$	$\displaystyle=$	$\displaystyle(x_{0,0},x_{1,d_{0}^{(i)}},x_{2,d_{0}^{(i)}+d_{1}^{(i)}},\ldots,x_{t-1,\sum_{j=0}^{t-2}d_{j}^{(i)}},$
		$\displaystyle x_{0,1},x_{1,1+d_{0}^{(i)}},x_{2,1+d_{0}^{(i)}+d_{1}^{(i)}},\ldots,x_{t-1,1+\sum_{j=0}^{t-2}d_{j}^{(i)}},$
		$\displaystyle\ldots,$
		$\displaystyle x_{0,p-1},x_{1,p-1+d_{0}^{(i)}},x_{2,p-1+d_{0}^{(i)}+d_{1}^{(i)}},\ldots,x_{t-1,p-1+\sum_{j=0}^{t-2}d_{j}^{(i)}},x_{0,0}).$

Since $\sum_{j=0}^{t-1}d_{j}^{(i)}=1$ , we have that $C^{(i)}$ is a directed $pt$ -cycle, and it contains all arcs of each $j$ -difference $d_{j}^{(i)}$ , for $j\in\mathbb{Z}_{t}$ .

Since for all $j\in\mathbb{Z}_{t}$ , we have that $d_{j}^{(0)},d_{j}^{(1)},\ldots,d_{j}^{(p-1)}$ are pairwise distinct, it follows that

{\mathcal{C}}=\{C^{(i)}:i\in\mathbb{Z}_{t}\}

is a $\vec{C}_{pt}$ -decomposition and hence a $\vec{C}_{pt}$ -factorization of $\vec{C}_{t}\wr\bar{K}_{p}$ .

Refer to caption — Figure 1: $\vec{C}_{t}$ -factors $F^{(0)},F^{(1)}$ (top), and $F^{(2)},F^{(3)}$ (bottom) in a $\vec{C}_{t}$ -factorization of $\vec{C}_{t}\wr\bar{K}_{4}$ for $t=5$ . (All arcs are oriented from left to right, and only the subscripts of the vertices are specified.)

(3)

We now have $s=4$ , and we define another permutation, $\tau$ , on $V$ by

\tau=(x_{0,0}\,x_{0,1})(x_{0,2}\,x_{0,3})(x_{1,0}\,x_{1,1})(x_{1,2}\,x_{1,3})\ldots(x_{t-1,0}\,x_{t-1,1})(x_{t-1,2}\,x_{t-1,3}).

Define the following directed $t$ -cycles in $\vec{C}_{t}\wr\bar{K}_{4}$ .

$\displaystyle C_{0}^{(0)}$	$\displaystyle=$	$\displaystyle(x_{0,0},x_{1,1},x_{2,0},x_{3,0},x_{4,0},x_{5,0},\ldots,x_{t-1,0},x_{0,0})$
$\displaystyle C_{0}^{(1)}$	$\displaystyle=$	$\displaystyle(x_{0,0},x_{1,2},x_{2,1},x_{3,0},x_{4,1},x_{5,0},\ldots,x_{t-1,1},x_{0,0})$
$\displaystyle C_{0}^{(2)}$	$\displaystyle=$	$\displaystyle(x_{0,0},x_{1,0},x_{2,2},x_{3,0},x_{4,2},x_{5,0},\ldots,x_{t-1,2},x_{0,0})$
$\displaystyle C_{0}^{(3)}$	$\displaystyle=$	$\displaystyle(x_{0,0},x_{1,3},x_{2,3},x_{3,0},x_{4,3},x_{5,0},\ldots,x_{t-1,3},x_{0,0})$

Then, for each $i\in\mathbb{Z}_{4}$ , let

C_{1}^{(i)}=\tau(C_{0}^{(i)}),\quad C_{2}^{(i)}=\rho^{2}(C_{0}^{(i)}),\quad\mbox{and}\quad C_{3}^{(i)}=\tau(C_{2}^{(i)}),

and let $F^{(i)}=C_{0}^{(i)}\cup C_{1}^{(i)}\cup C_{2}^{(i)}\cup C_{3}^{(i)}$ . Figure 1 illustrates the case $t=5$ . It is not difficult to verity that each $F^{(i)}$ is a $\vec{C}_{t}$ -factor in $\vec{C}_{t}\wr\bar{K}_{4}$ , and that $F^{(0)},\ldots,F^{(3)}$ , for each $j\in\mathbb{Z}_{t}$ , jointly contain exactly one arc of each $j$ -difference. Hence ${\mathcal{F}}=\{F^{(i)}:i\in\mathbb{Z}_{4}\}$ is a $\vec{C}_{t}$ -factorization of $\vec{C}_{t}\wr\bar{K}_{4}$ .

Corollary 4.2

Let $t\geq 3$ be an integer, and let $D$ be a digraph admitting a $\vec{C}_{t}$ -factorizaton. Let $s\geq 3$ be an odd integer, and $\ell$ a non-negative integer. Then the following hold.

(a)

The digraph $D\wr\bar{K}_{s}$ admits a $\vec{C}_{t}$ -factorizaton.
(b)

The digraph $D\wr\bar{K}_{s}$ admits a $\vec{C}_{st}$ -factorizaton.
(c)

If $t$ is odd, then the digraph $D\wr\bar{K}_{4^{\ell}s}$ admits a $\vec{C}_{t}$ -factorizaton.

Proof.

(a)

Let $\cal C$ be a $\vec{C}_{t}$ -factorizaton of $D$ , and take any odd prime $p|s$ . Then $\{F\wr\bar{K}_{p}:F\in\cal C\}$ is a decomposition of $D\wr\bar{K}_{p}$ into spanning subdigraphs whose connected components are isomorphic to $\vec{C}_{t}\wr\bar{K}_{p}$ . By Lemma 4.1(1), each such component admits a $\vec{C}_{t}$ -factorizaton. Therefore, $D\wr\bar{K}_{p}$ admits a $\vec{C}_{t}$ -factorizaton.

Since for primes $p$ and $p^{\prime}$ we have that $(D\wr\bar{K}_{p})\wr\bar{K}_{p^{\prime}}\cong D\wr\bar{K}_{pp^{\prime}}$ , repeating this process for all prime divisors of $s$ yields the desired result.
(b)

This is similar to (a), using Lemma 4.1(2).
(c)

This is similar to (a), using Lemma 4.1(1) and (3).

The above corollary shows how to “blow up the holes” in a $\vec{C}_{t}$ -factorizaton by either keeping the cycle length, or “blowing up” the cycle length by the same odd factor. Note that Statement (b) also follows from [24, Lemma 2.11], and Statement (a) can be obtained from [25, Corollary 5.7] by appropriately orienting each cycle.

5 $\vec{C}_{t}$ -factorizaton of $K_{n[m]}^{*}$ for $m$ odd, $n$ even: the easy cases

Proposition 5.1

Let $m$ , $n$ , and $t$ be integers greater than 1 with $m(n-1)$ odd, $t|mn$ , and $t$ even if $n=2$ . Furthermore, let $g=\gcd(n,t)$ . Then $K_{n[m]}^{\ast}$ admits a $\vec{C}_{t}$ -factorizaton in each of the following cases:

(1)

$g$ is even and $(g,n)\not\in\{(4,4),(6,6)\}$ ; and
(2)

$g$ is odd, $g\geq 3$ , and $(g,n)\neq(3,6)$ .

Proof. Recall that $K_{n[m]}^{\ast}\cong K_{n}^{\ast}\wr\bar{K}_{m}$ . From the assumptions on $m$ , $n$ , and $t$ it follows that $m$ is odd, $n$ is even, $\frac{t}{g}$ is odd and divides $m$ , and $\frac{mg}{t}$ is odd as well.

(1)

Let $g$ be even. Assume first that $g\geq 4$ . Since $g|n$ and $(g,n)\not\in\{(4,4),(6,6)\}$ , by Theorem 1.2, there exists a $\vec{C}_{g}$ -factorizaton of $K_{n}^{\ast}$ . Hence, by Corollary 4.2(b), there exists a $\vec{C}_{t}$ -factorizaton of $K_{n}^{\ast}\wr\bar{K}_{\frac{t}{g}}$ . Finally, by Corollary 4.2(a), there exists a $\vec{C}_{t}$ -factorizaton of $K_{n}^{\ast}\wr\bar{K}_{m}$ .

Now let $g=2$ , which implies $\frac{t}{2}|m$ . Since $n$ is even, $K_{n}$ admits a 1-factorization. Consequently, $K_{n}^{\ast}\wr\bar{K}_{m}$ admits a resolvable decomposition into copies of $K_{m,m}^{\ast}$ . Since $\frac{t}{2}|m$ , by Lemma 3.1, there exists a $\vec{C}_{t}$ -factorizaton of $K_{m,m}^{\ast}$ . Therefore, $K_{n}^{\ast}\wr\bar{K}_{m}$ admits a $\vec{C}_{t}$ -factorizaton.
(2)

Let $g$ be odd, $g\geq 3$ .

First, assume $g=3$ and $n\neq 6$ . By Theorem 1.4, there exists a $\vec{C}_{3}$ -factorizaton of $K_{n}^{\ast}\wr\bar{K}_{\frac{3m}{t}}$ . Hence by Corollary 4.2(b), there exists a $\vec{C}_{t}$ -factorizaton of $K_{n}^{\ast}\wr\bar{K}_{m}$ .

Finally, let $g\geq 5$ . Since $g|n$ , by Theorem 1.2, there exists a $\vec{C}_{g}$ -factorizaton of $K_{n}^{\ast}$ . Hence by Corollary 4.2(b), there exists a $\vec{C}_{t}$ -factorizaton of $K_{n}^{\ast}\wr\bar{K}_{\frac{t}{g}}$ , and thus by Corollary 4.2(a), there exists a $\vec{C}_{t}$ -factorizaton of $K_{n}^{\ast}\wr\bar{K}_{m}$ .

Note that Proposition 5.1 leaves open only the following cases of Problem 1.3 with $m$ odd, $n$ even, and $g=\gcd(n,t)$ : case $g=1$ and cases $(g,n)\in\{(3,6),(4,4),(6,6)\}$ .

6 $\vec{C}_{t}$ -factorizaton of $K_{n[m]}^{*}$ for $m$ odd, $n$ even: the case $\gcd(n,t)=1$

The following lemma and its corollary will allow us to reduce this case to a few crucial subcases, namely, to subcases $n=4$ , $n=8$ , and $n=2p$ for an odd prime $p$ .

Lemma 6.1

Let $t\geq 3$ be odd, $n_{1}\geq 3$ , and $n_{2}=4^{\ell}s$ for some integer $\ell\geq 0$ and odd integer $s\geq 1$ . Assume that both $K_{n_{1}[t]}^{\ast}$ and $K_{n_{2}[t]}^{\ast}$ admit $\vec{C}_{t}$ -factorizations. Then $K_{n_{1}n_{2}[t]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization.

Proof. As $K_{n_{1}[t]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization, by Corollary 4.2(c), so does $K_{n_{1}[t]}^{\ast}\wr\bar{K}_{4^{\ell}s}\cong K_{n_{1}[4^{\ell}st]}^{\ast}$ . Since $K_{n_{1}n_{2}[t]}^{\ast}\cong K_{n_{1}}^{\ast}\wr K_{n_{2}[t]}^{\ast}$ decomposes into $K_{n_{1}[4^{\ell}st]}^{\ast}$ and $n_{1}$ pairwise disjoint copies of $K_{n_{2}[t]}^{\ast}$ , which by assumption admits a $\vec{C}_{t}$ -factorization, we conclude that $K_{n_{1}n_{2}[t]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization. a

Corollary 6.2

Let $t$ be odd, $t\geq 3$ .

(1)

Assume that each of $K_{4[t]}^{\ast}$ and $K_{8[t]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization. Then there exists a $\vec{C}_{t}$ -factorization of $K_{n[t]}^{\ast}$ for all $n\equiv 0\pmod{4}$ .
(2)

Let $p$ be an odd prime, and assume that $K_{2p[t]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization. Then there exists a $\vec{C}_{t}$ -factorization of $K_{n[t]}^{\ast}$ for all $n=2ps$ with $s$ odd.
(3)

Assume there exists a $\vec{C}_{t}$ -factorization of $K_{n[t]}^{\ast}$ for all $n\in\{4,8\}\cup\{2p:p\mbox{ an odd prime}\}$ . Then there exists a $\vec{C}_{t}$ -factorization of $K_{n[t]}^{\ast}$ for all even $n\geq 4$ .

Proof.

(1)

Take any $n\equiv 0\pmod{4}$ . There are two cases to consider.

Case 1: $n=4^{\ell}s$ with $\ell\geq 1$ and $s$ odd. If $s=1$ , then a repeated application of Lemma 6.1 with $n_{1}=4$ and $n_{2}=4,4^{2},\ldots,4^{\ell-1}$ yields a $\vec{C}_{t}$ -factorization of $K_{n[t]}^{\ast}$ . If $s\geq 3$ , then by Corollary 3.2, there exists a $\vec{C}_{t}$ -factorization of $K_{s[t]}^{\ast}$ . We can now use Lemma 6.1 with $n_{1}=4$ and $n_{2}=s,4s,4^{2}s,\ldots,4^{\ell-1}s$ .

Case 2: $n=8\cdot 4^{\ell}s$ with $\ell\geq 0$ and $s$ odd, and we may assume that $\ell\geq 1$ or $s\geq 3$ . Hence, by Corollary 3.2 and Case 1, there exists a $\vec{C}_{t}$ -factorization of $K_{4^{\ell}s[t]}^{\ast}$ . We can therefore use Lemma 6.1 with $n_{1}=8$ and $n_{2}=4^{\ell}s$ .
(2)

Use Lemma 6.1 with $n_{1}=2p$ and $n_{2}=s$ .
(3)

This follows directly from (1) and(2).

6.1 Subcase $n\equiv 0\pmod{4}$

In the next two lemmas, we show that the assumptions from Corollary 6.2(1) indeed hold, that is, both $K_{4[t]}^{\ast}$ and $K_{8[t]}^{\ast}$ admit $\vec{C}_{t}$ -factorizations.

Lemma 6.3

Let $t$ be odd, $t\geq 3$ . Then $K_{4[t]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization.

Proof. A $\vec{C}_{t}$ -factorization of $K_{4[3]}^{\ast}$ exists by Theorem 1.4. Hence we may assume $t\geq 5$ . We shall construct a $\vec{C}_{t}$ -factorization of $K_{4[t]}^{\ast}$ as follows.

Let the vertex set of $D=K_{4[t]}^{\ast}$ be $V\cup X$ , where $V$ and $X$ are disjoint sets, with $V=\{v_{i}:i\in\mathbb{Z}_{3t}\}$ and $X=\{x_{i}:i\in\mathbb{Z}_{t}\}$ . The four parts (holes) of $D$ are $X$ and $V_{r}=\{v_{3i+r}:i=0,1,\ldots,t-1\}$ , for $r=0,1,2$ . Note that $D[V]$ is a circulant digraph with connection set (set of differences) ${\mathcal{D}}=\{d\in\mathbb{Z}_{3t}:d\not\equiv 0\pmod{3}\}$ . Define the permutation $\rho=(v_{0}\,v_{1}\,\ldots\,v_{3t-1})$ on $V\cup X$ , which fixes the vertices of $X$ pointwise.

Let $t=2k+1$ . Hence the differences in ${\mathcal{D}}$ and the subscripts of the vertices in $V$ can be seen as elements of $\{0,\pm 1,\pm 2,\ldots,\pm(3k+1)\}$ .

We define the following directed paths in $D[V]$ (see Figure 2):

P_{1}=v_{0}v_{1}v_{-1}v_{3}v_{-2}v_{5}\ldots v_{2k-3}v_{-(k-1)}v_{2k-1},

and $P_{2}$ is obtained from $P_{1}$ by applying $\rho^{3k+2}$ (or $\rho^{-(3k+1)}$ ) and reversing the direction of the path. That is,

P_{2}=v_{-(k+2)}v_{2k+3}v_{-(k+4)}\ldots v_{-(3k-2)}v_{3k+1}v_{-3k}v_{-(3k+1)}.

Observe that $P_{1}$ and $P_{2}$ are disjoint, and jointly contain all vertices in $V$ except those in

	$\displaystyle V-(V(P_{1})\cup V(P_{2}))$	$\displaystyle=$	$\displaystyle\{v_{2},v_{4},\ldots,v_{2k-2}\}\cup\{v_{2k},v_{2k+1},v_{2k+2}\}$
			$\displaystyle\cup\{v_{-(3k-1)},v_{-(3k-3)},\ldots,v_{-(k+3)}\}\cup\{v_{-(k+1)},v_{-k}\}.$

The set of differences of the arcs in $P_{1}$ , listing the differences in order of appearance, is

{\mathcal{D}}(P_{1})=\{1,-2,4,-5,7,\ldots,3k-5,-(3k-4),3k-2\},

and ${\mathcal{D}}(P_{2})=-{\mathcal{D}}(P_{1})$ .

Furthermore, let

	$\displaystyle P_{3}$	$\displaystyle=$	$\displaystyle v_{2k-2}v_{-(k+1)}v_{2k+1}v_{-(k+3)}\quad\mbox{ and}$
	$\displaystyle P_{4}$	$\displaystyle=$	$\displaystyle v_{2k+2}v_{-k}.$

Thus

	$\displaystyle{\mathcal{D}}(P_{3})$	$\displaystyle=$	$\displaystyle\{-(3k-1),-(3k+1),3k-1\}\quad\mbox{ and}$
	$\displaystyle{\mathcal{D}}(P_{4})$	$\displaystyle=$	$\displaystyle\{3k+1\}.$

Observe that directed paths $P_{1},\ldots,P_{4}$ are pairwise disjoint, and jointly contain exactly one arc of each difference in ${\mathcal{D}}$ .

Let $U=V-\bigcup_{i=1}^{4}V(P_{i})$ . It is easy to verify that $|U|=(6k+3)-(2k+2k+4+2)=2k-3$ , so we may set $U=\{u_{0},\ldots,u_{2k-4}\}$ . Finally, we extend the four paths to four pairwise disjoint directed $t$ -cycles as follows:

$\displaystyle C_{1}$	$\displaystyle=$	$\displaystyle P_{1}v_{2k-1}x_{0}v_{0},$
$\displaystyle C_{2}$	$\displaystyle=$	$\displaystyle P_{2}v_{-(3k+1)}x_{1}v_{-(k+2)},$
$\displaystyle C_{3}$	$\displaystyle=$	$\displaystyle P_{3}v_{-(k+3)}x_{2}u_{0}x_{3}u_{1}\ldots u_{k-3}x_{k}v_{2k-2},\quad\mbox{ and}$
$\displaystyle C_{4}$	$\displaystyle=$	$\displaystyle P_{4}v_{-k}x_{k+1}u_{k-2}x_{k+2}u_{k-1}\ldots u_{2k-4}x_{2k}v_{2k+2}.$

Let $R=C_{1}\cup C_{2}\cup C_{3}\cup C_{4}$ , so $R$ is a $\vec{C}_{t}$ -factor in $D$ . It is not difficult to verify that $\{\rho^{i}(R):i\in\mathbb{Z}_{3t}\}$ is a $\vec{C}_{t}$ -factorization of $D$ . a

Lemma 6.4

Let $t$ be odd, $t\geq 3$ . Then $K_{8[t]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization.

Proof. By Corollary 4.2(b), we may assume that $t$ is a prime, and hence $t\equiv 1$ or $5\pmod{6}$ , and by Theorem 1.4, we may assume $t\geq 5$ .

Let the vertex set of $D=K_{8[t]}^{\ast}$ be $V\cup X$ , where $V$ and $X$ are disjoint sets, with $V=\{v_{i}:i\in\mathbb{Z}_{7t}\}$ and $X=\{x_{i}:i\in\mathbb{Z}_{t}\}$ . The eight parts (holes) of $D$ are $X$ and $V_{r}=\{v_{7i+r}:i=0,1,\ldots,t-1\}$ , for $r=0,1,\ldots,6$ . Note that $D[V]$ is a circulant digraph with connection set (set of differences) ${\mathcal{D}}=\{d\in\mathbb{Z}_{7t}:d\not\equiv 0\pmod{7}\}$ . Define the permutation $\rho=(v_{0}\,v_{1}\,\ldots\,v_{7t-1})$ , which fixes the vertices of $X$ pointwise.

Case 1: $t=5$ . Then $D[V]$ is a circulant digraph with vertex set $V=\{v_{i}:i\in\mathbb{Z}_{35}\}$ and connection set ${\mathcal{D}}=\{\pm d:1\leq d\leq 17,d\not\equiv 0\pmod{7}\}$ .

First, define the following two directed $5$ -cycles (see Figure 3):

	$\displaystyle C_{1}$	$\displaystyle=$	$\displaystyle v_{0}v_{16}v_{1}v_{14}v_{2}v_{0}\quad\mbox{ and }$
	$\displaystyle C_{2}$	$\displaystyle=$	$\displaystyle v_{13}v_{3}v_{12}v_{4}v_{9}v_{13}.$

The next two directed $5$ -cycles are obtained by applying the reflection $\tau:v_{i}\mapsto v_{-(i+1)}$ to cycles $C_{1}$ and $C_{2}$ :

	$\displaystyle C_{3}$	$\displaystyle=$	$\displaystyle v_{34}v_{18}v_{33}v_{20}v_{32}v_{34}\quad\mbox{ and }$
	$\displaystyle C_{4}$	$\displaystyle=$	$\displaystyle v_{21}v_{31}v_{22}v_{30}v_{25}v_{21}.$

Next, we define three directed 3-paths and one directed 1-path:

$\displaystyle P_{1}$	$\displaystyle=$	$\displaystyle v_{6}v_{24}v_{27}v_{26},$
$\displaystyle P_{2}$	$\displaystyle=$	$\displaystyle v_{29}v_{23}v_{5}v_{11},$
$\displaystyle P_{3}$	$\displaystyle=$	$\displaystyle v_{10}v_{7}v_{8}v_{19},\quad\mbox{ and }$
$\displaystyle P_{4}$	$\displaystyle=$	$\displaystyle v_{28}v_{17}.$

Observe that these cycles and paths are pairwise disjoint, and $U=V-\bigcup_{i=1}^{4}\big{(}V(P_{i})\cup V(C_{i})\big{)}=\{v_{15}\}$ . Their sets of differences are:

$\displaystyle{\mathcal{D}}(C_{1})$	$\displaystyle=$	$\displaystyle\{16,-15,13,-12,-2\},$
$\displaystyle{\mathcal{D}}(C_{2})$	$\displaystyle=$	$\displaystyle\{-10,9,-8,5,4\},$
$\displaystyle{\mathcal{D}}(C_{3})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(C_{1}),$
$\displaystyle{\mathcal{D}}(C_{4})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(C_{2}),$
$\displaystyle{\mathcal{D}}(P_{1})$	$\displaystyle=$	$\displaystyle\{-17,3,-1\},$
$\displaystyle{\mathcal{D}}(P_{2})$	$\displaystyle=$	$\displaystyle\{-6,17,6\},$
$\displaystyle{\mathcal{D}}(P_{3})$	$\displaystyle=$	$\displaystyle\{-3,1,11\},\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{4})$	$\displaystyle=$	$\displaystyle\{-11\}.$

Thus, these paths and cycles jointly use exactly one arc of each difference in ${\mathcal{D}}$ . We next extend the paths to directed 5-cycles as follows:

$\displaystyle C_{5}$	$\displaystyle=$	$\displaystyle P_{1}v_{26}x_{0}v_{6},$
$\displaystyle C_{6}$	$\displaystyle=$	$\displaystyle P_{2}v_{11}x_{1}v_{29},$
$\displaystyle C_{7}$	$\displaystyle=$	$\displaystyle P_{3}v_{19}x_{2}v_{10},\quad\mbox{ and }$
$\displaystyle C_{8}$	$\displaystyle=$	$\displaystyle P_{4}v_{17}x_{3}v_{15}x_{4}v_{28}.$

Let $R=C_{1}\cup\ldots\cup C_{8}$ , so $R$ is a $\vec{C}_{5}$ -factor in $D$ . It is not difficult to verify that $\{\rho^{i}(R):i\in\mathbb{Z}_{35}\}$ is a $\vec{C}_{5}$ -factorization of $D$ .

Case 2: $t=7$ . Now $D[V]$ is a circulant digraph with vertex set $V=\{v_{i}:i\in\mathbb{Z}_{49}\}$ and connection set ${\mathcal{D}}=\{\pm d:1\leq d\leq 24,d\not\equiv 0\pmod{7}\}$ .

First, define the following two directed $7$ -cycles:

	$\displaystyle C_{1}$	$\displaystyle=$	$\displaystyle v_{0}v_{23}v_{1}v_{21}v_{2}v_{20}v_{3}v_{0}\quad\mbox{ and }$
	$\displaystyle C_{2}$	$\displaystyle=$	$\displaystyle v_{19}v_{4}v_{17}v_{5}v_{16}v_{6}v_{15}v_{19}.$

The next two directed $7$ -cycles are obtained by applying the reflection $\tau:v_{i}\mapsto v_{-(i+1)}$ to cycles $C_{1}$ and $C_{2}$ :

	$\displaystyle C_{3}$	$\displaystyle=$	$\displaystyle v_{48}v_{25}v_{47}v_{27}v_{46}v_{28}v_{45}v_{48}\quad\mbox{ and }$
	$\displaystyle C_{4}$	$\displaystyle=$	$\displaystyle v_{29}v_{44}v_{31}v_{43}v_{32}v_{42}v_{33}v_{29}.$

The fifth 7-cycle is

C_{5}=v_{9}v_{10}v_{26}v_{34}v_{40}v_{35}v_{11}v_{9}.

Next, we define one directed 5-path and two directed 1-paths:

$\displaystyle P_{1}$	$\displaystyle=$	$\displaystyle v_{39}v_{38}v_{30}v_{14}v_{8}v_{13},$
$\displaystyle P_{2}$	$\displaystyle=$	$\displaystyle v_{37}v_{12},\quad\mbox{ and }$
$\displaystyle P_{3}$	$\displaystyle=$	$\displaystyle v_{22}v_{24}.$

Observe that these cycles and paths are pairwise disjoint, and $U=V-\big{(}\bigcup_{i=1}^{5}V(C_{i})\cup\big{(}\bigcup_{i=1}^{3}V(P_{i})\big{)}=\{v_{7},v_{18},v_{36},v_{41}\}$ . Their sets of differences are:

$\displaystyle{\mathcal{D}}(C_{1})$	$\displaystyle=$	$\displaystyle\{23,-22,20,-19,18,-17,-3\},$
$\displaystyle{\mathcal{D}}(C_{2})$	$\displaystyle=$	$\displaystyle\{-15,13,-12,11,-10,9,4\},$
$\displaystyle{\mathcal{D}}(C_{3})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(C_{1}),$
$\displaystyle{\mathcal{D}}(C_{4})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(C_{2}),$
$\displaystyle{\mathcal{D}}(C_{5})$	$\displaystyle=$	$\displaystyle\{1,16,8,6,-5,-24,-2\},$
$\displaystyle{\mathcal{D}}(P_{1})$	$\displaystyle=$	$\displaystyle\{-1,-8,-16,-6,5\},$
$\displaystyle{\mathcal{D}}(P_{2})$	$\displaystyle=$	$\displaystyle\{24\},\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{3})$	$\displaystyle=$	$\displaystyle\{2\}.$

Thus, these paths and cycles jointly use exactly one arc of each difference in ${\mathcal{D}}$ . We extend paths $P_{1},P_{2},P_{3}$ to directed 7-cycles as follows:

$\displaystyle C_{6}$	$\displaystyle=$	$\displaystyle P_{1}v_{13}x_{0}v_{39},$
$\displaystyle C_{7}$	$\displaystyle=$	$\displaystyle P_{2}v_{12}x_{1}v_{7}x_{2}v_{18}x_{3}v_{37},\quad\mbox{ and }$
$\displaystyle C_{8}$	$\displaystyle=$	$\displaystyle P_{3}v_{24}x_{4}v_{36}x_{5}v_{41}x_{6}v_{22}.$

Let $R=C_{1}\cup\ldots\cup C_{8}$ , so $R$ is a $\vec{C}_{7}$ -factor in $D$ . It is not difficult to verify that $\{\rho^{i}(R):i\in\mathbb{Z}_{49}\}$ is a $\vec{C}_{7}$ -factorization of $D$ .

Case 3: $t=6k+5$ for an integer $k\geq 1$ . Now $D[V]$ is a circulant digraph with vertex set $V=\{v_{i}:i\in\mathbb{Z}_{42k+35}\}$ and connection set ${\mathcal{D}}=\{\pm d:1\leq d\leq 21k+17,d\not\equiv 0\pmod{7}\}$ .

Subcase 3.1: $k\equiv 1$ or $2\pmod{4}$ .

Define the following three directed $(6k+3)$ -paths (see Figure 4):

$\displaystyle P_{1}$	$\displaystyle=$	$\displaystyle v_{0}v_{1}v_{-1}v_{2}v_{-2}v_{3}v_{-3}v_{5}v_{-4}\ldots v_{4k-2}v_{-(3k-1)}v_{4k-1}v_{-3k}v_{4k+1}v_{-(3k+1)}v_{4k+2},$
$\displaystyle P_{2}$	$\displaystyle=$	$\displaystyle v_{-(3k+2)}v_{4k+3}v_{-(3k+3)}v_{4k+5}v_{-(3k+4)}v_{4k+6}\ldots v_{-(6k+2)}v_{8k+3}v_{-(6k+3)}v_{8k+5},\quad\mbox{ and }$
$\displaystyle P_{3}$	$\displaystyle=$	$\displaystyle v_{-(6k+4)}v_{8k+6}v_{-(6k+5)}v_{8k+7}v_{-(6k+6)}v_{8k+9}\ldots v_{-(9k+4)}v_{12k+6}v_{-(9k+5)}v_{12k+7}.$

For $i=1,2,3$ , let $P_{i+3}$ be the directed $(6k+3)$ -path obtained from $P_{i}$ by applying $\rho^{21k+18}=\rho^{-(21k+17)}$ and changing the direction. Thus,

$\displaystyle P_{4}$	$\displaystyle=$	$\displaystyle v_{-(17k+15)}v_{18k+17}\ldots v_{-(21k+16)}v_{-(21k+17)},$
$\displaystyle P_{5}$	$\displaystyle=$	$\displaystyle v_{-(13k+12)}v_{15k+15}\ldots v_{-(17k+14)}v_{18k+16},\quad\mbox{ and }$
$\displaystyle P_{6}$	$\displaystyle=$	$\displaystyle v_{-(9k+10)}v_{12k+13}\ldots v_{-(13k+11)}v_{15k+14}.$

Observe that these paths are pairwise disjoint, and use all vertices in $V$ except those in

$\displaystyle V-\bigcup_{i=1}^{6}V(P_{i})$	$\displaystyle=$	$\displaystyle\{v_{4},v_{8},v_{12},\ldots,v_{12k+4}\}\cup\{v_{12k+8},v_{12k+9},\ldots,v_{12k+12}\}$
		$\displaystyle\cup\{v_{-(21k+13)},v_{-(21k+9)},v_{-(21k+5)},\ldots,v_{-(9k+13)}\}$
		$\displaystyle\cup\{v_{-(9k+9)},v_{-(9k+8)},v_{-(9k+7)},v_{-(9k+6)}\}.$

The sets of differences of these paths, listing the differences in their order of appearance, are:

$\displaystyle{\mathcal{D}}(P_{1})$	$\displaystyle=$	$\displaystyle\{1,-2,3,-4,5,-6,8,-9,\ldots,-(7k-1),7k+1,-(7k+2),7k+3\},$
$\displaystyle{\mathcal{D}}(P_{2})$	$\displaystyle=$	$\displaystyle\{7k+5,-(7k+6),7k+8,-(7k+9),\ldots,14k+5,-(14k+6),14k+8\},$
$\displaystyle{\mathcal{D}}(P_{3})$	$\displaystyle=$	$\displaystyle\{14k+10,-(14k+11),14k+12,-(14k+13),14k+15,\ldots$
		$\displaystyle\ldots,21k+10,-(21k+11),21k+12\},$
$\displaystyle{\mathcal{D}}(P_{4})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{1}),$
$\displaystyle{\mathcal{D}}(P_{5})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{2}),\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{6})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{3}).$

Thus, these paths jointly use exactly one arc of each difference in ${\mathcal{D}}-{\mathcal{D}}^{\prime}$ , where

{\mathcal{D}}^{\prime}=\{\pm(7k+4),\pm(14k+9),\pm(21k+13),\pm(21k+15),\pm(21k+16),\pm(21k+17)\}.

The remaining two directed paths depend on the congruency class of $k$ modulo 4.

If $k\equiv 1\pmod{4}$ , we let

	$\displaystyle P_{7}$	$\displaystyle=$	$\displaystyle v_{5k+3},v_{-(9k+6)},v_{-(16k+10)},v_{5k+7},v_{12k+11},v_{-(9k+8)},v_{12k+12},v_{-(16k+14)}\quad\mbox{ and }$
	$\displaystyle P_{8}$	$\displaystyle=$	$\displaystyle v_{-(9k+9)},v_{12k+4},v_{-(9k+13)},v_{12k+9},v_{-(9k+7)},v_{12k+8}.$

See Figure 5. The sets of differences of these paths are

	$\displaystyle{\mathcal{D}}(P_{7})$	$\displaystyle=$	$\displaystyle\{-(14k+9),-(7k+4),21k+17,7k+4,21k+16,-(21k+15),14k+9\}\quad\mbox{ and }$
	$\displaystyle{\mathcal{D}}(P_{8})$	$\displaystyle=$	$\displaystyle\{21k+13,-(21k+17),-(21k+13),-(21k+16),21k+15\}.$

If $k\equiv 2\pmod{4}$ , we let

	$\displaystyle P_{7}$	$\displaystyle=$	$\displaystyle v_{5k-2},v_{-(16k+15)},v_{12k+11},v_{-(9k+8)},v_{12k+12},v_{-(9k+6)},v_{12k+9},v_{-(9k+13)}\quad\mbox{ and }$
	$\displaystyle P_{8}$	$\displaystyle=$	$\displaystyle v_{-(9k+9)},v_{12k+10},v_{5k+6},v_{-(16k+11)},v_{-(9k+7)},v_{5k+2}.$

In this case, we have

	$\displaystyle{\mathcal{D}}(P_{7})$	$\displaystyle=$	$\displaystyle\{-(21k+13),-(14k+9),21k+16,-(21k+15),21k+17,21k+15,21k+13\}\quad\mbox{ and }$
	$\displaystyle{\mathcal{D}}(P_{8})$	$\displaystyle=$	$\displaystyle\{-(21k+16),-(7k+4),-(21k+17),7k+4,14k+9\}.$

In either case, paths $P_{1},\ldots,P_{8}$ are pairwise disjoint, and jointly contain exactly one arc of each difference in ${\mathcal{D}}$ . Moreover, the set of unused vertices $U$ has cardinality $|U|=(42k+35)-6(6k+4)-8-6=6k-3$ . Hence we may label $U=\{u_{i}:i\in\mathbb{Z}_{6k-3}\}$ .

Finally, we extend the eight directed paths to directed $(6k+5)$ -cycles as follows. It will be convenient to denote the source and terminal vertex of directed path $P_{i}$ by $s_{i}$ and $t_{i}$ , respectively. Let

C_{i}=P_{i}t_{i}x_{i-1}s_{i}\quad\mbox{ for }i=1,2,\ldots,6,

while

	$\displaystyle C_{7}$	$\displaystyle=$	$\displaystyle P_{7}t_{7}x_{6}u_{0}x_{7}u_{1}\ldots u_{3k-3}x_{3k+4}s_{7}\quad\mbox{ and }$
	$\displaystyle C_{8}$	$\displaystyle=$	$\displaystyle P_{8}t_{8}x_{3k+5}u_{3k-2}x_{3k+6}u_{3k-1}\ldots u_{6k-4}x_{6k+4}s_{8}.$

To conclude, let $R=C_{1}\cup\ldots\cup C_{8}$ , so $R$ is a $\vec{C}_{t}$ -factor in $D$ . Since the permutation $\rho$ fixes the vertices of $X$ pointwise, it is not difficult to verify that $\{\rho^{i}(R):i\in\mathbb{Z}_{7t}\}$ is a $\vec{C}_{t}$ -factorization of $D$ .

Subcase 3.2: $k\equiv 0$ or $3\pmod{4}$ . This case will be solved similarly to Subcase 3.1, so we only highlight the differences.

Define the following three directed $(6k+3)$ -paths:

$\displaystyle P_{1}$	$\displaystyle=$	$\displaystyle v_{0}v_{-1}v_{1}v_{-2}v_{3}v_{-3}v_{5}v_{-4}v_{6}v_{-5}v_{7}v_{-6}v_{9}v_{-7}v_{10}\ldots v_{4k-1}v_{-3k}v_{4k+1}v_{-(3k+1)}v_{4k+2}v_{-(3k+2)},$
$\displaystyle P_{2}$	$\displaystyle=$	$\displaystyle v_{4k+3}v_{-(3k+3)}v_{4k+5}v_{-(3k+4)}v_{4k+6}\ldots v_{-(6k+2)}v_{8k+3}v_{-(6k+3)}v_{8k+5}v_{-(6k+4)},\quad\mbox{ and }$
$\displaystyle P_{3}$	$\displaystyle=$	$\displaystyle v_{8k+6}v_{-(6k+5)}v_{8k+7}v_{-(6k+6)}v_{8k+9}\ldots v_{12k+3}v_{-(9k+3)}v_{12k+5}v_{-(9k+4)}v_{12k+6}v_{-(9k+5)}v_{12k+7}v_{-(9k+6)}.$

For $i=1,2,3$ , let $P_{i+3}$ be the directed $(6k+3)$ -path obtained from $P_{i}$ by applying $\rho^{21k+18}=\rho^{-(21k+17)}$ and changing the direction. Thus,

$\displaystyle P_{4}$	$\displaystyle=$	$\displaystyle v_{18k+16}v_{-(17k+15)}\ldots v_{21k+17}v_{-(21k+17)},$
$\displaystyle P_{5}$	$\displaystyle=$	$\displaystyle v_{15k+14}v_{-(13k+12)}\ldots v_{18k+15}v_{-(17k+14)},\quad\mbox{ and }$
$\displaystyle P_{6}$	$\displaystyle=$	$\displaystyle v_{12k+12}v_{-(9k+10)}\ldots v_{15k+13}v_{-(13k+11)}.$

Observe that these paths are pairwise disjoint, and use all vertices in $V$ except those in

$\displaystyle V-\bigcup_{i=1}^{6}V(P_{i})$	$\displaystyle=$	$\displaystyle\{v_{2},v_{4},v_{8},v_{12},\ldots,v_{12k+4}\}\cup\{v_{12k+8},v_{12k+9},\ldots,v_{12k+11}\}$
		$\displaystyle\cup\{v_{-(21k+15)},v_{-(21k+13)},v_{-(21k+9)},v_{-(21k+5)},\ldots,v_{-(9k+13)}\}$
		$\displaystyle\cup\{v_{-(9k+9)},v_{-(9k+8)},v_{-(9k+7)}\}.$

The sets of differences of these paths, listing the differences in their order of appearance, are:

$\displaystyle{\mathcal{D}}(P_{1})$	$\displaystyle=$	$\displaystyle\{-1,2,-3,5,-6,8,-9,\ldots,-(7k-1),7k+1,-(7k+2),7k+3,-(7k+4)\},$
$\displaystyle{\mathcal{D}}(P_{2})$	$\displaystyle=$	$\displaystyle\{-(7k+6),7k+8,-(7k+9),\ldots,14k+5,-(14k+6),14k+8,-(14k+9)\},$
$\displaystyle{\mathcal{D}}(P_{3})$	$\displaystyle=$	$\displaystyle\{-(14k+11),14k+12,-(14k+13),14k+15,\ldots$
		$\displaystyle\ldots,21k+10,-(21k+11),21k+12,-(21k+13)\},$
$\displaystyle{\mathcal{D}}(P_{4})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{1}),$
$\displaystyle{\mathcal{D}}(P_{5})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{2}),\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{6})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{3}).$

Thus, these paths jointly use exactly one arc of each difference in ${\mathcal{D}}-{\mathcal{D}}^{\prime}$ , where

{\mathcal{D}}^{\prime}=\{\pm 4,\pm(7k+5),\pm(14k+10),\pm(21k+15),\pm(21k+16),\pm(21k+17)\}.

The remaining two directed paths depend on the congruency class of $k$ modulo 4.

If $k\equiv 3\pmod{4}$ , we let

	$\displaystyle P_{7}$	$\displaystyle=$	$\displaystyle v_{-(9k+9)}v_{12k+10}v_{-(9k+8)}v_{12k+8}v_{-(9k+7)}v_{-(16k+12)}v_{-(16k+16)}v_{12k+9}\quad\mbox{ and }$
	$\displaystyle P_{8}$	$\displaystyle=$	$\displaystyle v_{-(21k+13)}v_{2}v_{7k+7}v_{-(14k+10)}v_{-(14k+6)}v_{4}.$

The sets of differences of these paths are

	$\displaystyle{\mathcal{D}}(P_{7})$	$\displaystyle=$	$\displaystyle\{-(21k+16),21k+17,21k+16,-(21k+15),-(7k+5),-4,-(14k+10)\}\quad\mbox{ and }$
	$\displaystyle{\mathcal{D}}(P_{8})$	$\displaystyle=$	$\displaystyle\{21k+15,7k+5,-(21k+17),4,14k+10\}.$

If $k\equiv 0\pmod{4}$ , we let

	$\displaystyle P_{7}$	$\displaystyle=$	$\displaystyle v_{2}v_{-(21k+13)}v_{7k+12}v_{7k+16}v_{-(21k+9)}v_{8}v_{4}v_{-(21k+15)}\quad\mbox{ and }$
	$\displaystyle P_{8}$	$\displaystyle=$	$\displaystyle v_{-(16k+13)}v_{-(9k+8)}v_{12k+11}v_{-(9k+9)}v_{12k+9}v_{5k+4}.$

In this case, we have

	$\displaystyle{\mathcal{D}}(P_{7})$	$\displaystyle=$	$\displaystyle\{-(21k+15),-(14k+10),4,14k+10,21k+17,-4,21k+16\}\quad\mbox{ and }$
	$\displaystyle{\mathcal{D}}(P_{8})$	$\displaystyle=$	$\displaystyle\{7k+5,-(21k+16),21k+15,-(21k+17),-(7k+5)\}.$

The construction is then completed precisely as in Subcase 3.1.

Case 4: $t=6k+1$ for an integer $k\geq 2$ . This case is similar to Subcase 3.2, so we only highlight the differences. Now $D[V]$ is a circulant digraph with vertex set $V=\{v_{i}:i\in\mathbb{Z}_{42k+7}\}$ and connection set ${\mathcal{D}}=\{\pm d:1\leq d\leq 21k+3,d\not\equiv 0\pmod{7}\}$ .

Define the following three directed $(6k-1)$ -paths:

$\displaystyle P_{1}$	$\displaystyle=$	$\displaystyle v_{0}v_{-1}v_{1}v_{-2}v_{3}v_{-3}v_{5}v_{-4}v_{6}v_{-5}v_{7}v_{-6}v_{9}v_{-7}v_{10}\ldots v_{4k-2}v_{-(3k-1)}v_{4k-1}v_{-3k},$
$\displaystyle P_{2}$	$\displaystyle=$	$\displaystyle v_{4k+1}v_{-(3k+1)}v_{4k+2}v_{-(3k+2)}v_{4k+3}\ldots v_{-(6k-2)}v_{8k-2}v_{-(6k-1)}v_{8k-1}v_{-6k},\quad\mbox{ and }$
$\displaystyle P_{3}$	$\displaystyle=$	$\displaystyle v_{-(6k+1)}v_{8k}v_{-(6k+2)}v_{8k+1}v_{-(6k+3)}v_{8k+2}v_{-(6k+4)}v_{8k+4}v_{-(6k+5)}v_{8k+5}\ldots$
		$\displaystyle\ldots v_{-(9k-3)}v_{12k-6}v_{-(9k-2)}v_{12k-4}v_{-(9k-1)}v_{12k-3}v_{-9k}v_{12k-2}.$

For $i=1,2,3$ , let $P_{i+3}$ be the directed $(6k-1)$ -path obtained from $P_{i}$ by applying $\rho^{21k+4}=\rho^{-(21k+3)}$ and changing the direction. Thus,

$\displaystyle P_{4}$	$\displaystyle=$	$\displaystyle v_{18k+4}v_{-(17k+4)}\ldots v_{21k+3}v_{-(21k+3)},$
$\displaystyle P_{5}$	$\displaystyle=$	$\displaystyle v_{15k+4}v_{-(13k+4)}\ldots v_{18k+3}v_{-(17k+2)},\quad\mbox{ and }$
$\displaystyle P_{6}$	$\displaystyle=$	$\displaystyle v_{-(9k+5)}v_{12k+4}\ldots v_{-(13k+3)}v_{15k+3}.$

Observe that these six paths are pairwise disjoint, and use all vertices in $V$ except those in

$\displaystyle V-\bigcup_{i=1}^{6}V(P_{i})$	$\displaystyle=$	$\displaystyle\{v_{2},v_{4},v_{8},v_{12},\ldots,v_{8k-4}\}\cup\{v_{8k+3},v_{8k+7},\ldots,v_{12k-5}\}$
		$\displaystyle\cup\{v_{12k-1},v_{12k},\ldots,v_{12k+3}\}$
		$\displaystyle\cup\{v_{-(21k+1)},v_{-(21k-1)},v_{-(21k-5)},v_{-(21k-9)},\ldots,v_{-(13k+7)}\}$
		$\displaystyle\cup\{v_{-13k},v_{-(13k-4)},\ldots,v_{-(9k+8)}\}$
		$\displaystyle\cup\{v_{-(9k+4)},v_{-(9k+3)},v_{-(9k+2)},v_{-(9k+1)}\}.$

The sets of differences of these paths, listing the differences in their order of appearance, are:

$\displaystyle{\mathcal{D}}(P_{1})$	$\displaystyle=$	$\displaystyle\{-1,2,-3,5,-6,8,-9,\ldots,,7k-4,-(7k-3),7k-2,-(7k-1)\},$
$\displaystyle{\mathcal{D}}(P_{2})$	$\displaystyle=$	$\displaystyle\{-(7k+2),7k+3,-(7k+4),\ldots,14k-4,-(14k-3),14k-2,-(14k-1)\},$
$\displaystyle{\mathcal{D}}(P_{3})$	$\displaystyle=$	$\displaystyle\{14k+1,-(14k+2),14k+3,\ldots,21k-4,-(21k-3),21k-2\},$
$\displaystyle{\mathcal{D}}(P_{4})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{1}),$
$\displaystyle{\mathcal{D}}(P_{5})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{2}),\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{6})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{3}).$

Thus, these paths jointly use exactly one arc of each difference in ${\mathcal{D}}-{\mathcal{D}}^{\prime}$ , where

{\mathcal{D}}^{\prime}=\{\pm 4,\pm(7k+1),\pm(21k-1),\pm(21k+1),\pm(21k+2),\pm(21k+3)\}.

The remaining two directed paths depend on the congruency class of $k$ modulo 4.

If $k\equiv 0\pmod{4}$ , we let

	$\displaystyle P_{7}$	$\displaystyle=$	$\displaystyle v_{12k-1}v_{-(9k+3)}v_{12k+1}v_{5k}v_{5k-4}v_{-(16k+3)}v_{-(9k+2)}v_{12k}v_{-(9k+1)}v_{12k+2}v_{-(9k+4)}v_{12k-5}\quad\mbox{ and }$
	$\displaystyle P_{8}$	$\displaystyle=$	$\displaystyle v_{4}v_{8}.$

The sets of differences of these paths are

$\displaystyle{\mathcal{D}}(P_{7})$	$\displaystyle=$	$\displaystyle\{-(21k+2),-(21k+3),-(7k+1),-4,-(21k-1),7k+1,21k+2,-(21k+1),$
		$\displaystyle\;\;21k+3,21k+1,21k-1\}\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{8})$	$\displaystyle=$	$\displaystyle\{4\}.$

If $k\equiv 1\pmod{4}$ , we let

	$\displaystyle P_{7}$	$\displaystyle=$	$\displaystyle v_{12k-1}v_{-(9k+2)}v_{12k+3}v_{-(9k+1)}v_{12k}v_{5k-1}v_{5k-5}v_{-(16k+4)}v_{-(9k+3)}v_{12k+1}v_{-(9k+4)}v_{12k-5}\quad\mbox{ and }$
	$\displaystyle P_{8}$	$\displaystyle=$	$\displaystyle v_{4}v_{8}.$

The sets of differences of these paths are

$\displaystyle{\mathcal{D}}(P_{7})$	$\displaystyle=$	$\displaystyle\{-(21k+1),-(21k+2),21k+3,21k+1,-(7k+1),-4,-(21k-1),7k+1,$
		$\displaystyle\;\;-(21k+3),21k+2,21k-1\}\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{8})$	$\displaystyle=$	$\displaystyle\{4\}.$

If $k\equiv 2\pmod{4}$ , we let

	$\displaystyle P_{7}$	$\displaystyle=$	$\displaystyle v_{-(9k+4)}v_{12k+2}v_{-(9k+3)}v_{12k+1}v_{-(9k+1)}v_{12k}v_{-(9k+8)}v_{12k-5}v_{12k-1}v_{5k-2}v_{5k-6}v_{-(16k+5)}\quad\mbox{ and }$
	$\displaystyle P_{8}$	$\displaystyle=$	$\displaystyle v_{5k+2}v_{12k+3}.$

The sets of differences of these paths are

$\displaystyle{\mathcal{D}}(P_{7})$	$\displaystyle=$	$\displaystyle\{-(21k+1),21k+2,-(21k+3),-(21k+2),21k+1,21k-1,21k+3,4,$
		$\displaystyle\;\;-(7k+1),-4,-(21k-1)\}\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{8})$	$\displaystyle=$	$\displaystyle\{7k+1\}.$

If $k\equiv 3\pmod{4}$ , we let

	$\displaystyle P_{7}$	$\displaystyle=$	$\displaystyle v_{12k-1}v_{-(9k+3)}v_{12k+3}v_{-(9k+2)}v_{12k+2}v_{5k+1}v_{5k-3}v_{-(16k+2)}v_{-(9k+1)}v_{12k}v_{-(9k+4)}v_{12k-5}\quad\mbox{ and }$
	$\displaystyle P_{8}$	$\displaystyle=$	$\displaystyle v_{4}v_{8}.$

The sets of differences of these paths are

$\displaystyle{\mathcal{D}}(P_{7})$	$\displaystyle=$	$\displaystyle\{-(21k+2),-(21k+1),21k+2,-(21k+3),-(7k+1),-4,-(21k-1),7k+1,$
		$\displaystyle\;\;21k+1,21k+3,21k-1\}\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{8})$	$\displaystyle=$	$\displaystyle\{4\}.$

The construction is then completed similarly to Subcases 3.1 and 3.2, except that $3k-5$ vertices of $X$ and $3k-6$ vertices of $U=V-\cup_{i=1}^{6}V(P_{i})$ are used to complete $P_{7}$ to $C_{7}$ , while $3k$ vertices of $X$ and $3k-1$ vertices of $U$ are used to complete $P_{8}$ to $C_{8}$ . Observe that, indeed, $|U|=(42k+7)-6(6k)-12-2=6k-7=(3k-6)+(3k-1)$ . a

Corollary 6.5

Assume $m\geq 3$ is odd, $n\equiv 0\pmod{4}$ , $t|mn$ , and $\gcd(n,t)=1$ . Then $K_{n[m]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization.

Proof. The assumptions imply that $m=st$ for some odd $s$ . By Lemmas 6.3 and 6.4, respectively, the digraphs $K_{4[t]}^{\ast}$ and $K_{8[t]}^{\ast}$ admit $\vec{C}_{t}$ -factorizations. Hence by Corollaries 6.2(1) and 4.2(a), the digraphs $K_{n[t]}^{\ast}$ and $K_{n[m]}^{\ast}\cong K_{n[t]}^{\ast}\wr\bar{K_{s}}$ , respectively, admit $\vec{C}_{t}$ -factorizations. a

6.2 Subcase $n\equiv 0\pmod{6}$

This section covers the smallest of the cases $n=2p$ , for $p$ an odd prime. The construction is similar to the case $n=8$ . In principle, this approach could be taken to construct a $\vec{C}_{t}$ -factorizaton of $K_{2p[t]}^{\ast}$ for any fixed prime $p$ , however, for $p\geq 5$ , the work involved becomes too tedious.

Lemma 6.6

Let $t$ be odd, $t\geq 3$ . Then $K_{6[t]}^{\ast}$ admits a $\vec{C}_{t}$ -factorizaton.

Proof. By Corollary 4.2(b), we may assume that $t$ is a prime, and by Theorem 1.4, we may assume $t\geq 5$ .

Let the vertex set of $D=K_{6[t]}^{\ast}$ be $V\cup X$ , where $V$ and $X$ are disjoint sets, with $V=\{v_{i}:i\in\mathbb{Z}_{5t}\}$ and $X=\{x_{i}:i\in\mathbb{Z}_{t}\}$ . The six parts (holes) of $D$ are $X$ and $V_{r}=\{v_{5i+r}:i=0,1,\ldots,t-1\}$ , for $r=0,1,\ldots,4$ . Note that $D[V]$ is a circulant digraph with connection set (set of differences) ${\mathcal{D}}=\{d\in\mathbb{Z}_{5t}:d\not\equiv 0\pmod{5}\}$ . Define a permutation $\rho=(v_{0}\,v_{1}\,\ldots\,v_{5t-1})$ , which fixes the vertices of $X$ pointwise.

Case 1: $t=5$ . Now $D[V]$ is a circulant digraph with vertex set $V=\{v_{i}:i\in\mathbb{Z}_{25}\}$ and connection set ${\mathcal{D}}=\{\pm 1,\ldots,\pm 4,\pm 6,\ldots,\pm 9,\pm 11,\pm 12\}$ .

First, define the following directed $5$ -cycle and directed 3-path:

	$\displaystyle C_{1}$	$\displaystyle=$	$\displaystyle v_{24}v_{11}v_{2}v_{10}v_{3}v_{24}\quad\mbox{ and }$
	$\displaystyle P_{2}$	$\displaystyle=$	$\displaystyle v_{6}v_{7}v_{5}v_{8}.$

The second directed $5$ -cycle and directed 3-path are obtained by applying the reflection $\tau:v_{i}\mapsto v_{-(i+1)}$ to $C_{1}$ and $P_{2}$ , respectively:

	$\displaystyle C_{3}$	$\displaystyle=$	$\displaystyle v_{0}v_{13}v_{22}v_{14}v_{21}v_{0}\quad\mbox{ and }$
	$\displaystyle P_{4}$	$\displaystyle=$	$\displaystyle v_{18}v_{17}v_{19}v_{16}.$

Next, we define another directed 3-path and a directed 1-path:

	$\displaystyle P_{5}$	$\displaystyle=$	$\displaystyle v_{9}v_{15}v_{1}v_{20}\quad\mbox{ and }$
	$\displaystyle P_{6}$	$\displaystyle=$	$\displaystyle v_{23}v_{12}.$

Observe that these cycles and paths are pairwise disjoint, and $U=V-\big{(}V(C_{1})\cup V(P_{2})\cup V(C_{3})\cup V(P_{4})\cup V(P_{5})\cup V(P_{6})\big{)}=\{v_{4}\}$ . Their sets of differences are, in order of appearance:

$\displaystyle{\mathcal{D}}(C_{1})$	$\displaystyle=$	$\displaystyle\{12,-9,8,-7,-4\},$
$\displaystyle{\mathcal{D}}(P_{2})$	$\displaystyle=$	$\displaystyle\{1,-2,3\},$
$\displaystyle{\mathcal{D}}(C_{3})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(C_{1}),$
$\displaystyle{\mathcal{D}}(P_{4})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{2}),$
$\displaystyle{\mathcal{D}}(P_{5})$	$\displaystyle=$	$\displaystyle\{6,11,-6\},\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{6})$	$\displaystyle=$	$\displaystyle\{-11\}.$

Thus, these paths and cycles jointly use exactly one arc of each difference in ${\mathcal{D}}$ . We next extend the three directed 3-paths $P_{2},P_{4},P_{5}$ to directed 5-cycles $C_{2},C_{4},C_{5}$ using a distinct vertex in $\{x_{0},x_{1},x_{2}\}$ , and we extend the directed 1-path $P_{6}$ to a directed 5-cycle $C_{6}$ using vertices $x_{3},v_{4},x_{4}$ .

Let $R=C_{1}\cup\ldots\cup C_{6}$ , so $R$ is a $\vec{C}_{5}$ -factor in $D$ . Then $\{\rho^{i}(R):i\in\mathbb{Z}_{25}\}$ is a $\vec{C}_{5}$ -factorization of $D$ .

Case 2: $t=4k+1$ for an integer $k\geq 2$ . Now $D[V]$ is a circulant digraph with vertex set $V=\{v_{i}:i\in\mathbb{Z}_{20k+5}\}$ and connection set ${\mathcal{D}}=\{\pm d:1\leq d\leq 10k+2,d\not\equiv 0\pmod{5}\}$ .

Define the following two directed $(4k-1)$ -paths (see Figure 6):

	$\displaystyle P_{1}$	$\displaystyle=$	$\displaystyle v_{0}v_{1}v_{-1}v_{2}v_{-2}v_{4}v_{-3}v_{5}v_{-4}v_{7}\ldots v_{-(2k-3)}v_{3k-4}v_{-(2k-2)}v_{3k-2}v_{-(2k-1)}v_{3k-1}\quad\mbox{ and }$
	$\displaystyle P_{2}$	$\displaystyle=$	$\displaystyle v_{-2k}v_{3k+1}v_{-(2k+1)}v_{3k+2}v_{-(2k+2)}v_{3k+4}\ldots v_{-(4k-3)}v_{6k-4}v_{-(4k-2)}v_{6k-2}v_{-(4k-1)}v_{6k-1}.$

For $i=1,2$ , let $P_{i+2}$ be the directed $(4k-1)$ -path obtained from $P_{i}$ by applying $\rho^{10k+3}=\rho^{-(10k+2)}$ and changing the direction. Thus,

	$\displaystyle P_{3}$	$\displaystyle=$	$\displaystyle v_{-(7k+3)}v_{8k+4}\ldots v_{-(10k+1)}v_{-(10k+2)}\quad\mbox{ and }$
	$\displaystyle P_{4}$	$\displaystyle=$	$\displaystyle v_{-(4k+3)}v_{6k+4}\ldots v_{-(7k+1)}v_{8k+3}.$

Observe that these paths are pairwise disjoint, and use all vertices in $V$ except those in

$\displaystyle V-\bigcup_{i=1}^{4}V(P_{i})$	$\displaystyle=$	$\displaystyle\{v_{3},v_{6},v_{9},\ldots,v_{6k-3}\}\cup\{v_{6k},v_{6k+1},v_{6k+2},v_{6k+3}\}$
		$\displaystyle\cup\{v_{-(10k-1)},v_{-(10k-4)},v_{-(10k-7)},\ldots,v_{-(4k+5)}\}$
		$\displaystyle\cup\{v_{-(4k+2)},v_{-(4k+1)},v_{-4k}\}.$

The sets of differences of these paths, listing the differences in their order of appearance, are:

$\displaystyle{\mathcal{D}}(P_{1})$	$\displaystyle=$	$\displaystyle\{1,-2,3,-4,6,-7,8,-9,\ldots,-(5k-6),5k-4,-(5k-3),5k-2\},$
$\displaystyle{\mathcal{D}}(P_{2})$	$\displaystyle=$	$\displaystyle\{5k+1,-(5k+2),5k+3,-(5k+4),5k+6,\ldots,$
		$\displaystyle\;\ldots,-(10k-6),10k-4,-(10k-3),10k-2\},$
$\displaystyle{\mathcal{D}}(P_{3})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{1}),\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{4})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{2}).$

Thus, these paths jointly use exactly one arc of each difference in ${\mathcal{D}}-{\mathcal{D}}^{\prime}$ , where

{\mathcal{D}}^{\prime}=\{\pm(5k-1),\pm(10k-1),\pm(10k+1),\pm(10k+2))\}.

The remaining two directed paths depend on the congruency class of $k$ modulo 3.

If $k\equiv 0\pmod{3}$ , we let

	$\displaystyle P_{5}$	$\displaystyle=$	$\displaystyle v_{k}v_{-(9k-1)}v_{-4k}v_{6k+1}v_{-(4k+2)}v_{6k-3}\quad\mbox{ and }$
	$\displaystyle P_{6}$	$\displaystyle=$	$\displaystyle v_{6k}v_{-(4k+1)}v_{6k+2}v_{k+3}.$

See Figure 7. The sets of differences of these paths are

	$\displaystyle{\mathcal{D}}(P_{5})$	$\displaystyle=$	$\displaystyle\{-(10k-1),5k-1,10k+1,10k+2,10k-1\}\quad\mbox{ and }$
	$\displaystyle{\mathcal{D}}(P_{6})$	$\displaystyle=$	$\displaystyle\{-(10k+1),-(10k+2),-(5k-1)\}.$

If $k\equiv 1\pmod{3}$ , we let

	$\displaystyle P_{5}$	$\displaystyle=$	$\displaystyle v_{6k+2}v_{-(4k+2)}v_{6k-3}v_{-(4k+5)}v_{6k+1}v_{k+2}\quad\mbox{ and }$
	$\displaystyle P_{6}$	$\displaystyle=$	$\displaystyle v_{-(4k+1)}v_{6k+3}v_{-4k}v_{k-1}.$

In this case, we have

	$\displaystyle{\mathcal{D}}(P_{5})$	$\displaystyle=$	$\displaystyle\{10k+1,10k-1,-(10k+2),-(10k-1),-(5k-1)\}\quad\mbox{ and }$
	$\displaystyle{\mathcal{D}}(P_{6})$	$\displaystyle=$	$\displaystyle\{-(10k+1),10k+2,5k-1\}.$

If $k\equiv 2\pmod{3}$ , we take

	$\displaystyle P_{5}$	$\displaystyle=$	$\displaystyle v_{-(4k+2)}v_{6k+2}v_{-(4k+1)}v_{6k}v_{k+1}v_{-(9k-2)}\quad\mbox{ and }$
	$\displaystyle P_{6}$	$\displaystyle=$	$\displaystyle v_{k+7}v_{-(9k-5)}v_{k+4}v_{6k+3}.$

The sets of differences are

	$\displaystyle{\mathcal{D}}(P_{5})$	$\displaystyle=$	$\displaystyle\{-(10k+1),10k+2,10k+1,-(5k-1),-(10k-1)\}\quad\mbox{ and }$
	$\displaystyle{\mathcal{D}}(P_{6})$	$\displaystyle=$	$\displaystyle\{-(10k+2),10k-1,5k-1\}.$

In all three cases, paths $P_{1},\ldots,P_{6}$ are pairwise disjoint, and jointly contain exactly one arc of each difference in ${\mathcal{D}}$ . Moreover, the set of unused vertices $U$ has cardinality $|U|=(20k+5)-4\cdot 4k-6-4=4k-5$ . Hence we may label $U=\{u_{i}:i\in\mathbb{Z}_{4k-5}\}$ .

Finally, we extend the four directed paths $P_{1},\ldots,P_{4}$ to disjoint directed $(4k+1)$ -cycles by adjoining one vertex from $\{x_{0},\ldots,x_{3}\}$ to each, extend the directed 5-path $P_{5}$ to a directed $(4k+1)$ -cycle $C_{5}$ by adjoining vertices $x_{4},u_{0},x_{5},u_{1},\ldots,u_{2k-4},x_{2k+1}$ , and extend the directed 3-path $P_{6}$ to a directed $(4k+1)$ -cycle $C_{6}$ by adjoining vertices $x_{2k+2},u_{2k-3},x_{2k+3},u_{2k-2},\ldots,$ $u_{4k-6},x_{4k}$ .

Finally, let $R=C_{1}\cup\ldots\cup C_{6}$ , so $R$ is a $\vec{C}_{t}$ -factor in $D$ . Since the permutation $\rho$ fixes the vertices of $X$ pointwise, it is not difficult to verify that $\{\rho^{i}(R):i\in\mathbb{Z}_{5t}\}$ is a $\vec{C}_{t}$ -factorization of $D$ .

Case 3: $t=4k+3$ for an integer $k\geq 1$ . Now $D[V]$ is a circulant digraph with vertex set $V=\{v_{i}:i\in\mathbb{Z}_{20k+15}\}$ and connection set ${\mathcal{D}}=\{\pm d:1\leq d\leq 10k+7,d\not\equiv 0\pmod{5}\}$ .

Define the following two directed $(4k+1)$ -paths:

	$\displaystyle P_{1}$	$\displaystyle=$	$\displaystyle v_{0}v_{1}v_{-1}v_{2}v_{-2}v_{4}v_{-3}v_{5}v_{-4}v_{7}\ldots v_{-(2k-2)}v_{3k-2}v_{-(2k-1)}v_{3k-1}v_{-2k}v_{3k+1}\quad\mbox{ and }$
	$\displaystyle P_{2}$	$\displaystyle=$	$\displaystyle v_{-(2k+1)}v_{3k+2}v_{-(2k+2)}v_{3k+4}\ldots v_{-(4k-1)}v_{6k-1}v_{-4k}v_{6k+1}v_{-(4k+1)}v_{6k+2}.$

For $i=1,2$ , let $P_{i+2}$ be the directed $(4k+1)$ -path obtained from $P_{i}$ by applying $\rho^{10k+8}=\rho^{-(10k+7)}$ and changing the direction. Thus,

	$\displaystyle P_{3}$	$\displaystyle=$	$\displaystyle v_{-(7k+6)}v_{8k+8}\ldots v_{-(10k+6)}v_{-(10k+7)}\quad\mbox{ and }$
	$\displaystyle P_{4}$	$\displaystyle=$	$\displaystyle v_{-(4k+5)}v_{6k+7}\ldots v_{-(7k+5)}v_{8k+7}.$

Observe that these paths are pairwise disjoint, and use all vertices in $V$ except those in

$\displaystyle V-\bigcup_{i=1}^{4}V(P_{i})$	$\displaystyle=$	$\displaystyle\{v_{3},v_{6},v_{9},\ldots,v_{6k}\}\cup\{v_{6k+3},v_{6k+4},v_{6k+5},v_{6k+6}\}$
		$\displaystyle\cup\{v_{-(10k+4)},v_{-(10k+1)},v_{-(10k-2)},\ldots,v_{-(4k+7)}\}$
		$\displaystyle\cup\{v_{-(4k+4)},v_{-(4k+3)},v_{-(4k+2)}\}.$

The sets of differences of these paths, listing the differences in their order of appearance, are:

$\displaystyle{\mathcal{D}}(P_{1})$	$\displaystyle=$	$\displaystyle\{1,-2,3,-4,6,-7,8,-9,\ldots,-(5k-3),5k-2,-(5k-1),5k+1\},$
$\displaystyle{\mathcal{D}}(P_{2})$	$\displaystyle=$	$\displaystyle\{5k+3,-(5k+4),5k+6,\ldots,\ldots,-(10k-1),10k+1,-(10k+2),10k+3\},$
$\displaystyle{\mathcal{D}}(P_{3})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{1}),\quad\mbox{ and }$
$\displaystyle{\mathcal{D}}(P_{4})$	$\displaystyle=$	$\displaystyle-{\mathcal{D}}(P_{2}).$

Thus, these paths jointly use exactly one arc of each difference in ${\mathcal{D}}-{\mathcal{D}}^{\prime}$ , where

{\mathcal{D}}^{\prime}=\{\pm(5k+2),\pm(10k+4),\pm(10k+6),\pm(10k+7)\}.

The remaining two directed paths depend on the congruency class of $k$ modulo 3. Since $t=4k+3$ is prime, we may assume $k\not\equiv 0\pmod{3}$ .

If $k\equiv 1\pmod{3}$ , we let

	$\displaystyle P_{5}$	$\displaystyle=$	$\displaystyle v_{6k+6}v_{-(4k+3)}v_{-(9k+5)}v_{k+2}v_{6k+4}v_{-(4k+7)}\quad\mbox{ and }$
	$\displaystyle P_{6}$	$\displaystyle=$	$\displaystyle v_{6k}v_{-(4k+4)}v_{6k+5}v_{-(4k+2)}.$

The sets of differences of these paths are

	$\displaystyle{\mathcal{D}}(P_{5})$	$\displaystyle=$	$\displaystyle\{10k+6,-(5k+2),10k+7,5k+2,10k+4\}\quad\mbox{ and }$
	$\displaystyle{\mathcal{D}}(P_{6})$	$\displaystyle=$	$\displaystyle\{-(10k+4),-(10k+6),-(10k+7)\}.$

If $k\equiv 2\pmod{3}$ , we take

	$\displaystyle P_{5}$	$\displaystyle=$	$\displaystyle v_{-(4k+4)}v_{6k+5}v_{-(4k+3)}v_{6k+3}v_{k+1}v_{-(9k+3)}\quad\mbox{ and }$
	$\displaystyle P_{6}$	$\displaystyle=$	$\displaystyle v_{k+7}v_{-9k}v_{k+4}v_{6k+6}.$

The sets of differences are

	$\displaystyle{\mathcal{D}}(P_{5})$	$\displaystyle=$	$\displaystyle\{-(10k+6),10k+7,10k+6,-(5k+2),-(10k+4)\}\quad\mbox{ and }$
	$\displaystyle{\mathcal{D}}(P_{6})$	$\displaystyle=$	$\displaystyle\{-(10k+7),10k+4,5k+2\}.$

In both cases, paths $P_{1},\ldots,P_{6}$ are pairwise disjoint, and jointly contain exactly one arc of each difference in ${\mathcal{D}}$ . Moreover, the set of unused vertices $U$ has cardinality $|U|=(20k+15)-4\cdot(4k+2)-6-4=4k-3$ . Hence we may label $U=\{u_{i}:i\in\mathbb{Z}_{4k-3}\}$ .

Finally, we extend the four directed paths $P_{1},\ldots,P_{4}$ to disjoint directed $(4k+3)$ -cycles by adjoining one vertex from $\{x_{0},\ldots,x_{3}\}$ to each, extend the directed 5-path $P_{5}$ to a directed $(4k+3)$ -cycle $C_{5}$ by adjoining vertices $x_{4},u_{0},x_{5},u_{1},\ldots,u_{2k-3},x_{2k+2}$ , and extend the directed 3-path $P_{6}$ to a directed $(4k+3)$ -cycle $C_{6}$ by adjoining vertices $x_{2k+3},u_{2k-2},x_{2k+4},u_{2k-1},\ldots,$ $u_{4k-4},x_{4k+2}$ .

The construction is then completed as in Case 2. a

Corollary 6.7

Assume $m\geq 3$ is odd, $n\equiv 0\pmod{6}$ , $t|mn$ , and $\gcd(t,n)=1$ . Then $K_{n[m]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization.

Proof. If $n\equiv 0\pmod{4}$ , then Corollary 6.5 yields the desired result. Hence we may assume that $n=6s$ for $s$ odd. By Lemma 6.6, there exists a $\vec{C}_{t}$ -factorization of $K_{6[t]}^{\ast}$ . Hence by Corollary 6.2(2), there exists a $\vec{C}_{t}$ -factorization of $K_{6s[t]}^{\ast}$ . a

7 $\vec{C}_{t}$ -factorizaton of $K_{4[m]}^{*}$ with $m$ odd and $\gcd(4,t)=4$

In this section, we settle the first exception from Proposition 5.1(1).

Lemma 7.1

Let $p$ be an odd prime. Then $K_{4[p]}^{\ast}$ admits

(a)

a $\vec{C}_{4p}$ -factorization and
(b)

a $\vec{C}_{4}$ -factorization.

Proof. Let the vertex set of $D=K_{4[p]}^{\ast}$ be $V\cup X$ , where $V$ and $X$ are disjoint sets, with $V=\{v_{i}:i\in\mathbb{Z}_{3p}\}$ and $X=\{x_{i}:i\in\mathbb{Z}_{p}\}$ . The four parts (holes) of $D$ are $X$ and $V_{r}=\{v_{3i+r}:i=0,1,\ldots,p-1\}$ , for $r=0,1,2$ . Note that $D[V]$ is a circulant digraph with connection set (set of differences) ${\mathcal{D}}=\{d\in\mathbb{Z}_{3p}:d\not\equiv 0\pmod{3}\}=\{\pm 1,\pm 2,\pm 4,\pm 5,\pm 7,\ldots,\pm\frac{3p-5}{2},\pm\frac{3p-1}{2}\}$ . Let $\rho$ be the permutation $\rho=(v_{0}\,v_{1}\,\ldots\,v_{3p-1})$ , fixing $X$ pointwise.

First, for each $i\in\{0,1,2,\ldots,\frac{p-3}{2}\}$ , we define the directed 2-path

P_{i}=v_{-2i}v_{i+1}v_{-(2i+1)}

with the set of differences

{\mathcal{D}}(P_{i})=\{3i+1,-(3i+2)\}.

See Figure 8. Let $Q_{i}$ be the directed 2-path obtained from $P_{i}$ by applying $\rho^{\frac{3p-1}{2}}$ and reversing the direction; that is,

Q_{i}=v_{-2i+\frac{3p-3}{2}}v_{i+\frac{3p+1}{2}}v_{-2i+\frac{3p-1}{2}}

and

{\mathcal{D}}(Q_{i})=\{-(3i+1),3i+2\}.

Observe that directed 2-paths $P_{0},\ldots,P_{\frac{p-3}{2}},Q_{0},\ldots,Q_{\frac{p-3}{2}}$ are pairwise disjoint and use all vertices in the set $V-U$ , where

U=\left\{\frac{p+1}{2},2p,2p+1\right\}.

Moreover, they jointly use exactly one arc of each difference in

{\mathcal{D}}-\left\{\pm\frac{3p-1}{2}\right\}.

The rest of the construction depends on the statement to be proved.

(a)

Let

P=v_{2p+1}v_{\frac{p+1}{2}},\quad Q=Q_{0}v_{\frac{3p-1}{2}}v_{0}P_{0},\quad\mbox{ and }\quad R=v_{2p},

so $P$ is directed 1-path, $Q$ is a directed 5-path, and $R$ is a directed 0-path, with

{\mathcal{D}}(P)=\left\{\frac{3p-1}{2}\right\},\quad{\mathcal{D}}(Q)=\left\{\pm 1,\pm 2,-\frac{3p-1}{2}\right\},\quad\mbox{ and }\quad{\mathcal{D}}(R)=\emptyset.

Directed paths $P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}},P,Q,$ and $R$ are pairwise disjoint, use all vertices in the set $V$ , and jointly use exactly one arc of each difference in ${\mathcal{D}}$ . As there are $p$ of these paths, we can use the $p$ vertices of $X$ to join them into a directed Hamilton cycle $C$ of $D$ ; for example, as follows:

\displaystyle C

\displaystyle=

\displaystyle P_{1}v_{-3}x_{0}v_{-4}P_{2}v_{-5}x_{1}\ldots Q_{\frac{p-3}{2}}v_{\frac{p+5}{2}}x_{p-4}v_{2p+1}Pv_{\frac{p+1}{2}}x_{p-3}v_{\frac{3p-3}{2}}Qv_{-1}x_{p-2}v_{2p}Rv_{2p}x_{p-1}v_{-2}.

Then $\{\rho^{i}(C):i\in\mathbb{Z}_{3p}\}$ is the required $\vec{C}_{4p}$ -factorization of $D$ .

(b)

Several cases will need to be considered.

Case $p\geq 5$ . Note that, since $p$ is prime, we have $p\not\equiv 0\pmod{3}$ .

First, define a directed 4-cycle

C_{0}=v_{-1}v_{1}v_{\frac{3p+1}{2}}v_{\frac{3p-3}{2}}v_{-1}

with

{\mathcal{D}}(C_{0})=\left\{\pm 2,\pm\frac{3p-1}{2}\right\}.

Subcase $p\equiv 1\pmod{3}$ . We will use directed 2-paths $P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}}$ defined earlier, except that we replace

Q_{\frac{p-1}{3}}=v_{\frac{5p-5}{6}}v_{\frac{11p+1}{6}}v_{\frac{5p+1}{6}}

with

Q_{\frac{p-1}{3}}^{\prime}=v_{\frac{5p+1}{6}}v_{\frac{5p-5}{6}}v_{\frac{11p+1}{6}}.

In addition, we let

R=v_{0}v_{2p}v_{2p+1}.

Observe that directed 2-paths $P_{\frac{p-1}{3}}$ , $Q_{\frac{p-1}{3}}^{\prime}$ , and $R$ jointly use each difference in $\{\pm 1,\pm p,$ $\pm(p+1)\}$ exactly once, and the $p-2$ paths $R,P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-4}{3}}Q_{\frac{p-1}{3}}^{\prime}Q_{\frac{p+2}{3}}\ldots Q_{\frac{p-3}{2}}$ , together with the 4-cycle $C_{0}$ , jointly use each difference in ${\mathcal{D}}$ exactly once. In addition, these paths and the cycle are pairwise disjoint, and vertices $v_{\frac{p+1}{2}}$ and $v_{\frac{3p-1}{2}}$ are the only vertices of $V$ that lie in none of them. We now use vertices $x_{0},\ldots,x_{p-3}$ to complete the $p-2$ directed 2-paths into directed 4-cycles $C_{1},\ldots,C_{p-2}$ , and finally define

C_{p-1}=v_{\frac{p+1}{2}}x_{p-2}v_{\frac{3p-1}{2}}x_{p-1}v_{\frac{p+1}{2}}.

Let $F=C_{0}\cup C_{1}\cup\ldots\cup C_{p-1}$ . Then $\{\rho^{i}(F):i\in\mathbb{Z}_{3p}\}$ is the required $\vec{C}_{4}$ -factorization of $D$ .

Subcase $p\equiv 2\pmod{3}$ . This subcase is similar, so we only highlight the differences. Again, we use directed 2-paths $P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}}$ defined earlier, except that we first replace directed 2-paths $P_{\frac{p-3}{2}}$ and $Q_{\frac{p-3}{2}}$ with

P_{\frac{p-3}{2}}^{\prime}=v_{\frac{p-1}{2}}v_{2p+3}v_{\frac{p+1}{2}}\quad\mbox{ and }\quad Q_{\frac{p-3}{2}}^{\prime}=v_{2p}v_{\frac{p+5}{2}}v_{2p-1},

which cover the same differences, namely, $\pm\frac{3p-5}{2}$ and $\pm\frac{3p-7}{2}$ , but use vertices $v_{\frac{p+1}{2}}$ and $v_{2p}$ instead of vertices $v_{2p+2}$ and $v_{\frac{p+3}{2}}$ , respectively. We also replace

Q_{\frac{p-2}{3}}=v_{\frac{5p-1}{6}}v_{\frac{11p-1}{6}}v_{\frac{5p+5}{6}}

with

Q_{\frac{p-2}{3}}^{\prime}=v_{\frac{5p+5}{6}}v_{\frac{5p-1}{6}}v_{\frac{11p-1}{6}},

and additionally define

R=v_{0}v_{2p+1}v_{2p+2}.

Observe that directed 2-paths $P_{\frac{p-2}{3}}$ , $Q_{\frac{p-2}{3}}^{\prime}$ , and $R$ jointly use each difference in $\{\pm 1,\pm(p-1),\pm p\}$ exactly once, and the $p-2$ paths $R,P_{1},\ldots,P_{\frac{p-5}{2}},P_{\frac{p-3}{2}}^{\prime},Q_{1},\ldots,Q_{\frac{p-5}{3}},Q_{\frac{p-2}{3}}^{\prime},Q_{\frac{p+1}{3}},$ $\ldots,Q_{\frac{p-5}{2}},Q_{\frac{p-3}{2}}^{\prime}$ , together with the 4-cycle $C_{0}=v_{-1}v_{1}v_{\frac{3p+1}{2}}v_{\frac{3p-3}{2}}v_{-1}$ , jointly use each difference in ${\mathcal{D}}$ exactly once. Again, these paths and the cycle are pairwise disjoint, this time using all vertices in $V$ except $v_{\frac{p+3}{2}}$ and $v_{\frac{3p-1}{2}}$ . The construction is now completed as in the previous case.

Case $p=3$ . We have $V=\{v_{i}:i\in\mathbb{Z}_{9}\}$ and $X=\{x_{0},x_{1},x_{2}\}$ . We construct three starter $\vec{C}_{4}$ -factors, and use $\rho^{3}$ , where $\rho=(v_{0}\,v_{1}\,\ldots,\,v_{8})$ , to generate the rest.

Let ${\mathcal{D}}_{3}=\left\{d_{r}:d=\pm 1,\pm 2,\pm 4,r\in\mathbb{Z}_{3}\right\}$ . It will be helpful to keep track of the base-3 difference of each arc $(v_{i},v_{j})$ , defined as $d_{r}\in{\mathcal{D}}_{3}$ such that $j-i\equiv d\pmod{9}$ and $r\equiv i\pmod{3}$ .

Define the following directed 4-cycles in $D$ :

$\displaystyle C_{0}^{0}$	$\displaystyle=v_{0}v_{7}v_{3}x_{0}v_{0}$	$\displaystyle C_{1}^{0}=v_{7}v_{6}v_{5}x_{0}v_{7}$	$\displaystyle C_{2}^{0}=v_{5}v_{0}v_{4}x_{0}v_{5}$
$\displaystyle C_{0}^{1}$	$\displaystyle=v_{4}v_{2}v_{1}x_{1}v_{4}$	$\displaystyle C_{1}^{1}=v_{3}v_{4}v_{8}x_{1}v_{3}$	$\displaystyle C_{2}^{1}=v_{8}v_{1}v_{3}x_{1}v_{8}$
$\displaystyle C_{0}^{2}$	$\displaystyle=v_{5}v_{6}v_{8}x_{2}v_{5}$	$\displaystyle C_{1}^{2}=v_{1}v_{2}v_{0}x_{2}v_{1}$	$\displaystyle C_{2}^{2}=v_{6}v_{2}v_{7}x_{2}v_{6}$

Observe that each $F_{i}=C_{i}^{0}\cup C_{i}^{1}\cup C_{i}^{2}$ is a $\vec{C}_{4}$ -factor in $D$ , and that $F_{0},F_{1},F_{2}$ jointly contain exactly one arc of each base-3 difference in ${\mathcal{D}}_{3}$ . Moreover, for each $j,r\in\mathbb{Z}_{3}$ , the $\vec{C}_{4}$ -factors $F_{0},F_{1},F_{2}$ jointly contain exactly one arc of the form $(x_{j},v_{i})$ with $i\equiv r\pmod{3}$ , and exactly one arc of the form $(v_{i},x_{j})$ with $i\equiv r\pmod{3}$ . Consequently, $\{\rho^{3k}(F_{i}):i,k=0,1,2\}$ is a $\vec{C}_{4}$ -factorization of $K_{4[3]}^{\ast}$ .

Corollary 7.2

Assume $m\geq 3$ is odd, $t|4m$ , and $\gcd(4,t)=4$ . Then $K_{4[m]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization.

Proof. The assumptions imply that $t=4s$ for some odd $s\geq 1$ , and $s|m$ .

If $s=1$ , let $p$ be any prime factor of $m$ . Then by Lemma 7.1(b), the digraph $K_{4[p]}^{\ast}$ admits a $\vec{C}_{4}$ -factorization, and it follows from Corollary 4.2(a) that $K_{4[m]}^{\ast}\cong K_{4[p]}^{\ast}\wr\bar{K_{\frac{m}{p}}}$ admits a $\vec{C}_{4}$ -factorization.

If $s\geq 3$ , let $p$ be any prime factor of $s$ . Then by Lemma 7.1(a), the digraph $K_{4[p]}^{\ast}$ admits a $\vec{C}_{4p}$ -factorization. It now follows from Corollary 4.2(b) that $K_{4[s]}^{\ast}\cong K_{4[p]}^{\ast}\wr\bar{K_{\frac{s}{p}}}$ admits a $\vec{C}_{4s}$ -factorization. Finally, by Corollary 4.2(a), $K_{4[m]}^{\ast}$ admits a $\vec{C}_{4s}$ -factorization. a

8 $\vec{C}_{t}$ -factorizaton of $K_{6[m]}^{*}$ with $m$ odd and $\gcd(6,t)=6$

In this section, we settle the second exception from Proposition 5.1(1).

Lemma 8.1

Let $p$ be an odd prime. Then $K_{6[p]}^{\ast}$ admits

(a)

a $\vec{C}_{6p}$ -factorization and
(b)

a $\vec{C}_{6}$ -factorization.

Proof. Let the vertex set of $D=K_{6[p]}^{\ast}$ be $V\cup X$ , where $V$ and $X$ are disjoint sets, with $V=\{v_{i}:i\in\mathbb{Z}_{5p}\}$ and $X=\{x_{i}:i\in\mathbb{Z}_{p}\}$ . The six parts (holes) of $D$ are $X$ and $V_{r}=\{v_{5i+r}:i=0,1,\ldots,p-1\}$ , for $r=0,1,\ldots,4$ . Note that $D[V]$ is a circulant digraph with connection set (set of differences) ${\mathcal{D}}=\{d\in\mathbb{Z}_{5p}:d\not\equiv 0\pmod{5}\}=\{\pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\ldots,\pm\frac{5p-7}{2},\pm\frac{5p-3}{2},\pm\frac{5p-1}{2}\}$ . Let $\rho$ be the permutation $\rho=(v_{0}\,v_{1}\,\ldots\,v_{5p-1})$ , which fixes $X$ pointwise.

First, for each $i\in\{1,2,\ldots,\frac{p-3}{2}\}$ , we define the directed 4-path

P_{i}=v_{-3i}v_{2i+1}v_{-(3i+1)}v_{2i+2}v_{-(3i+2)}

with the set of differences

{\mathcal{D}}(P_{i})=\{5i+1,-(5i+2),5i+3,-(5i+4)\}.

See Figure 9. The rest of the construction depends on the statement to be proved.

(a)

Let $Q_{i}$ be the directed 4-path obtained from $P_{i}$ by applying $\rho^{\frac{5p-1}{2}}$ and reversing the direction; that is,

Q_{i}=v_{\frac{5p-5}{2}-3i}v_{\frac{5p+3}{2}+2i}v_{\frac{5p-3}{2}-3i}v_{\frac{5p+1}{2}+2i}v_{\frac{5p-1}{2}-3i}

and

{\mathcal{D}}(Q_{i})=\{-(5i+1),5i+2,-(5i+3),5i+4\}.

See Figure 9. Observe that directed 4-paths $P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}}$ are pairwise disjoint and use all vertices in the set $V-U$ , where

U=\left\{v_{-2},v_{-1},v_{0},v_{1},v_{2},v_{p},v_{p+1},v_{\frac{5p-5}{2}},v_{\frac{5p-3}{2}},v_{\frac{5p-1}{2}},v_{\frac{5p+1}{2}},v_{\frac{5p+3}{2}},v_{\frac{7p-1}{2}},v_{\frac{7p+1}{2}},v_{\frac{7p+3}{2}}\right\}.

Moreover, they jointly use exactly one arc of each difference in ${\mathcal{D}}-{\mathcal{D}}^{\prime}$ , where

{\mathcal{D}}^{\prime}=\left\{\pm 1,\pm 2,\pm 3,\pm 4,\pm\frac{5p-3}{2},\pm\frac{5p-1}{2}\right\}.

Additionally, define directed paths

$\displaystyle P_{0}$	$\displaystyle=$	$\displaystyle v_{\frac{5p-5}{2}}v_{\frac{5p+3}{2}}v_{\frac{5p-3}{2}}v_{\frac{5p+1}{2}}v_{\frac{5p-1}{2}}v_{0}v_{1}v_{-1}v_{2}v_{-2},$
$\displaystyle R_{1}$	$\displaystyle=$	$\displaystyle v_{p+1}v_{\frac{7p-1}{2}},\quad\mbox{ and }$
$\displaystyle R_{2}$	$\displaystyle=$	$\displaystyle v_{\frac{7p+1}{2}}v_{p}v_{\frac{7p+3}{2}},$

and observe that ${\mathcal{D}}(P_{0}\cup R_{1}\cup R_{2})={\mathcal{D}}^{\prime}$ .

The $p$ directed paths $P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}},P_{0},R_{1},R_{2}$ are pairwise disjoint, use all vertices in $V$ , and jointly use exactly one arc of each difference in ${\mathcal{D}}$ . Hence we can use the $p$ vertices of $X$ to join them into a directed Hamilton cycle $C$ of $D$ , similarly to the proof of Lemma 7.1(a). Then $\{\rho^{i}(C):i\in\mathbb{Z}_{5p}\}$ is the required $\vec{C}_{6p}$ -factorization of $D$ .

(b)

In this case, let $Q_{i}$ be the directed 2-path obtained from $P_{i}$ by applying $\rho^{\frac{5p-3}{2}}$ and reversing the direction; that is,

Q_{i}=v_{\frac{5p-7}{2}-3i}v_{\frac{5p+1}{2}+2i}v_{\frac{5p-5}{2}-3i}v_{\frac{5p-1}{2}+2i}v_{\frac{5p-3}{2}-3i}

and, again,

{\mathcal{D}}(Q_{i})=\{-(5i+1),5i+2,-(5i+3),5i+4\}.

Observe that directed 4-paths $P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}}$ are pairwise disjoint and use all vertices in the set $V-U$ , where

U=\left\{v_{-2},v_{-1},v_{0},v_{1},v_{2},v_{p},v_{\frac{5p-7}{2}},v_{\frac{5p-5}{2}},v_{\frac{5p-3}{2}},v_{\frac{5p-1}{2}},v_{\frac{5p+1}{2}},v_{\frac{7p-3}{2}},v_{\frac{7p-1}{2}},v_{\frac{7p+1}{2}},v_{\frac{7p+3}{2}}\right\}.

Moreover, they jointly use exactly one arc of each difference in ${\mathcal{D}}-{\mathcal{D}}^{\prime}$ , where

{\mathcal{D}}^{\prime}=\left\{\pm 1,\pm 2,\pm 3,\pm 4,\pm\frac{5p-3}{2},\pm\frac{5p-1}{2}\right\}.

Additionally, on vertex set $U$ , define the following directed 6-cycle and two directed paths:

$\displaystyle C_{0}$	$\displaystyle=$	$\displaystyle v_{-1}v_{2}v_{-2}v_{\frac{5p-7}{2}}v_{\frac{5p+1}{2}}v_{\frac{5p-5}{2}}v_{-1},$
$\displaystyle R_{1}$	$\displaystyle=$	$\displaystyle v_{p}v_{\frac{7p-1}{2}}v_{\frac{7p+3}{2}}v_{\frac{7p+1}{2}}v_{\frac{7p-3}{2}},\quad\mbox{ and }$
$\displaystyle R_{2}$	$\displaystyle=$	$\displaystyle v_{\frac{5p-1}{2}}v_{0}v_{1},$

and observe that ${\mathcal{D}}(P_{0}\cup R_{1}\cup R_{2})={\mathcal{D}}^{\prime}$ .

Observe that the $p-1$ directed paths $P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}},R_{1},R_{2}$ , together with the directed 6-cycle $C_{0}$ , jointly use each difference in ${\mathcal{D}}$ exactly once. In addition, these paths and the cycle are pairwise disjoint, using each vertex in $V$ except $v_{\frac{5p-3}{2}}$ . We now use vertices $x_{0},\ldots,x_{p-3}$ to complete the $p-2$ directed 4-paths $P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}},R_{1}$ into directed 6-cycles $C_{1},\ldots,C_{p-2}$ , and finally use vertices $x_{p-2},v_{\frac{5p-3}{2}},x_{p-1}$ to complete the directed 2-path $R_{2}$ to a directed 6-cycle $C_{p-1}$ .

Let $F=C_{0}\cup\ldots\cup C_{p-1}$ . Then $\{\rho^{i}(F):i\in\mathbb{Z}_{5p}\}$ is a $\vec{C}_{6}$ -factorization of $D$ .

Corollary 8.2

Assume $m\geq 3$ is odd, $t|6m$ , and $\gcd(6,t)=6$ . Then $K_{6[m]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization.

Proof. The proof is analogous to the proof of Corollary 7.2, using Lemma 8.1 instead of Lemma 7.1. a

9 $\vec{C}_{t}$ -factorizaton of $K_{6[m]}^{*}$ with $m$ odd and $\gcd(6,t)=3$

We shall now address the exceptional case from Proposition 5.1(2).

Lemma 9.1

Let $p$ be an odd prime. Then $K_{6[p]}^{\ast}$ admits

(a)

a $\vec{C}_{3p}$ -factorization and
(b)

if $p\leq 37$ , also a $\vec{C}_{3}$ -factorization.

Proof. As in the proof of Lemma 8.1, let the vertex set of $D=K_{6[p]}^{\ast}$ be $V\cup X$ , where $V=\{v_{i}:i\in\mathbb{Z}_{5p}\}$ and $X=\{x_{i}:i\in\mathbb{Z}_{p}\}$ , so $D[V]$ is a circulant digraph with connection set ${\mathcal{D}}=\{d\in\mathbb{Z}_{5p}:d\not\equiv 0\pmod{5}\}$ . Let $\rho$ be the permutation $\rho=(v_{0}\,v_{1}\,\ldots\,v_{5p-1})$ .

(a)

First assume $p\geq 5$ . This is very similar to the proof of Lemma 8.1(a).

For each $i\in\{1,2,\ldots,\frac{p-3}{2}\}$ , define the directed 4-paths $P_{i}$ and $Q_{i}$ , as well as directed paths $P_{0},R_{1}$ , and $R_{2}$ exactly as in the proof of Lemma 8.1(a). (See Figure 9.) Recall that the $p$ directed paths $P_{1},\ldots,P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}},P_{0},R_{1},R_{2}$ are pairwise disjoint, use all vertices in $V$ , and jointly use exactly one arc of each difference in ${\mathcal{D}}$ .

We join the $\frac{p-1}{2}$ directed paths $P_{0},R_{2},P_{1},\ldots,P_{\frac{p-5}{2}}$ into a directed cycle $C_{1}$ using $\frac{p-1}{2}$ vertices of $X$ . The length of $C_{1}$ is $9+2+4\cdot\frac{p-5}{2}+2\cdot\frac{p-1}{2}=3p$ , as required. We then join the remaining $\frac{p+1}{2}$ directed paths — namely, $R_{1},P_{\frac{p-3}{2}},Q_{1},\ldots,Q_{\frac{p-3}{2}}$ — into a directed cycle $C_{2}$ using the remaining $\frac{p+1}{2}$ vertices of $X$ . The length of $C_{2}$ is $1+4\cdot\frac{p-1}{2}+2\cdot\frac{p+1}{2}=3p$ , again as required.

Let $F=C_{1}\cup C_{2}$ . Then $\{\rho^{i}(F):i\in\mathbb{Z}_{5p}\}$ is a $\vec{C}_{3p}$ -factorization of $D$ .

Now let $p=3$ , so $V=\{v_{i}:i\in\mathbb{Z}_{15}\}$ and ${\mathcal{D}}=\{\pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 7\}$ . Define the directed paths

$\displaystyle P_{1}$	$\displaystyle=$	$\displaystyle v_{7}v_{0}v_{1}v_{-1}v_{2}v_{-2}v_{-3}v_{3},$
$\displaystyle P_{2}$	$\displaystyle=$	$\displaystyle v_{-5}v_{4}v_{-4},\quad\mbox{ and }$
$\displaystyle P_{3}$	$\displaystyle=$	$\displaystyle v_{6}v_{-7}v_{5}v_{-6},$

and observe that they are pairwise disjoint, and jointly use exactly one arc of each difference in ${\mathcal{D}}$ . Use vertex $x_{0}$ to extend $P_{1}$ to a directed 9-cycle $C_{1}$ , and use vertices $x_{1}$ and $x_{2}$ to join $P_{1}$ and $P_{2}$ into a directed 9-cycle $C_{2}$ . Then $\{\rho^{i}(F):i\in\mathbb{Z}_{15}\}$ , for $F=C_{1}\cup C_{2}$ , is a $\vec{C}_{9}$ -factorization of $D$ .

(b)
It suffices to show that $K_{5[p]}^{\ast}$ admits a spanning subdigraph $D^{\prime}$ with the following properties:
1. (i)
  
  $D^{\prime}$ is a disjoint union of $p$ copies of $\vec{C}_{3}$ and $p$ copies of $\vec{P}_{1}$ , the directed 1-path; and
2. (ii)
  
  $D^{\prime}$ contains exactly one arc of each difference in ${\mathcal{D}}$ .
Let $F$ be obtained from $D^{\prime}$ by completing each copy of $\vec{P}_{1}$ to a $\vec{C}_{3}$ using a distinct vertex in $X$ . It then follows that $\{\rho^{i}(F):i\in\mathbb{Z}_{5p}\}$ is a $\vec{C}_{3}$ -factorization of $D$ .
Computationally, we have verified the existence of a suitable subdigraph $D^{\prime}$ of $K_{5[p]}^{\ast}$ for all primes $p$ , $3\leq p\leq 37$ (see Appendix A). Since the existence of a $\vec{C}_{3}$ -factorization of $K_{6[p]}^{\ast}$ for each odd prime $p<17$ is guaranteed by Theorem 1.4, only the cases with $17\leq p\leq 37$ are presented.

Corollary 9.2

Assume $m\geq 3$ is odd, $t|6m$ , and $\gcd(6,t)=3$ . Then $K_{6[m]}^{\ast}$ admits a $\vec{C}_{t}$ -factorization, except possibly when $t=3$ and $m$ is not divisible by any prime $p\leq 37$ .

Proof. The assumptions imply that $t=3s$ for some odd $s\geq 1$ , and $s|m$ .

If $s\geq 3$ , let $p$ be any prime factor of $s$ . Then by Lemma 9.1(a), the digraph $K_{6[p]}^{\ast}$ admits a $\vec{C}_{3p}$ -factorization. It now follows from Corollary 4.2(b) that $K_{6[s]}^{\ast}\cong K_{6[p]}^{\ast}\wr\bar{K_{\frac{s}{p}}}$ admits a $\vec{C}_{3s}$ -factorization. Finally, by Corollary 4.2(a), $K_{6[m]}^{\ast}$ admits a $\vec{C}_{3s}$ -factorization.

If $s=1$ , assume $m$ has a prime factor $p\leq 37$ . Then by Lemma 9.1(b), the digraph $K_{6[p]}^{\ast}$ admits a $\vec{C}_{3}$ -factorization, and it follows from Corollary 4.2(a) that $K_{6[m]}^{\ast}\cong K_{6[p]}^{\ast}\wr\bar{K_{\frac{m}{p}}}$ admits a $\vec{C}_{3}$ -factorization. a

10 Proof of Theorem 1.5 and conclusion

For convenience, we re-state the main result of this paper before summarizing its proof.

Theorem 1.5

Let $m$ , $n$ , and $t$ be integers greater than 1, and let $g=\gcd(n,t)$ . Assume one of the following conditions holds.

(i)

$m(n-1)$ even; or
(ii)

$g\not\in\{1,3\}$ ; or
(iii)

$g=1$ , and $n\equiv 0\pmod{4}$ or $n\equiv 0\pmod{6}$ ; or
(iv)

$g=3$ , and if $n=6$ , then $m$ is divisible by a prime $p\leq 37$ .

Then the digraph $K_{n[m]}^{*}$ admits a $\vec{C}_{t}$ -factorization if and only if $t|mn$ and $t$ is even in case $n=2$ .

Proof. If $K_{n[m]}^{*}$ admits a $\vec{C}_{t}$ -factorization, then clearly $t|mn$ , and $t$ is even when $n=2$ .

Now assume these necessary conditions hold.

If $m(n-1)$ is even, then a $\vec{C}_{t}$ -factorization of $K_{n[m]}^{*}$ exists by Corollary 3.2.

Hence assume $m(n-1)$ is odd. If $g\not\in\{1,3\}$ , then the result follows by Proposition 5.1, and Corollaries 7.2 and 8.2. If $g=1$ , the results for $n\equiv 0\pmod{4}$ and $n\equiv 0\pmod{6}$ follow by Corollaries 6.5 and 6.7, respectively.

Finally, the claim for $g=3$ follows from Proposition 5.1(2) if $n\neq 6$ , and from Corollary 9.2 if $n=6$ and $m$ is divisible by a prime $p\leq 37$ . a

We have thus solved several extensive cases of Problem 1.3. Since there are no exceptions in the cases with small parameters covered by Theorem 1.5, we propose the following conjecture.

Conjecture 10.1

Let $m$ , $n$ , and $t$ be positive integers. Then $K_{n[m]}^{*}$ admits a $\vec{C}_{t}$ -factorization if and only if $t|mn$ , $t$ is even in case $n=2$ , and $(m,n,t)\not\in\{(1,6,3),(1,4,4),(1,6,6)\}$ .

By Corollary 4.2, and Lemmas 6.1 and 9.1, to complete the proof of Conjecture 10.1, it suffices to prove existence of a $\vec{C}_{t}$ -factorization of $K_{n[m]}^{*}$ in the following cases:

(i)

$(m,n,t)=(t,2p,t)$ for a prime $p\geq 5$ and odd prime $t$ ; and
(ii)

$(m,n,t)=(m,6,3)$ for a prime $m\geq 41$ .

Acknowledgements

The second author gratefully acknowledges support by the Natural Sciences and Engineering Research Council of Canada (NSERC).

References

[1] P. Adams, D. Bryant, Resolvable directed cycle systems of all indices for cycle length 3 and 4, unpublished.
[2] P. Adams, D. Bryant, Two-factorisations of complete graphs of orders fifteen and seventeen, Australas. J. Combin. 35 (2006), 113–118.
[3] B. Alspach, H. Gavlas, M. Šajna, H. Verrall, Cycle decompositions IV: Complete directed graphs and fixed length directed cycles, J. Combin. Theory Ser. A 103 (2003), 165–208.
[4] B. Alspach, R. Häggkvist, Some observations on the Oberwolfach problem, J. Graph Theory 9 (1985), 177–187.
[5] B. Alspach, P. J. Schellenberg, D. R. Stinson, D. Wagner, The Oberwolfach problem and factors of uniform odd length cycles, J. Combin. Theory Ser. A 52 (1989), 20–43.
[6] F. E. Bennett, X. Zhang, Resolvable Mendelsohn designs with block size $4$ , Aequationes Math. 40 (1990), 248–260.
[7] F. E. Bennett, R. Wei, L. Zhu, Resolvable Mendelsohn triple systems with equal sized holes, J. Combin. Des. 5 (1997), 329–340.
[8] J.-C. Bermond, O. Favaron, M. Mahéo, Hamiltonian decomposition of Cayley graphs of degree 4, J. Combin. Theory Ser. B 46 (1989), 142–153.
[9] J.-C. Bermond, A. Germa, D. Sotteau, Resolvable decomposition of $K_{n}^{\ast}$ , J. Combin. Theory Ser. A 26 (1979), 179–185.
[10] D. Bryant, P. Danziger, On bipartite 2-factorizations of $K_{n}-I$ and the Oberwolfach problem, J. Graph Theory 68 (2011), 22–37.
[11] A. Burgess, N. Francetić, M. Šajna, On the directed Oberwolfach Problem with equal cycle lengths: the odd case, Australas. J. Combin. 71 (2018), 272–292.
[12] A. Burgess, M. Šajna, On the directed Oberwolfach problem with equal cycle lengths, Electron. J. Combin. 21 (2014), Paper 1.15, 14 pp.
[13] C. J. Colbourn, J. H. Dinitz (editors), Handbook of combinatorial designs, Chapman and Hall/CRC, Boca Raton, FL, 2007.
[14] A. Deza, F. Franek, W. Hua, M. Meszka, A. Rosa, Solutions to the Oberwolfach problem for orders 18 to 40, J. Combin. Math. Combin. Comput. 74 (2010), 95–102.
[15] F. Franek, J. Holub, A. Rosa, Two-factorizations of small complete graphs II: The case of 13 vertices, J. Combin. Math. Combin. Comput. 51 (2004), 89–94.
[16] F. Franek, A. Rosa, Two-factorizations of small complete graphs, J. Statist. Plann. Inference 86 (2000), 435–442.
[17] S. Glock, F. Joos, J. Kim, D. Kühn, D. Osthus, Resolution of the Oberwolfach problem, J. Eur. Math. Soc. 23 (2021), 2511–2547.
[18] D. G. Hoffman, P. J. Schellenberg, The existence of $C_{k}$ -factorizations of $K_{2n}-F$ , Discrete Math. 97 (1991), 243–250.
[19] C. Huang, A. Kotzig, A. Rosa, On a variation of the Oberwolfach problem, Discrete Math. 27 (1979), 261–277.
[20] A. Lacaze-Masmonteil, Resolution of the directed Oberwolfach problem with cycles of equal length, submitted, arXiv:2212.12072.
[21] J. Liu, The equipartite Oberwolfach problem with uniform tables, J. Combin. Theory Ser. A 101 (2003), 20–34.
[22] J. Liu, D. R. Lick, On $\lambda$ -fold equipartite Oberwolfach problem with uniform table sizes, Ann. Comb. 7 (2003), 315–323.
[23] L. Ng, Hamiltonian decomposition of complete regular multipartite digraphs, Discrete Math. 177 (1997), 279–285.
[24] P. Paulraja, S. Sivasankar, Directed Hamilton cycle decompositions of the tensor products of symmetric digraphs, Graphs Combin. 25 (2009), 571–581.
[25] W.-L. Piotrowski, The solution of the bipartite analogue of the Oberwolfach problem, Discrete Math. 97 (1991), 339–356.
[26] R. Rees, Two new direct product-type constructions for resolvable group-divisible designs, J. Comb. Des. 1 (1993), 15–26.
[27] F. Salassa, G. Dragotto, T. Traetta, M. Buratti, F. Della Croce, Merging combinatorial design and optimization: the Oberwolfach problem, Australas. J. Combin. 79 (2021), 141–166.
[28] T. W. Tillson, A hamiltonian decomposition of $K_{2m}^{\ast}$ , $2m\geq 8$ , J. Comb. Theory Ser. B 29 (1980), 69–74.
[29] T. Traetta, A complete solution to the two-table Oberwolfach problems, J. Combin. Theory Ser. A 120 (2013), 984–997.
[30] K. Ushio, Cycle-factorization of symmetric complete multipartite digraphs, Discrete Math. 199 (1999), 273–278.

Appendix A Starter digraphs for a $\vec{C}_{3}$ -factorization of $K_{6[p]}^{\ast}$

For each prime $p$ , $17\leq p\leq 37$ , we give a set ${\mathcal{C}}$ containing $p$ copies of $\vec{C}_{3}$ and a set ${\mathcal{P}}$ containing $p$ copies of $\vec{P}_{1}$ that together form a starter digraph $D^{\prime}$ for a $\vec{C}_{3}$ -factorization of $K_{6[p]}^{\ast}$ ; see the proof of Lemma 9.1(b).

•

$p=17$

$\displaystyle{\mathcal{C}}$	$\displaystyle=$	$\displaystyle\{v_{10}v_{21}v_{33}v_{10},v_{1}v_{74}v_{63}v_{1},v_{55}v_{64}v_{83}v_{55},v_{40}v_{68}v_{49}v_{40},v_{29}v_{37}v_{58}v_{29},v_{3}v_{67}v_{59}v_{3},$
		$\displaystyle v_{5}v_{12}v_{36}v_{5},v_{19}v_{50}v_{26}v_{19},v_{17}v_{75}v_{23}v_{17},v_{14}v_{20}v_{47}v_{14},v_{35}v_{39}v_{71}v_{35},v_{9}v_{45}v_{13}v_{9},$
		$\displaystyle v_{22}v_{70}v_{73}v_{22},v_{0}v_{82}v_{34}v_{0},v_{31}v_{77}v_{78}v_{31},v_{42}v_{81}v_{80}v_{42},v_{2}v_{44}v_{46}v_{2}\}$
$\displaystyle{\mathcal{P}}$	$\displaystyle=$	$\displaystyle\{v_{8}v_{6},v_{65}v_{24},v_{60}v_{18},v_{7}v_{79},v_{56}v_{69},v_{62}v_{76},v_{66}v_{52},v_{41}v_{57},v_{15}v_{84},v_{11}v_{28},v_{4}v_{72},$
		$\displaystyle v_{30}v_{48},v_{61}v_{43},v_{16}v_{38},v_{54}v_{32},v_{25}v_{51},v_{53}v_{27}\}$

•

$p=19$

$\displaystyle{\mathcal{C}}$	$\displaystyle=$	$\displaystyle\{v_{20}v_{32}v_{51}v_{20},v_{2}v_{78}v_{66}v_{2},v_{9}v_{26}v_{93}v_{9},v_{46}v_{74}v_{57}v_{46},v_{1}v_{10}v_{34}v_{1},v_{4}v_{37}v_{28}v_{4},$
		$\displaystyle v_{36}v_{70}v_{62}v_{36},v_{7}v_{33}v_{94}v_{7},v_{18}v_{77}v_{84}v_{18},v_{17}v_{83}v_{76}v_{17},v_{53}v_{59}v_{91}v_{53},v_{49}v_{87}v_{55}v_{49},$
		$\displaystyle v_{15}v_{69}v_{73}v_{15},v_{39}v_{80}v_{43}v_{39},v_{25}v_{67}v_{64}v_{25},v_{12}v_{65}v_{68}v_{12},v_{42}v_{86}v_{85}v_{42},v_{40}v_{41}v_{92}v_{40},$
		$\displaystyle v_{11}v_{58}v_{60}v_{11}\}$
$\displaystyle{\mathcal{P}}$	$\displaystyle=$	$\displaystyle\{v_{90}v_{88},v_{14}v_{63},v_{31}v_{79},v_{48}v_{61},v_{21}v_{8},v_{30}v_{44},v_{19}v_{5},v_{3}v_{82},v_{29}v_{45},v_{54}v_{72},v_{89}v_{71},$
		$\displaystyle v_{6}v_{27},v_{56}v_{35},v_{0}v_{22},v_{38}v_{16},v_{24}v_{47},v_{75}v_{52},v_{13}v_{81},v_{23}v_{50}\}$

•

$p=23$

$\displaystyle{\mathcal{C}}$	$\displaystyle=$	$\displaystyle\{v_{11}v_{25}v_{44}v_{11},v_{17}v_{113}v_{99}v_{17},v_{49}v_{86}v_{73}v_{49},v_{45}v_{58}v_{82}v_{45},v_{28}v_{102}v_{114}v_{28},v_{71}v_{112}v_{83}v_{71},$
		$\displaystyle v_{15}v_{92}v_{103}v_{15},v_{5}v_{109}v_{32}v_{5},v_{48}v_{57}v_{91}v_{48},v_{29}v_{110}v_{101}v_{29},v_{31}v_{39}v_{75}v_{31},v_{26}v_{70}v_{34}v_{26},$
		$\displaystyle v_{38}v_{84}v_{77}v_{38},v_{60}v_{67}v_{106}v_{60},v_{4}v_{10}v_{52}v_{4},v_{63}v_{111}v_{69}v_{63},v_{47}v_{98}v_{94}v_{47},v_{14}v_{18}v_{65}v_{14},$
		$\displaystyle v_{53}v_{56}v_{105}v_{53},v_{30}v_{96}v_{93}v_{30},v_{54}v_{108}v_{107}v_{54},v_{27}v_{80}v_{81}v_{27},v_{21}v_{23}v_{79}v_{21}\}$
$\displaystyle{\mathcal{P}}$	$\displaystyle=$	$\displaystyle\{v_{78}v_{76},v_{64}v_{8},v_{37}v_{95},v_{55}v_{87},v_{51}v_{19},v_{72}v_{88},v_{16}v_{0},v_{7}v_{24},v_{85}v_{68},v_{59}v_{41},v_{43}v_{61},$
		$\displaystyle v_{3}v_{97},v_{100}v_{6},v_{13}v_{35},v_{42}v_{20},v_{66}v_{89},v_{12}v_{104},v_{36}v_{62},v_{1}v_{90},v_{46}v_{74},v_{50}v_{22},v_{9}v_{40},v_{33}v_{2}\}$

•

$p=29$

$\displaystyle{\mathcal{C}}$	$\displaystyle=$	$\displaystyle\{v_{5}v_{23}v_{46}v_{5},v_{21}v_{62}v_{39}v_{21},v_{54}v_{71}v_{100}v_{54},v_{63}v_{109}v_{80}v_{63},v_{2}v_{33}v_{131}v_{2},v_{12}v_{141}v_{43}v_{12},$
		$\displaystyle v_{1}v_{98}v_{112}v_{1},v_{60}v_{108}v_{74}v_{60},v_{9}v_{102}v_{115}v_{9},v_{31}v_{83}v_{44}v_{31},v_{20}v_{32}v_{76}v_{20},v_{36}v_{92}v_{48}v_{36},$
		$\displaystyle v_{4}v_{15}v_{57}v_{4},v_{41}v_{94}v_{52}v_{41},v_{7}v_{56}v_{143}v_{7},v_{55}v_{113}v_{64}v_{55},v_{77}v_{85}v_{136}v_{77},v_{0}v_{137}v_{51}v_{0},$
		$\displaystyle v_{49}v_{133}v_{140}v_{49},v_{69}v_{130}v_{123}v_{69},v_{16}v_{79}v_{73}v_{16},v_{29}v_{35}v_{117}v_{29},v_{59}v_{138}v_{142}v_{59},v_{37}v_{120}v_{116}v_{37},$
		$\displaystyle v_{14}v_{17}v_{81}v_{14},v_{47}v_{128}v_{125}v_{47},v_{65}v_{66}v_{134}v_{65},v_{11}v_{88}v_{87}v_{11},v_{19}v_{91}v_{93}v_{19}\}$
$\displaystyle{\mathcal{P}}$	$\displaystyle=$	$\displaystyle\{v_{30}v_{28},v_{22}v_{96},v_{78}v_{6},v_{110}v_{129},v_{126}v_{107},v_{3}v_{24},v_{135}v_{114},v_{84}v_{106},v_{97}v_{75},v_{95}v_{119},v_{50}v_{26},$
		$\displaystyle v_{8}v_{34},v_{53}v_{27},v_{18}v_{45},v_{67}v_{40},v_{10}v_{38},v_{139}v_{111},v_{90}v_{122},v_{104}v_{72},v_{99}v_{132},v_{103}v_{70},$
		$\displaystyle v_{82}v_{118},v_{61}v_{25},v_{68}v_{105},v_{13}v_{121},v_{86}v_{124},v_{127}v_{89},v_{42}v_{144},v_{58}v_{101}\}$

•

$p=31$

$\displaystyle{\mathcal{C}}$	$\displaystyle=$	$\displaystyle\{v_{3}v_{22}v_{51}v_{3},v_{28}v_{154}v_{135}v_{28},v_{45}v_{63}v_{91}v_{45},v_{26}v_{72}v_{44}v_{26},v_{39}v_{56}v_{90}v_{39},v_{7}v_{58}v_{24}v_{7},$
		$\displaystyle v_{25}v_{41}v_{77}v_{25},v_{29}v_{148}v_{132}v_{29},v_{33}v_{47}v_{86}v_{33},v_{66}v_{119}v_{80}v_{66},v_{55}v_{68}v_{112}v_{55},v_{4}v_{146}v_{48}v_{4},$
		$\displaystyle v_{18}v_{79}v_{67}v_{18},v_{89}v_{138}v_{150}v_{89},v_{38}v_{49}v_{96}v_{38},v_{6}v_{114}v_{17}v_{6},v_{14}v_{106}v_{115}v_{14},v_{40}v_{103}v_{94}v_{40},$
		$\displaystyle v_{57}v_{65}v_{121}v_{57},v_{73}v_{137}v_{81}v_{73},v_{75}v_{82}v_{141}v_{75},v_{37}v_{133}v_{126}v_{37},v_{54}v_{60}v_{122}v_{54},v_{0}v_{149}v_{87}v_{0},$
		$\displaystyle v_{42}v_{46}v_{113}v_{42},v_{21}v_{92}v_{88}v_{21},v_{2}v_{5}v_{74}v_{2},v_{34}v_{120}v_{117}v_{34},v_{19}v_{100}v_{101}v_{19},v_{71}v_{153}v_{152}v_{71},$
		$\displaystyle v_{62}v_{64}v_{140}v_{62}\}$
$\displaystyle{\mathcal{P}}$	$\displaystyle=$	$\displaystyle\{v_{104}v_{102},v_{85}v_{9},v_{129}v_{52},v_{107}v_{128},v_{13}v_{147},v_{83}v_{105},v_{23}v_{1},v_{95}v_{118},v_{43}v_{20},$
		$\displaystyle v_{127}v_{151},v_{134}v_{110},v_{116}v_{142},v_{123}v_{97},v_{84}v_{111},v_{59}v_{32},v_{12}v_{136},v_{99}v_{130},v_{8}v_{131},v_{139}v_{16},$
		$\displaystyle v_{76}v_{109},v_{69}v_{36},v_{27}v_{145},v_{61}v_{98},v_{15}v_{53},v_{108}v_{70},v_{10}v_{124},v_{125}v_{11},v_{31}v_{144},v_{143}v_{30},$
		$\displaystyle v_{50}v_{93},v_{78}v_{35}\}$

•

$p=37$

$\displaystyle{\mathcal{C}}$	$\displaystyle=$	$\displaystyle\{v_{130}v_{153}v_{182}v_{130},v_{125}v_{177}v_{148}v_{125},v_{78}v_{100}v_{134}v_{78},v_{29}v_{85}v_{51}v_{29},$
		$\displaystyle v_{33}v_{160}v_{181}v_{33},v_{63}v_{121}v_{84}v_{63},v_{88}v_{107}v_{151}v_{88},v_{20}v_{161}v_{142}v_{20},v_{28}v_{71}v_{89}v_{28},v_{0}v_{167}v_{43}v_{0},$
		$\displaystyle v_{65}v_{82}v_{131}v_{65},v_{13}v_{149}v_{132}v_{13},v_{50}v_{168}v_{184}v_{50},v_{23}v_{90}v_{39}v_{23},v_{60}v_{114}v_{128}v_{60},v_{54}v_{122}v_{68}v_{54},$
		$\displaystyle v_{91}v_{104}v_{163}v_{91},v_{111}v_{183}v_{124}v_{111},v_{37}v_{146}v_{158}v_{37},v_{36}v_{157}v_{48}v_{36},$
		$\displaystyle v_{52}v_{164}v_{175}v_{52},v_{86}v_{159}v_{97}v_{86},v_{49}v_{58}v_{127}v_{49},v_{66}v_{144}v_{135}v_{66},v_{14}v_{22}v_{93}v_{14},v_{44}v_{123}v_{115}v_{44},$
		$\displaystyle v_{35}v_{42}v_{116}v_{35},v_{95}v_{176}v_{169}v_{95},v_{15}v_{92}v_{98}v_{15},v_{96}v_{179}v_{173}v_{96},v_{6}v_{10}v_{109}v_{6},v_{57}v_{143}v_{61}v_{57},$
		$\displaystyle v_{19}v_{103}v_{106}v_{19},v_{18}v_{105}v_{21}v_{18},v_{83}v_{171}v_{172}v_{83},v_{59}v_{156}v_{155}v_{59},v_{53}v_{55}v_{147}v_{53}\}$
$\displaystyle{\mathcal{P}}$	$\displaystyle=$	$\displaystyle\{v_{140}v_{138},v_{26}v_{120},v_{154}v_{62},v_{1}v_{162},v_{77}v_{101},v_{152}v_{178},v_{99}v_{73},v_{3}v_{30},v_{31}v_{4},v_{117}v_{145},v_{108}v_{80},$
		$\displaystyle v_{41}v_{72},v_{133}v_{102},v_{17}v_{170},v_{24}v_{56},v_{12}v_{45},v_{38}v_{5},v_{16}v_{165},v_{74}v_{110},v_{32}v_{70},v_{113}v_{75},$
		$\displaystyle v_{79}v_{118},v_{34}v_{180},v_{46}v_{87},v_{81}v_{40},v_{25}v_{67},v_{69}v_{27},v_{2}v_{141},v_{150}v_{11},v_{47}v_{94},v_{166}v_{119},$
		$\displaystyle v_{64}v_{112},v_{174}v_{126},v_{7}v_{139},v_{76}v_{129},v_{9}v_{137},v_{136}v_{8}\}$

On the directed Oberwolfach problem for complete symmetric equipartite digraphs and uniform-length cycles

Abstract

1 Introduction

Theorem 1.1

Theorem 1.2

Problem 1.3

Theorem 1.4

Theorem 1.5

2 Prerequisites

3 C→t\vec{C}_{t}-factorization of Kn​[m]∗K_{n[m]}^{*}: easy observations

Lemma 3.1

Corollary 3.2

4 Some useful decompositions

Lemma 4.1

Corollary 4.2

5 C→t\vec{C}_{t}-factorizaton of Kn​[m]∗K_{n[m]}^{*} for mm odd, nn even: the easy cases

Proposition 5.1

6 C→t\vec{C}_{t}-factorizaton of Kn​[m]∗K_{n[m]}^{*} for mm odd, nn even: the case gcd⁡(n,t)=1\gcd(n,t)=1

Lemma 6.1

Corollary 6.2

6.1 Subcase n≡0(mod4)n\equiv 0\pmod{4}

Lemma 6.3

Lemma 6.4

Corollary 6.5

6.2 Subcase n≡0(mod6)n\equiv 0\pmod{6}

Lemma 6.6

Corollary 6.7

7 C→t\vec{C}_{t}-factorizaton of K4​[m]∗K_{4[m]}^{*} with mm odd and gcd⁡(4,t)=4\gcd(4,t)=4

Lemma 7.1

Corollary 7.2

8 C→t\vec{C}_{t}-factorizaton of K6​[m]∗K_{6[m]}^{*} with mm odd and gcd⁡(6,t)=6\gcd(6,t)=6

Lemma 8.1

Corollary 8.2

9 C→t\vec{C}_{t}-factorizaton of K6​[m]∗K_{6[m]}^{*} with mm odd and gcd⁡(6,t)=3\gcd(6,t)=3

Lemma 9.1

Corollary 9.2

10 Proof of Theorem 1.5 and conclusion

Theorem 1.5

Conjecture 10.1

Acknowledgements

References

Appendix A Starter digraphs for a C→3\vec{C}_{3}-factorization of K6​[p]∗K_{6[p]}^{\ast}

On the directed Oberwolfach problem
for complete symmetric equipartite digraphs
and uniform-length cycles

3 $\vec{C}_{t}$ -factorization of $K_{n[m]}^{*}$ : easy observations

5 $\vec{C}_{t}$ -factorizaton of $K_{n[m]}^{*}$ for $m$ odd, $n$ even: the easy cases

6 $\vec{C}_{t}$ -factorizaton of $K_{n[m]}^{*}$ for $m$ odd, $n$ even: the case $\gcd(n,t)=1$

6.1 Subcase $n\equiv 0\pmod{4}$

6.2 Subcase $n\equiv 0\pmod{6}$

7 $\vec{C}_{t}$ -factorizaton of $K_{4[m]}^{*}$ with $m$ odd and $\gcd(4,t)=4$

8 $\vec{C}_{t}$ -factorizaton of $K_{6[m]}^{*}$ with $m$ odd and $\gcd(6,t)=6$

9 $\vec{C}_{t}$ -factorizaton of $K_{6[m]}^{*}$ with $m$ odd and $\gcd(6,t)=3$

Appendix A Starter digraphs for a $\vec{C}_{3}$ -factorization of $K_{6[p]}^{\ast}$