# Almost resolvable even cycle systems of $(K_{u}\times K_{g})(\lambda)$

S. Duraimurugan, A. Shanmuga Vadivu and A. Muthusamy
Department of Mathematics, Periyar University, Salem,
Tamil Nadu, India.
_E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>and
<EMAIL_ADDRESS>
Abstract

In this paper, we prove that almost resolvable $k$-cycle systems (briefly
$k$-ARCS) of $(K_{u}\times K_{g})(\lambda)$ exists for all $k\equiv 0(mod\ 4)$
with few possible exceptions, where $\times$ represents tensor product of
graphs.
Keywords: Tensor product; Resolvable cycle systems; Almost resolvable cycle
systems.

##  1 Introduction

Throughout this paper all the graphs considered here are finite. For a graph
$G$, we use $G(\lambda)$ and $\lambda G$, where $\lambda$ is an integer, to
represent the multi-graphs obtained from $G$ by replacing each edge of $G$
with uniform edge-multiplicity $\lambda$ and $\lambda$ edge-disjoint copies of
$G$ respectively. Let $C_{t}$, $K_{t}$ and $\bar{K}_{t}$ respectively, denote
the cycle, complete graph and complement of complete graph on $t$ vertices.
Let $K_{t,t}$ be a complete bipartite graph with bipartition $(A,B)$, where
$A=\\{a_{0},a_{1},...,a_{t-1}\\}\ \mbox{and}\
B=\\{b_{0},b_{1},...,b_{t-1}\\}$. The edge set of $F_{i}(A,B)\subset K_{t,t}$
is defined as $\\{a_{j}b_{j+i}:\ 0\leq j\leq t-1\\}$, $0\leq i\leq t-1$, where
addition in the subscripts are taken modulo $t$. Clearly $F_{i}(A,B)$ is a
$1$-factor of $K_{t,t}$ with distance $i$ from $A$ to $B$. Also,
$\oplus_{i=0}^{t-1}F_{i}(A,B)=K_{t,t}.$

For two graphs $G$ and $H$, their lexicographic product $G\otimes H$ has the
vertex set $V(G\otimes H)=V(G)\times V(H)$ in which two vertices
$(g_{1},h_{1})$ and $(g_{2},h_{2})$ are adjacent whenever $g_{1}g_{2}\in E(G)$
or $g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$. Similarly, the tensor product
$G\times H$ of two graphs $G$ and $H$ has the vertex set $V(G)\times V(H)$ in
which two vertices $(g_{1},h_{1})$ and $(g_{2},h_{2})$ are adjacent whenever
$g_{1}g_{2}\in E(G)$ and $h_{1}h_{2}\in E(H)$. Clearly, the tensor product is
commutative and distributive over edge disjoint union of graphs, i.e, if
$G=G_{1}\oplus G_{2}\oplus...\oplus G_{u},$ then $G\times H=(G_{1}\times
H)\oplus...\oplus(G_{u}\times H)$. One can easily observe that
$K_{u}\otimes\bar{K}_{g}\cong K_{g,g,....g}$, the complete $u$-partite graph
in which each partite set has $g$ vertices. Hereafter, we denote a complete
$u$-partite graph with $g$ vertices in each partite set as
$K_{u}\otimes\bar{K}_{g}$. It is clear that
$(K_{u}\otimes\bar{K}_{g})-gK_{u}\cong K_{u}\times K_{g}$, where $gK_{u}$
denotes $g$ disjoint copies of $K_{u}$. For more details about product graphs,
the readers are referred to [15].

A $k$-factor (respectively, near $k$-factor) of $G$ is a $k$-regular spanning
subgraph of $G$ (respectively, $G\setminus\\{v\\}$, for some $v\in V(G)$).
Note that the $C_{k}$-factor (respectively, near $C_{k}$-factor) of $G$ can
also be called a $2$-factor of $G$ (respectively, $G\setminus\\{v\\}$, for
some $v\in V(G)$), where the components are $C_{k}$. We say that the graph $G$
has a decomposition into $G_{1},G_{2},...,G_{r}$, for some integer $r\geq 1$,
if $G=\oplus_{i=1}^{r}G_{i}$ and $G_{1},G_{2},...,G_{r}$ are pairwise edge-
disjoint subgraphs of $G$. We say that $G$ has a $C_{k}$-decomposition if $G$
can be partitioned into edge-disjoint cycles of length $k$, and the existence
of such decomposition is denoted as $C_{k}\rvert G$. A $1$-factorization
(respectively, near $1$-factorization) of $G$ is the partition of $G$ into
edge-disjoint $1$-factors (respectively, near $1$-factors). A
$C_{k}$-factorization of $G$ is the partition of $G$ into edge-disjoint
$C_{k}$-factors, denoted by $C_{k}\rVert G$. A near $C_{k}$-factorization of
$G$ is the partition of $G$ into edge-disjoint near $C_{k}$-factors. A partial
$k$-factor of $(K_{u}\otimes\bar{K}_{g})(\lambda)$ is the $k$-factor of
$(K_{u}\otimes\bar{K}_{g})(\lambda)\setminus V_{i}$, for some
$i\in\\{1,2,3,..,u\\}$, where $V_{1},V_{2},V_{3},...,V_{u}$ are the partite
sets of $(K_{u}\otimes\bar{K}_{g})(\lambda)$. A partial $k$-factorization
(respectively, partial $C_{k}$-factorization )
$(K_{u}\otimes\bar{K}_{g})(\lambda)$ is a decomposition of
$(K_{u}\otimes\bar{K}_{g})(\lambda)$ into partial $k$-factors (respectively,
partial $C_{k}$-factors). Let $K$ be a set of integers. A resolvable $K$-cycle
systems (respectively, almost resolvable $K$-cycle systems), briefly $K$-RCS
(respectively, $K$-ARCS) of $(K_{u}\otimes\bar{K}_{g})(\lambda)$ is a
decomposition of $(K_{u}\otimes\bar{K}_{g})(\lambda)$ into $2$-factors
(respectively, partial $2$-factors) consists cycles of lengths from $K$. When
$K=\\{k\\},$ we write $K$\- RCS as a $k$-RCS and $K$-ARCS as a $k$-ARCS. A
$(k,\lambda)$-modified cycle frame, briefly $(k,\lambda)$-MCF of
$(K_{u}\otimes\bar{K}_{g})(\lambda)$ is a decomposition of
$(K_{u}\otimes\bar{K}_{g})(\lambda)-gK_{u}(\lambda)$ into partial
$C_{k}$-factors. It is appropriate to mention that $k$-ARCS of $(K_{u}\times
K_{g})(\lambda)$ is nothing but a modified cycle frame. One can easily observe
that $(K_{u}\times K_{g})(\lambda)$ is an $u$-partite graph with edge
multiplicity $\lambda$ and $g$ vertices in each part ; it can also be
considered as an $g$-partite graph with edge multiplicity $\lambda$ and $u$
vertices in each part by the commutative property of tensor product.
Hereafter, we consider $(K_{u}\times K_{g})(\lambda)$ as a $u$-partite graph
with edge multiplicity $\lambda$ and $g$ vertices in each part.

RCS/ARCS research has a direct link to various types of cycle frames. Many
mathematicians (Stinson [25], Cao et al. [8, 7], Niu et al. [23], Chitra et
al. [9], Muthusamy et al. [22] Buratti et al. [5]) have studied cycle frames,
which have connections to many well-known combinatorial problems such as the
Oberwolfach problem and the Hamilton waterloo problem. The above facts
motivate us to work on RCS/ARCS in this paper.

D.R. Stinson [25] proved that there exists a $3$-ARCS of
$(K_{u}\otimes\bar{K}_{g})(\lambda)$ if and only if $u\geq 4,\ \lambda g\equiv
0\ (mod\ 2)$ and $g(u-1)\equiv 0\ (mod\ 3)$. M. Niu and H. Cao [23] proved
that there exits a $\\{3,5\\}$-ARCS of $(K_{u}\otimes\bar{K}_{g})(\lambda)$.
Lot of results have been published on ARCS of
$(K_{u}\otimes\bar{K}_{g})(\lambda),$ see [5, 7, 9, 22]. RCS of $(K_{u}\times
K_{g})(\lambda)$ has been studied by many authors [1, 3, 4, 11]. H. Cao et al.
[8] proved that there exists a $3$-ARCS of $(K_{u}\times{K}_{g})(\lambda)$ if
and only if $\lambda(g-1)\equiv\ 0(mod\ 2)$, $g(u-1)\equiv 0(mod\ 3)$, $g\geq
3$, and $u\geq 4$, except for $(\lambda,g,u)=\\{(1,3,6),(2m+1,6n+3,6)$, $m\geq
0$ and $n\geq 1\\}.$
In this paper, we shall prove that the necessary conditions for a $k$-ARCS of
$(K_{u}\times{K}_{g})(\lambda)$ are also sufficient with few possible
exceptions.

The necessary conditions for a $k$-ARCS of $(K_{u}\times{K}_{g})(\lambda)$ are
shown in the following Theorem.

######  Theorem 1.1.

For all even integers $k\geq 4$, if $(K_{u}\times K_{g})(\lambda)$ has a
$k$-ARCS, then

  * (i)

$u\geq 3$ and $g\geq 2$

  * (ii)

$g(u-1)\equiv 0(mod\ k)$

  * (iii)

$\lambda(g-1)\equiv 0(mod\ 2)$.

###### Proof.

Since $k\geq 4$ is an even integer, it is clear from the definition of
$k$-ARCS that $u\geq 3$ and $g\geq 2$. As the existence of $k$-ARCS gives the
edge disjoint union of partial $C_{k}$-factors of $(K_{u}\times
K_{g})(\lambda),$ the number of vertices in $(K_{u}\times
K_{g})(\lambda)\setminus V_{i},$ for some $i\in\\{1,2,...,u\\}$, where
$V_{1},V_{2},...,V_{u}$ are the partite sets of $(K_{u}\times K_{g})(\lambda)$
must be divisible by $k,$ so $g(u-1)\equiv 0(mod\ k).$ Since each partial
$C_{k}$-factor of $(K_{u}\times K_{g})(\lambda)$ consists of $g(u-1)$ edges,
the number of partial $C_{k}$-factors in $(K_{u}\times K_{g})(\lambda)$ is

$\lambda\frac{\frac{u(u-1)}{2}g^{2}-\frac{u(u-1)}{2}g}{(u-1)g}=\lambda\frac{u(g-1)}{2}.$

Hence, there are precisely $\frac{\lambda(g-1)}{2}$ partial $C_{k}$-factors
correspond to each partite set $V_{i},\ i\in\\{1,2,...,u\\}$. ∎

######  Theorem 1.2.

For even $k\equiv 0(mod\ 4),$ there exists a $k$-ARCS of
$(K_{u}\times{K}_{g})(\lambda)$ if and only if $u\geq 3$, $g\geq 2$,
$\lambda(g-1)\equiv 0(mod\ 2)$, $g(u-1)\equiv 0(mod\ k),$ except possibly
$(\lambda,k,u)\in\\{(2s,4,4x),(2s,4t,8),(2s,4t,4x+2),\ s,t,x\geq 1\\}$ and
$(\lambda,k,u,g)\in\\{(2x+1,4t,8t+1,y),(2x+1,rs,2r+1,sy),\ x\geq 0,\ t\geq 1,\
r\ \mbox{is even},\ s\geq 3\ \mbox{and}\ y\geq 1\ \mbox{are odd}\\}.$

##  2 Preliminaries

To prove our results we need the following:

######  Theorem 2.1.

[2] For any odd integer $t\geq 3$, if $u\equiv t(mod\ 2t)$, then
$C_{t}||K_{u}$.

######  Theorem 2.2.

[10] For $u\geq 3$, $K_{u}$ has a near $1$-factorization if and only if
$u\equiv 1(mod\ 2)$.

######  Theorem 2.3.

[6] For $u\geq 3$, $K_{u}(2)$ has a near $C_{2k}$-factorization if and only if
$u\equiv 1(mod\ 2k)$.

######  Theorem 2.4.

[20] There exists a $C_{2m}$-factorization of $K_{u}(\lambda)$ if and only if
$\lambda$ is even and $u\equiv 0(mod\ 2m)$.

######  Theorem 2.5.

[12] For any odd $m\geq 3$ and a non-negative integer $s$, there exists a near
$C_{m}$-factorization of $K_{ms+1}(2)$.

######  Theorem 2.6.

[13] $K_{m,n}$ has a $C_{k}$-factorization if and only if

  * (i)

$m=n\equiv 0(mod\ 2)$

  * (ii)

$k\equiv 0(mod\ 2)\geq 4$

  * (iii)

$2n\equiv 0(mod\ k)$

with precisely one exception, namely $m=n=k=6$.

######  Theorem 2.7.

[21] For $m,n\geq 1$, the graph $C_{2n+1}\times K_{2m}$ has a Hamilton cycle
decomposition.

######  Theorem 2.8.

[18] The graph $C_{2n}\times K_{2m}$ has a Hamilton cycle decomposition.

######  Theorem 2.9.

[16] The graph $C_{m}\otimes\bar{K}_{n}$ has a Hamilton cycle decomposition.

######  Theorem 2.10.

[21] If $C_{k}\rVert G$ and $n|m$, then $C_{kn}\rVert G\times K_{m}$, where
$m\not\equiv 2(mod\ 4),$ when $k$ is odd.

######  Theorem 2.11.

[24] For an odd integer $m\geq 3$ and even integer $k\geq 4,$ we have
$C_{k}\rVert G^{k}\times K_{m}$ except possibly for $(k,m)=(4,3),$ where
$G^{k}$ is a cubic graph of order $k.$

######  Theorem 2.12.

[7] There exists a $6$-ARCS of $K_{4}\otimes\bar{K}_{2}$.

######  Theorem 2.13.

[14] $K_{t,t,t}$ has a $C_{t}$-factorization.

######  Theorem 2.14.

[10] There exists a partial $1$-factorization of $K_{u}\otimes\bar{K}_{g},$ if
and only if $u\geq 3$ and $g(u-1)\equiv 0\ (mod\ 2)$.

##  3 Basic Constructions

######  Theorem 3.1.

There exists a partial $C_{k}$-factorization of $K_{k+1}\times K_{t}$, for all
odd $t\geq 3$ and $k\equiv 0(mod\ 4)$.

###### Proof.

To prove this Theorem, without loss of generality we consider a graph
$K_{k+1}(2)$ as follows. Let
$V(K_{k+1}(2))=\\{a_{0},a_{1},a_{2},...,a_{k-1},a_{\infty}\\}.$ By Theorem
2.3, $K_{k+1}(2)$ has a near $C_{k}$-factorization. The required near
$C_{k}$-factors are given by
$G_{i}=(a_{i},a_{i+1},a_{i-1},a_{i+2},a_{i-2},...,a_{i+\frac{k}{2}-1},a_{i-\frac{k}{2}+1},a_{\infty}),$
$0\leq i\leq k-1$ and calculations are taken modulo $k$, and
$G_{\infty}=(a_{0},a_{1},a_{2},...,a_{k-1})$.
We now construct the partial $C_{k}$-factors of $K_{k+1}\times K_{t}$ as
follows:
Set $A_{i}=\\{i\\}\times\mathbb{Z}_{t},$ for every
$i\in\mathbb{Z}_{k}\cup\\{\infty\\}.$ Also, let
$A_{0},A_{1},...,A_{k-1},A_{\infty}$ be the partite sets of $K_{k+1}\times
K_{t}.$
(i) For odd $i<k$, let $G_{i}^{r}=F_{r}(A_{i},A_{i+1})\oplus
F_{t-r}(A_{i+1},A_{i-1})\oplus...\oplus F_{t-r}(A_{\infty},A_{i})$,
(ii) For even $i<k$, let $G^{r}_{i}=F_{t-r}(A_{i},A_{i+1})\oplus
F_{r}(A_{i+1},A_{i-1})\oplus...\oplus F_{r}(A_{\infty},A_{i})$ and
(iii) let $G^{r}_{\infty}=F_{r}(A_{0},A_{1})\oplus
F_{t-r}(A_{1},A_{2})\oplus...\oplus F_{t-r}(A_{k-1},A_{0})$,
where each $G_{i}^{r}$ and $G_{\infty}^{r}$ misses $A_{i+\frac{k}{2}}$ and
$A_{\infty}$ respectively, $0\leq i\leq k-1,\ 1\leq r\leq\frac{t-1}{2}$ and
the additions are taken modulo $k$.
One can check that each $G^{r}_{i},\ i\in\mathbb{Z}_{k}\cup\\{\infty\\},$
$1\leq r\leq\frac{t-1}{2}$ is a partial $C_{k}$-factor of $K_{k+1}\times
K_{t}$ and hence $K_{k+1}\times K_{t}$ has a partial $C_{k}$-factorization. ∎

######  Lemma 3.1.

There exists a $C_{kt}$-factorization of $C_{k}\times K_{t},$ for all even
$k\geq 4,$ and odd $t\geq 3$.

###### Proof.

We can write

$\displaystyle C_{k}\times K_{t}$ $\displaystyle\cong$ $\displaystyle
C_{k}\times\\{C_{t}^{1}\oplus...\oplus C_{t}^{\frac{t-1}{2}}\\}$
$\displaystyle\cong$ $\displaystyle\oplus_{i=1}^{\frac{t-1}{2}}(C_{k}\times
C_{t}^{i})$ $\displaystyle\cong$
$\displaystyle\oplus_{i=1}^{\frac{t-1}{2}}(C_{t}^{i}\times C_{k})$

We know that $C_{t}^{i}\times C_{k}\cong C_{t}\times C_{k}$ and find its
$C_{kt}$-factors as follows:
Let $V(C_{t})=\\{a_{0},a_{1},...,a_{t-1}\\}$ then $V(C_{t}\times
C_{k})=\\{A_{i}|0\leq i\leq t-1\\},$ where
$A_{i}=a_{i}\times\mathbb{Z}_{k}=\\{a_{i}^{0},a_{i}^{1},...,a_{i}^{k-1}\\}.$
Let

$\displaystyle\mbox{(i)}\ \hskip 28.45274pt{G}$ $\displaystyle=$
$\displaystyle\\{\oplus_{i=0}^{\frac{t-1}{2}}F_{1}(A_{2i},A_{2i+1})\\}\oplus\\{\oplus_{i=0}^{\frac{t-3}{2}}F_{k-1}(A_{2i+1},A_{2i+2})\\}\
\ \mbox{and}$ (1) $\displaystyle\mbox{(ii)}\hskip 28.45274pt{H}$
$\displaystyle=$
$\displaystyle\\{\oplus_{i=0}^{\frac{t-1}{2}}F_{k-1}(A_{2i},A_{2i+1})\\}\oplus\\{\oplus_{i=0}^{\frac{t-3}{2}}F_{1}(A_{2i+1},A_{2i+2})\\},$
(2)

where the subscripts of $A$ are taken modulo $t$. One can check that both
$\mathcal{G}$ and $\mathcal{H}$ are the $C_{kt}$-factors of $C_{t}\times
C_{k}$. Thus each $C_{t}^{i}\times C_{k}$ has $2$ $C_{kt}$-factors and hence
together gives a $C_{kt}$-factorization of $C_{k}\times K_{t}.$ ∎

######  Theorem 3.2.

There exists a partial $C_{kt}$-factorization of $K_{k+1}\times K_{t},$ for
all even $k\geq 4,$ and odd $t\geq 3$.

###### Proof.

By Theorem 2.3, $K_{k+1}(2)$ has a near $C_{k}$-factorization. The required
near $C_{k}$-factors are given by
$G_{i}=(a_{i},a_{i+1},a_{i-1},a_{i+2},a_{i-2},...,a_{i+\frac{k}{2}-1},a_{i-\frac{k}{2}+1},a_{\infty}),$
$0\leq i\leq k-1$ and calculations are taken modulo $k$, and
$G_{\infty}=(a_{0},a_{1},a_{2},...,a_{k-1})$. We can write

$\displaystyle K_{k+1}(2)\times K_{t}$ $\displaystyle\cong$
$\displaystyle\oplus_{i=0}^{k-1}(G_{i}\oplus G_{\infty})\times K_{t}\ \mbox{by
Theorem \ref{t4} }$ (3) $\displaystyle\cong$
$\displaystyle\oplus_{i=0}^{k-1}(G_{i}\times K_{t})\oplus(G_{\infty}\times
K_{t})$

By (1) of Lemma 3.1, $G_{i}\times K_{t}\cong C_{k}\times K_{t}$ has a
$C_{kt}$-factorization
$\mathcal{G}_{i}=\\{G_{i,1},G_{i,2},...,G_{i,\frac{t-1}{2}}\\}$, for every
$i\in\mathbb{Z}_{k}$.
Considering that $G_{\infty}\times K_{t}\cong C_{k}\times K_{t}$ and by (2) of
Lemma 3.1, $G_{\infty}\times K_{t}$ has a $C_{kt}$-factorization
$\mathcal{G}_{\infty}=\\{H^{\infty}_{1},H^{\infty}_{2},...,H^{\infty}_{\frac{t-1}{2}}\\}$.
One can check that $\mathcal{G}=\\{G_{i,j}\oplus H^{\infty}_{j}|\
i\in\mathbb{Z}_{k},\ 1\leq j\leq\frac{t-1}{2}\\}$ gives a partial
$C_{kt}$-factorization of $K_{k+1}\times K_{t}$. ∎

######  Theorem 3.3.

There exists a $C_{k}$-factorization of $K_{3}\times K_{ky}$ for all even
$k\geq 6$ and all odd $y\geq 1$.

###### Proof.

We establish the proof in two cases
Case (i): $y=1$

$\displaystyle K_{3}\times K_{k}$ $\displaystyle\cong$ $\displaystyle
K_{k}\times K_{3}$ $\displaystyle\cong$
$\displaystyle(\underbrace{C_{k}\oplus...\oplus C_{k}}_{\frac{k}{2}-2\ \
\mbox{times}}\oplus G)\times K_{3},\ \mbox{by walecki's contruction}$
$\displaystyle\cong$ $\displaystyle(C_{k}\times
K_{3})\oplus...\oplus(C_{k}\times K_{3})\oplus(G\times K_{3}),$

where $G$ is a cubic graph having perfect $1$-factorization as defined in
[24].
One can check that each $C_{k}\times K_{3}$ has $2$ $C_{k}$-factors by Theorem
2.10 and $G\times K_{3}$ has $3$ $C_{k}$-factors by Theorem 2.11. Hence
$K_{3}\times K_{k}$ is factorable into $(k-1)\ C_{k}$-factors.
Case (ii): $y\geq 3$ is odd
We can write

$\displaystyle K_{3}\times K_{ky}\cong\\{(K_{3}\times
K_{y})\otimes\bar{K}_{k}\\}\oplus y(K_{3}\times K_{k})$ (5)

Graphs in the R.H.S of (7) can be obtained by making $y$ holes of type
$K_{3}\times K_{k}$ in $K_{3}\times K_{ky}$ and identifying each $k$-subsets
of $K_{ky}$ (in the resulting graph) into a single vertex and two of them are
adjacent if the corresponding $k$-subsets form a $K_{k,k}$ in $K_{3}\times
K_{ky}.$ By expanding the vertices into $k$-subsets we get the first graph of
(7)
Now, we construct the $C_{k}$-factors of $(K_{3}\times
K_{y})\otimes\bar{K}_{k}$ as follows:

$\displaystyle(K_{3}\times K_{y})\otimes\bar{K}_{k}$ $\displaystyle\cong$
$\displaystyle(C_{3}^{1}\oplus C_{3}^{2}\oplus...\oplus
C_{3}^{y-1})\otimes\bar{K}_{k},\ \mbox{by Theorem \ref{l1}}$
$\displaystyle\cong$
$\displaystyle(C_{3}^{1}\otimes\bar{K}_{k})\oplus...\oplus(C_{3}^{y-1}\otimes\bar{K}_{k}),$

each $C_{3}^{i},\ 1\leq i\leq y-1,$ is a $C_{3}$-factor of $K_{3}\times
K_{y}$. One can observe that $C_{3}^{i}\otimes\bar{K}_{k}\cong
y(C_{3}\otimes\bar{K}_{k})\cong y(K_{k,k,k})$. By Theorem 2.13, each
$K_{k,k,k}$ is factorable into $k\ C_{k}$-factors. Thus we get $k(y-1)$
$C_{k}$-factors of $(K_{3}\times K_{y})\otimes\bar{K}_{k}$. By (3), each
$K_{3}\times K_{k}$ is factorable into $(k-1)\ C_{k}$-factors. Finally, the
two graph in (7), together gives $(ky-1)\ C_{k}$-factors of $K_{3}\times
K_{ky}$. Hence, $C_{k}$-factorization of $K_{3}\times K_{ky}$ exists. ∎

######  Theorem 3.4.

There exists a $C_{k}$-factorization of $K_{3}\times K_{ky}$ for all even
$k\geq 6$ and all odd $y\geq 1$.

###### Proof.

We establish the proof in two cases
Case (i): $y=1$

$\displaystyle K_{3}\times K_{k}$ $\displaystyle\cong$ $\displaystyle
K_{k}\times K_{3}$ $\displaystyle\cong$
$\displaystyle(\underbrace{C_{k}\oplus...\oplus C_{k}}_{\frac{k}{2}-2\ \
\mbox{times}}\oplus G)\times K_{3},\ \mbox{by walecki's contruction}$
$\displaystyle\cong$ $\displaystyle(C_{k}\times
K_{3})\oplus...\oplus(C_{k}\times K_{3})\oplus(G\times K_{3}),$

where $G$ is a cubic graph having perfect $1$-factorization as defined in
[24].
One can check that each $C_{k}\times K_{3}$ has $2$ $C_{k}$-factors by Theorem
2.10 and $G\times K_{3}$ has $3$ $C_{k}$-factors by Theorem 2.11. Hence
$K_{3}\times K_{k}$ is factorable into $(k-1)\ C_{k}$-factors.
Case (ii): $y\geq 3$ is odd
We can write

$\displaystyle K_{3}\times K_{ky}\cong\\{(K_{3}\times
K_{y})\otimes\bar{K}_{k}\\}\oplus y(K_{3}\times K_{k})$ (7)

Graphs in the R.H.S of (7) can be obtained by making $y$ holes of type
$K_{3}\times K_{k}$ in $K_{3}\times K_{ky}$ and identifying each $k$-subsets
of $K_{ky}$ (in the resulting graph) into a single vertex and two of them are
adjacent if the corresponding $k$-subsets form a $K_{k,k}$ in $K_{3}\times
K_{ky}.$ By expanding the vertices into $k$-subsets we get the first graph of
(7)
Now, we construct the $C_{k}$-factors of $(K_{3}\times
K_{y})\otimes\bar{K}_{k}$ as follows:

$\displaystyle(K_{3}\times K_{y})\otimes\bar{K}_{k}$ $\displaystyle\cong$
$\displaystyle(C_{3}^{1}\oplus C_{3}^{2}\oplus...\oplus
C_{3}^{y-1})\otimes\bar{K}_{k},\ \mbox{by Theorem \ref{l1}}$
$\displaystyle\cong$
$\displaystyle(C_{3}^{1}\otimes\bar{K}_{k})\oplus...\oplus(C_{3}^{y-1}\otimes\bar{K}_{k}),$

each $C_{3}^{i},\ 1\leq i\leq y-1,$ is a $C_{3}$-factor of $K_{3}\times
K_{y}$. One can observe that $C_{3}^{i}\otimes\bar{K}_{k}\cong
y(C_{3}\otimes\bar{K}_{k})\cong y(K_{k,k,k})$. By Theorem 2.13, each
$K_{k,k,k}$ is factorable into $k\ C_{k}$-factors. Thus we get $k(y-1)$
$C_{k}$-factors of $(K_{3}\times K_{y})\otimes\bar{K}_{k}$. By (3), each
$K_{3}\times K_{k}$ is factorable into $(k-1)\ C_{k}$-factors. Finally, the
two graph in (7), together gives $(ky-1)\ C_{k}$-factors of $K_{3}\times
K_{ky}$. Hence, $C_{k}$-factorization of $K_{3}\times K_{ky}$ exists. ∎

######  Theorem 3.5.

There exists a $C_{k}$-factorization of $K_{3}\times K_{ky}$ for all even
integers $k>6$ and $y\geq 2$.

###### Proof.

We can write

$\displaystyle K_{3}\times K_{ky}$ $\displaystyle\cong$
$\displaystyle\\{(K_{3}\times K_{y})\otimes\bar{K}_{k}\\}\oplus y(K_{3}\times
K_{k})\ \mbox{(by case (ii) of Theorem \ref{nr})}$ $\displaystyle\cong$
$\displaystyle\\{(C_{3y}^{1}\oplus...\oplus
C_{3y}^{y-1})\otimes\bar{K}_{k}\\}\oplus y(K_{3}\times K_{k}),\ \mbox{by
Theorem \ref{hc}}$

Since each $C_{3y}^{i}\cong(F_{1}\oplus F_{2}),\ 1\leq i\leq y-1$, where
$F_{j},\ j=1,2$ is a $1$-factor of $C_{3y}$. We know that
$F_{j}\otimes\bar{K}_{k}\cong\frac{3y}{2}(K_{2}\otimes\bar{K}_{k})\cong\frac{3y}{2}(K_{k,k})$
and by Theorem 2.6, each $K_{k,k}$ has $\frac{k}{2}\ C_{k}$-factors . Hence
$(K_{3}\times K_{y})\otimes\bar{K}_{k}$ is factorable into $(y-1)k\
C_{k}$-factors. By (3), $K_{3}\times K_{k}$ is factorable into $(k-1)\
C_{k}$-factors. Finally, the two graphs in (3), together gives $(ky-1)\
C_{k}$-factors of $K_{3}\times K_{ky}$. Hence, $C_{k}$-factorization of
$K_{3}\times K_{ky}$ exists. ∎

######  Theorem 3.6.

There exists a $C_{kt}$-factorization of $C_{k}\times K_{s},$ for all even
$k\geq 4,\ t\geq 3$ and $s\equiv 0(mod\ 2t).$

###### Proof.

We can write

$\displaystyle C_{k}\times K_{s}$ $\displaystyle\cong$ $\displaystyle
C_{k}\times K_{2ty}$ $\displaystyle\cong$ $\displaystyle C_{k}\times
K_{t(2y)}$

Case (i): $t\geq 3$ is odd
By Theorem 2.10, $C_{k}\times K_{t(2y)}$ has $2ty-1$ $C_{kt}$-factors.
Case (ii): $t\geq 4$ is even
We write

$\displaystyle C_{k}\times K_{t(2y)}$ $\displaystyle\cong$
$\displaystyle\\{(C_{k}\times K_{2y})\otimes\bar{K}_{t}\\}\oplus
2y(C_{k}\times K_{t})$ (9)

Graphs in the R.H.S of (9) can be obtained by making $2y$ holes of type
$C_{k}\times K_{t}$ in $C_{k}\times K_{t(2y)}$ and identifying each
$t$-subsets of $K_{t(2y)}$ (in the resulting graph) into a single vertex and
two of them are adjacent if the corresponding $t$\- subsets in $C_{k}\times
K_{t(2y)}$ form a $K_{t,t}.$ By expanding the vertices into $t$-subsets we get
the first graph in (9).
Now, we construct the $C_{k}$-factors of $C_{k}\times K_{2y}$ as follows:
Let $V(C_{k})=\\{a_{0},a_{1},...,a_{k-1}\\}$ then $V(C_{k}\times
K_{2y})=\\{A_{i}|0\leq i\leq k-1\\},$ where
$A_{i}=a_{i}\times\mathbb{Z}_{2y}=\\{a_{i}^{0},a_{i}^{1},...,a_{i}^{2y-1}\\}.$

  * ${G}_{l}=\oplus_{j=0}^{\frac{k}{2}-1}\\{F_{l}(A_{2j},A_{2j+1})\\}\oplus\\{\oplus_{j=0}^{\frac{k}{2}-1}\\{F_{2y-l}(A_{2j+1},A_{2j+2})\\}\\},$

where the subscripts of $A$ are taken modulo $k.$ One can check that each
$G_{l}$, $1\leq l\leq 2y-1,$ is a $C_{k}$-factor of $C_{k}\times K_{2y}.$ We
know that $(C_{k}\times
K_{2y})\otimes\bar{K}_{t}\cong(2y-1)\\{2y(C_{k}\otimes\bar{K}_{t})\\}$ and by
Theorem 2.9, each $C_{k}\otimes\bar{K}_{t}$ has $t$ $C_{kt}$-factors. Thus we
have obtained $(2y-1)t$ $C_{kt}$-factors of $(C_{k}\times
K_{2y})\otimes\bar{K}_{t}.$ Further, by Theorem 2.8, each $C_{k}\times K_{t}$
has $t-1$ $C_{kt}$-factors. The combination of the $2ty-1$ $C_{kt}$-factors of
(9) gives a $C_{kt}$-factors of $C_{k}\times K_{s}$. Hence $C_{kt}$-factors of
$C_{k}\times K_{s}$ exists. ∎

##  4 $k$-ARCS of $(K_{u}\times K_{g})(\lambda)$

In this section, we investigate the existence of $k$-ARCS of tensor product of
complete graphs with edge multiplicity $\lambda.$

######  Theorem 4.1.

For all even $k\geq 4$, $u\equiv 1(mod\ k)$ and $g\geq 2$, there exists a
$k$-ARCS of $(K_{u}\times{K}_{g})(2)$.

###### Proof.

Let $u=kx+1$, where $x\geq 1$.
By Theorem 2.3, let
$\mathcal{C}=\\{\mathcal{C}_{k}^{1},\mathcal{C}_{k}^{2},\mathcal{C}_{k}^{3},...,\mathcal{C}_{k}^{u}\\}$
be the near $C_{k}$-factorization of $K_{u}(2)$, where each
$\mathcal{C}_{k}^{i}$, $1\leq i\leq u$ is a near $C_{k}$-factor of $K_{u}(2)$.
Now we write

$\displaystyle(K_{u}\times K_{g})(2)$ $\displaystyle\cong$ $\displaystyle
K_{u}(2)\times K_{g}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{k}^{1}\oplus\mathcal{C}_{k}^{2}\oplus...\oplus\mathcal{C}_{k}^{u})\times
K_{g},\ \ \mbox{by Theorem \ref{t4}}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{k}^{1}\times
K_{g})\oplus(\mathcal{C}_{k}^{2}\times
K_{g})\oplus...\oplus(\mathcal{C}_{k}^{u}\times K_{g}).$

Since each $\mathcal{C}_{k}^{i}\times K_{g}\cong\frac{u-1}{k}(C_{k}\times
K_{g})$, by Theorem 2.10, each $C_{k}\times K_{g}$ has $g-1$ $C_{k}$-factors.
The $C_{k}$-factors obtained above become the partial $C_{k}$-factors of
$(K_{u}\times K_{g})(2).$ Thus, in total we get $u(g-1)$ partial
$C_{k}$-factors of $(K_{u}\times K_{g})(2).$ Therefore $k$-ARCS of
$(K_{u}\times{K}_{g})(2)$ exists. ∎

######  Theorem 4.2.

For all even $k\equiv 0(mod\ 4),\ x\in\mathbb{N}\setminus\\{2\\}$, $u=kx+1$
and $g\geq 3$ is odd , there exists a $k$-ARCS of $K_{u}\times{K}_{g}.$

###### Proof.

Let $u=kx+1$, $g\geq 3$ is odd and $k=4t$, where
$x\in\mathbb{N}\setminus\\{2\\},$ and $y,t\geq 1$.
We establish the proof in two cases.
Case (i): $x=1$
Let $A_{0},A_{1},...,A_{4t-1},A_{\infty}$ be the parts of $K_{4t+1}\times
K_{g}.$ By Theorem 3.1, $K_{4t+1}\times K_{g}$ has a partial
$C_{k}$-factorization $\mathcal{G}=\\{G_{s,h}\oplus
G_{h}^{\infty}|s\in\mathbb{Z}_{4t},1\leq h\leq\frac{g-1}{2}\\}$ where each
$G_{s,h}$ is a partial $C_{k}$-factor missing the partite set $A_{s+2t},$ and
the subscripts of $A$ are taken modulo $4t$; each $G_{h}^{\infty}$ is a
partial $C_{k}$\- factor missing the partite set $A_{\infty}.$
Hence $k$-ARCS of $K_{4t+1}\times{K}_{g}$ exists.
Case (ii): $x>2$
Set $X_{i}=\\{i\\}\times\mathbb{Z}_{4t}$ and let $\Gamma_{i}$ be the complete
graph of order $4t+1$ with vertex-set $V(\Gamma_{i})=X_{i}\cup\\{\infty\\},$
for every $i\in\mathbb{Z}_{x}.$ Also, let $X_{0},X_{1},...,X_{x-1}$ be the
parts of the complete multipartite graph $K_{x}\otimes\bar{K}_{4t},$ and set

$\displaystyle
K_{4tx+1}\cong(K_{x}\otimes\bar{K}_{4t})\oplus(\oplus_{i=0}^{x-1}\Gamma_{i})$
(10)

Considering that
$K_{x}\otimes\bar{K}_{4t}\cong(K_{x}\otimes\bar{K}_{2})\otimes\bar{K}_{2t},$
and by Theorem 2.14, $K_{x}\otimes\bar{K}_{2}$ has a partial $1$-factorization
$\\{\Delta_{0},\Delta_{1},...,\Delta_{x-1}\\}$ . We have that

$\displaystyle K_{x}\otimes\bar{K}_{4t}$ $\displaystyle\cong$
$\displaystyle(\Delta_{0}\oplus...\oplus\Delta_{x-1})\otimes\bar{K}_{2t}$
$\displaystyle\cong$
$\displaystyle(\Delta_{0}\otimes\bar{K}_{2t})\oplus...\oplus(\Delta_{x-1}\otimes\bar{K}_{2t}),$

where each $\Gamma^{\prime}_{i}=\Delta_{i}\otimes\bar{K}_{2t}$ misses $X_{i}.$
Therefore, by (10) it follows that

$\displaystyle
K_{4tx+1}\cong\oplus_{i=0}^{x-1}(\Gamma^{\prime}_{i}\oplus\Gamma_{i})$

where
$V(\Gamma^{\prime}_{i}\oplus\Gamma_{i})=(\mathbb{Z}_{x}\times\mathbb{Z}_{4t})\cup\\{\infty\\}.$
Also,

$\displaystyle K_{4tx+1}\times K_{g}$ $\displaystyle\cong$
$\displaystyle\oplus_{i=0}^{x-1}(\Gamma^{\prime}_{i}\oplus\Gamma_{i})\times
K_{g}$ (11) $\displaystyle\cong$
$\displaystyle\oplus_{i=0}^{x-1}\\{(\Gamma^{\prime}_{i}\times
K_{g})\oplus(\Gamma_{i}\times K_{g})\\}.$

By Theorem 2.6, $\Gamma^{\prime}_{i}$ has a $C_{4t}$-factorization
$\mathcal{G}^{\prime}_{i}=\\{G^{\prime}_{i,1},G^{\prime}_{i,2},...,G^{\prime}_{i,2t}\\},$
and by Theorem 2.10, $G^{\prime}_{i,j}\times K_{g}$ has a
$C_{k}$-factorization
$\mathcal{G}^{\prime}_{i,j}=\\{G^{\prime}_{i,j,1},G^{\prime}_{i,j,2},...,G^{\prime}_{i,j,g-1}\\},$
for every $i\in\mathbb{Z}_{x},$ and $j\in\\{1,2,...,2t\\}.$ Hence,
$\oplus_{j}\mathcal{G}^{\prime}_{i,j}$ gives a $C_{k}$-factorization of
$\Gamma^{\prime}_{i}\times K_{g}.$

Now consider $\Gamma_{i}\times K_{g}\cong K_{4t+1}\times K_{g}$ and let
$A_{0},A_{1},...,A_{4t-1},A_{\infty}$ be the parts of $K_{4t+1}\times K_{g}.$
By Theorem 3.1, $K_{4t+1}\times K_{g}$ has a partial $C_{k}$-factorization
$\mathcal{G}_{i}=\\{G_{i,s,h}\oplus G_{i,h}^{\infty}|s\in\mathbb{Z}_{4t},1\leq
h\leq\frac{g-1}{2}\\}$ where each $G_{i,s,h}$ is a partial $C_{k}$-factor
missing the partite set $A_{s+2t},$ and the subscripts of $A$ are taken modulo
$4t$; each $G_{i,h}^{\infty}$ is a partial $C_{k}$-factor missing the partite
set $A_{\infty}.$
One can check that $\mathcal{G}=\\{G^{\prime}_{i,j,l}|i\in\mathbb{Z}_{x},1\leq
j\leq 2t,1\leq l\leq g-1\\}\cup\\{G_{i,s,h}\oplus
G_{i,h}^{\infty}|i\in\mathbb{Z}_{x},s\in\mathbb{Z}_{4t},1\leq
h\leq\frac{g-1}{2}\\}$ gives a partial $C_{k}$-factorization of
$K_{4tx+1}\times K_{g}.$ Therefore $k$-ARCS of $K_{u}\times{K}_{g}$ exists. ∎

######  Theorem 4.3.

For all even $k\geq 4$, odd $u\geq 3$ and $g\equiv 0(mod\ k)$, there exists a
$k$-ARCS of $(K_{u}\times{{K}_{g}})(2)$.

###### Proof.

Let $u=2x+1$ and $g=ky$, where $x,y\geq 1$.
By Theorem 2.2, let $\mathcal{F}=\\{F_{1},F_{2},....,F_{u}\\}$ be the near
$1$-factorization of $K_{u}$, where each $F_{i}$, $1\leq i\leq u$ is a near
$1$-factor of $K_{u}$. We can write

$\displaystyle(K_{u}\times K_{g})(2)$ $\displaystyle\cong$
$\displaystyle\\{(F_{1}\oplus F_{2}\oplus....\oplus F_{u})\times K_{g}\\}(2),\
\ \mbox{by Theorem \ref{t1}}$ $\displaystyle\cong$ $\displaystyle(F_{1}\times
K_{g})(2)\oplus....\oplus(F_{u}\times K_{g})(2)$ $\displaystyle\cong$
$\displaystyle(F_{1}\times K_{ky})(2)\oplus....\oplus(F_{u}\times K_{ky})(2)$

Since $(F_{i}\times K_{ky})(2)\cong F_{i}\times K_{ky}(2)\cong\frac{u-1}{2}\
(K_{2}\times K_{ky}(2))$ and by Theorem 2.4, let
$\mathcal{C}=\\{\mathcal{C}_{k}^{1},\mathcal{C}_{k}^{2},...,\mathcal{C}_{k}^{ky-1}\\}$
be the $C_{k}$-factorization of $K_{ky}(2),$ where each $C_{k}^{j},\ 1\leq
j\leq ky-1$ is a $C_{k}$-factor of $K_{ky}(2)$. One can observe that
$\mathcal{C}_{k}^{j}\cong yC_{k}$ and $K_{2}\times C_{k}\cong C_{k}\times
K_{2}.$ By Theorem 2.10, each $C_{k}\times K_{2}$ is a $C_{k}$-factor. Thus,
in total we get $(2x+1)(ky-1)$ partial $C_{k}$-factors of $(K_{u}\times
K_{g})(2)$. Therefore $k$-ARCS of $(K_{u}\times{K}_{g})(2)$ exists. ∎

######  Theorem 4.4.

For all even $k\geq 6$, $y\geq 1$ is odd, $x\in\mathbb{N}\setminus\\{2\\},\
u=4x$ and $g=ky,$ there exists a $k$-ARCS of $(K_{u}\times{K}_{g})(2).$

###### Proof.

Let $u=4x$ and $g=ky$, where $x\in\mathbb{N}\setminus\\{2\\},\ y\geq 1$ is
odd.
We establish the proof in two cases.
Case (i): $x=1.$
We can write

$(K_{4}\times K_{ky})(2)\cong K_{4}(2)\times K_{ky}$

By Theorem 2.5, $K_{4}(2)$ has a near $C_{3}$-factorization
$\mathcal{G}=\\{G_{1},G_{2},G_{3},G_{4}\\}$, and by Theorem 3.4, each
$G_{i}\times K_{ky},\ 1\leq i\leq 4$ has a $C_{k}$-factorization
$\mathcal{G}_{i}=\\{G_{i,1},G_{i,2},...,G_{i,ky-1}\\}.$ Hence $(K_{4}\times
K_{ky})(2)$ has a partial $C_{k}$-factorization.
Case (ii): $x>2.$
Set $X_{i}=\\{i\\}\times\mathbb{Z}_{4}$ and let $\Gamma_{i}$ be the complete
graph of order $4$ with vertex-set $V(\Gamma_{i})=X_{i},$ for every
$i\in\mathbb{Z}_{x}.$ Also, let $X_{0},X_{1},...,X_{x-1}$ be the parts of the
complete multipartite graph $K_{x}\otimes\bar{K}_{4},$ and set

$\displaystyle
K_{4x}\cong(K_{x}\otimes\bar{K}_{4})\oplus(\oplus_{i=0}^{x-1}\Gamma_{i})$ (12)

By Theorem 2.14, $K_{x}\otimes\bar{K}_{4}$ has a partial $1$-factorization
$\\{\Gamma^{\prime}_{0},\Gamma^{\prime}_{1},...,\Gamma^{\prime}_{x-1}\\}$
where each $\Gamma^{\prime}_{i}$ misses $X_{i}.$ Therefore, by (12) it follows
that

$\displaystyle
K_{4x}=\oplus_{i=0}^{x-1}(\Gamma^{\prime}_{i}\oplus\Gamma_{i}),$

where
$V(\Gamma^{\prime}_{i}\oplus\Gamma_{i})=V(K_{4x})=\mathbb{Z}_{x}\times\mathbb{Z}_{4},$
Also

$\displaystyle(K_{4x}\times
K_{ky})(2)\cong\oplus_{i=0}^{x-1}\Big{\\{}\big{(}\Gamma^{\prime}_{i}\times
K_{ky}(2)\big{)}\oplus\big{(}\Gamma_{i}\times K_{ky}(2)\big{)}\Big{\\}}.$

By Theorem 2.4 and Theorem 2.10, $\Gamma^{\prime}_{i}\times K_{ky}(2)$ has a
$C_{k}$-factorization
$\mathcal{G}^{\prime}_{i}=\\{G^{\prime}_{i,1},G^{\prime}_{i,2},...,G^{\prime}_{i,(ky-1)}\\},$
for every $i\in\mathbb{Z}_{x}.$
It is clear that $\Gamma_{i}\times K_{ky}(2)\cong K_{4}(2)\times K_{ky}$. By
Theorem 2.5, $K_{4}(2)$ has a near $C_{3}$-factorization
$\mathcal{G}_{i}=\\{G_{i,1},G_{i,2},G_{i,3},G_{i,4}\\}$, and by Theorem 3.4,
$G_{i,j}\times K_{ky}$ has a $C_{k}$-factorization
$\mathcal{G}_{i,j}=\\{G_{i,j,1},G_{i,j,2},...,$ $G_{i,j,ky-1}\\}.$ Hence
$\Gamma_{i}\times K_{ky}(2)$ has a partial $C_{k}$-factorization.
One can check that $\mathcal{G}=\\{G^{\prime}_{i,l}\oplus
G_{i,j,l}|i\in\mathbb{Z}_{x},\ 1\leq j\leq 4,\ 1\leq l\leq ky-1\\}$ gives a
partial $C_{k}$-factorization of $(K_{4x}\times K_{ky})(2).$ Therefore
$k$-ARCS of $(K_{u}\times{K}_{g})(2)$ exists. ∎

######  Theorem 4.5.

For all even integers $k>6$, $y\geq 2$, $u=4x,\
x\in\mathbb{N}\setminus\\{2\\}$ and $g=ky,$ there exists a $k$-ARCS of
$(K_{u}\times{K}_{g})(2)$.

###### Proof.

Let $u=4x$ and $g=ky$, where $x\in\mathbb{N}\setminus\\{2\\},\ y\geq 2$ is
even.
We establish the proof in two cases.
Case (i): $x=1.$
We can write

$(K_{4}\times K_{ky})(2)\cong K_{4}(2)\times K_{ky}$

By Theorem 2.5, $K_{4}(2)$ has a near $C_{3}$-factorization
$\mathcal{G}=\\{G_{1},G_{2},G_{3},G_{4}\\}$, and by Theorem 3.5, each
$G_{i}\times K_{ky},\ 1\leq i\leq 4$ has a $C_{k}$-factorization
$\mathcal{G}_{i}=\\{G_{i,1},G_{i,2},...,G_{i,ky-1}\\}.$ Hence $(K_{4}\times
K_{ky})(2)$ has a partial $C_{k}$-factorization.
Case (ii): $x>2.$
Using a similar procedure as in case (ii) of Theorem 4.4, we can get the
following

$\displaystyle(K_{4x}\times
K_{ky})(2)\cong\oplus_{i=0}^{x-1}\Big{\\{}\big{(}\Gamma^{\prime}_{i}\times
K_{ky}(2)\big{)}\oplus\big{(}\Gamma_{i}\times K_{ky}(2)\big{)}\Big{\\}}.$

By Theorem 2.4 and Theorem 2.10, $\Gamma^{\prime}_{i}\times K_{ky}(2)$ has a
$C_{k}$-factorization
$\mathcal{G}^{\prime}_{i}=\\{G^{\prime}_{i,1},G^{\prime}_{i,2},...,G^{\prime}_{i,(ky-1)}\\},$
for every $i\in\mathbb{Z}_{x}.$
It is clear that $\Gamma_{i}\times K_{ky}(2)\cong K_{4}(2)\times K_{ky}$. By
Theorem 2.5, $K_{4}(2)$ has a partial $C_{3}$-factorization
$\mathcal{G}_{i}=\\{G_{i,1},G_{i,2},G_{i,3},G_{i,4}\\}$, and by Theorem 3.5,
$G_{i,j}\times K_{ky}$ has a $C_{k}$-factorization
$\mathcal{G}_{i,j}=\\{G_{i,j,1},G_{i,j,2},...,G_{i,j,ky-1}\\}.$ Hence
$\Gamma_{i}\times K_{ky}(2)$ has a partial $C_{k}$-factorization.
One can check that $\mathcal{G}=\\{G^{\prime}_{i,l}\oplus
G_{i,j,l}|i\in\mathbb{Z}_{x},\ 1\leq j\leq 4,\ 1\leq l\leq ky-1\\}$ gives a
partial $C_{k}$-factorization of $(K_{4x}\times K_{ky})(2).$ Therefore
$k$-ARCS of $(K_{u}\times{K}_{g})(2)$ exists. ∎

######  Theorem 4.6.

Let $k=p_{1}p_{2}p_{3}...p_{t}\geq 6$ be even, where
$p_{1},p_{2},p_{3},...,p_{t}$ are primes not necessarily distinct. If $u\equiv
1(mod\ p_{1}p_{2}p_{3}...p_{i})$, $g\equiv 0(mod\
2p_{i+1}p_{i+2}p_{i+3}...p_{t})$, $1\leq i<t-1,$ at least one of the
$p_{1},p_{2},p_{3},...,p_{i}$ is $2$ and $p_{i+1},p_{i+2},...,p_{t}$ are odd
primes, then there exists a $k$-ARCS of $(K_{u}\times{K}_{g})(2)$.

###### Proof.

We establish the proof in two cases
Case(i) $i=1$ and $p_{1}=2$.
Let $u=2x+1$, $g=2sy$, where $x,y\geq 1,$ $s=p_{2}p_{3}...p_{t}$ and $k=2s.$
Now

$\displaystyle(K_{u}\times K_{g})(2)$ $\displaystyle\cong$
$\displaystyle\\{(F_{1}\oplus F_{2}\oplus...\oplus F_{u})\times K_{g}\\}(2),\
\mbox{by Theorem \ref{t1}}$ $\displaystyle\cong$ $\displaystyle(F_{1}\times
K_{2sy})(2)\oplus...\oplus(F_{u}\times K_{2sy})(2),$

where each $F_{j}$, $1\leq j\leq u$ is a near $1$-factor of $K_{u}$. Since
$(F_{j}\times K_{2sy})(2)\cong\frac{u-1}{2}(K_{2}\times K_{ky}(2))$ and by
Theorem 2.4, $K_{ky}(2)$ has a $C_{k}$-factorization
$\\{{C}_{k}^{1},{C}_{k}^{2},...,{C}_{k}^{ky-1}\\},$ where $C_{k}^{l},\ \ 1\leq
l\leq ky-1,$ is a $C_{k}$-factor of $K_{ky}(2)$. By Theorem 2.10, each
$C_{k}\times K_{2}$ is a $C_{k}$-factor. Thus we have obtained $ky-1$
$C_{k}$-factors of $K_{ky}(2)\times K_{2}$. The $C_{k}$-factors obtained above
become the partial $C_{k}$-factors of $(K_{u}\times K_{g})(2)$. Thus we get
$(2x+1)(ky-1)$ partial $C_{k}$-factors of $(K_{u}\times K_{g})(2)$. Hence,
$k$-ARCS of $(K_{u}\times{K}_{g})(2)$ exists.
Case (ii) $1<i\ <t-1$
Suppose that $r=p_{1}p_{2}...p_{i}$ and $s=p_{i+1}p_{i+2}...p_{t},$ $1<i<t-1$
Let $u=rx+1$, $g=2sy$, where $x,y\geq 1$ and $k=rs.$
We can write

$\displaystyle(K_{u}\times K_{g})(2)$ $\displaystyle\cong$ $\displaystyle
K_{u}(2)\times K_{g}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\oplus...\oplus\mathcal{C}_{r}^{u})\times
K_{g},\mbox{by Theorem \ref{t4}}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\times
K_{(2s)y})\oplus...\oplus(\mathcal{C}_{r}^{u}\times K_{(2s)y}),$

where each $\mathcal{C}_{r}^{j}$, $1\leq j\leq u$ is a near $C_{r}$-factor of
$K_{u}(2)$. Since $\mathcal{C}_{r}^{j}\times K_{(2s)y}\cong x(C_{r}\times
K_{s(2y)})$, by Theorem 3.6 each $C_{r}\times K_{s(2y)}$ has a
$C_{rs}$-factorization. Thus we have obtained $2sy-1\ C_{k}$-factors of
$C_{r}\times K_{s(2y)}$. The $C_{k}$-factors obtained above become the partial
$C_{k}$-factors of $(K_{u}\times K_{g})(2)$. Thus, in total we get
$(rx+1)(2sy-1)$ partial $C_{k}$-factors of $(K_{u}\times K_{g})(2)$. Therefore
$k$-ARCS of $(K_{u}\times{K}_{g})(2)$ exists. ∎

######  Theorem 4.7.

Let $k=p_{1}p_{2}p_{3}...p_{t}\geq 6$ be even, where $p_{1},p_{2},...,p_{t}$
are primes not necessarily distinct. If $u\equiv 1(mod\
p_{1}p_{2}p_{3}...p_{i})$, $g\equiv(p_{i+1}p_{i+2}p_{i+3}...p_{t})(mod\
2p_{i+1}p_{i+2}p_{i+3}...p_{t})$ is odd, $1\leq i\leq t-1$ and at least one of
the $p_{1},p_{2},p_{3},...,p_{i}$ is $2$, then there exists a $k$-ARCS of
$(K_{u}\times{K}_{g})(2)$.

###### Proof.

Suppose that $r=p_{1}p_{2}...p_{i}$ and $s=p_{i+1}p_{i+1}...p_{t}$, $1\leq
i\leq t-1$.
We establish the proof in two cases.
Case (i): $i=1,\ p_{1}=2$
Let $u=2x+1$, $g=s(2y+1)$ and $k=2s$, where $x,y\geq 1$.
We can write

$\displaystyle(K_{u}\times K_{g})(2)$ $\displaystyle\cong$ $\displaystyle
K_{u}(2)\times K_{s(2y+1)}$ $\displaystyle\cong$ $\displaystyle(F_{1}\oplus
F_{2}\oplus...\oplus F_{u})\times K_{s(2y+1)},\ \mbox{by Theorem \ref{t1}}$
$\displaystyle\cong$ $\displaystyle(F_{1}\times
K_{s(2y+1)})\oplus...\oplus(F_{u}\times K_{s(2y+1)}),$

where each $F_{l},\ 1\leq l\leq u,$ consists of $2$ near $1$-factors of
$K_{u}(2)$. Since each $F_{l}\times K_{s(2y+1)}\cong 2\\{x(K_{2}\times
K_{s(2y+1)})\\}$ and by Theorem 2.1, $K_{s(2y+1)}$ has a $C_{s}$-factorization
$\\{{C}_{s}^{1},{C}_{s}^{2},...,{C}_{s}^{\frac{g-1}{2}}\\},$ where each
${C}_{s}^{m},\ 1\leq m\leq\frac{g-1}{2}$ is $C_{s}$-factor of $K_{s(2y+1)}$.
We write $K_{2}\times{C}_{s}^{m}\cong{C}_{s}^{m}\times
K_{2}\cong(2y+1)(C_{s}\times K_{2})$ and by Theorem 2.7, each $C_{s}\times
K_{2}$ is a $C_{2s}$-factor. Thus, in total we get $(2x+1)(g-1)$ partial
$C_{k}$-factors of $(K_{u}\times K_{g})(2)$. Hence, $k$-ARCS of
$(K_{u}\times{K}_{g})(2)$exists.
Case (ii): $1<i\leq t-1$
Let $u=rx+1$, $g=s(2y+1)$ and $k=rs$, where $x,y\geq 1$.

$\displaystyle(K_{u}\times K_{g})(2)$ $\displaystyle\cong$ $\displaystyle
K_{u}(2)\times K_{g}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\oplus\mathcal{C}_{r}^{2}\oplus...\oplus\mathcal{C}_{r}^{u})\times
K_{g},\ \ \mbox{by Theorem \ref{t4}}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\times
K_{g})\oplus(\mathcal{C}_{r}^{2}\times
K_{g})\oplus...\oplus(\mathcal{C}_{r}^{u}\times K_{g})$

where each $\mathcal{C}_{r}^{j}$, $1\leq j\leq u$ is a near $C_{r}$-factor of
$K_{u}(2)$. Since $C_{r}^{j}\times K_{g}\cong x(C_{r}\times K_{s(2y+1)}),$ by
Theorem 2.10, each $C_{r}\times K_{s(2y+1)}$ has $s(2y+1)-1$ $C_{rs}$ factors.
The $C_{k}$-factors obtained above become the partial $C_{k}$-factors of
$(K_{u}\times K_{g})(2)$. Thus, in total we get $(rx+1)(s(2y+1)-1)$ partial
$C_{k}$-factors of $(K_{u}\times K_{g})(2)$. Therefore $k$-ARCS of
$(K_{u}\times{K}_{g})(2)$ exists. ∎

######  Theorem 4.8.

Let $k=p_{1}p_{2}p_{3}...p_{t}\equiv 0(mod\ 4),r=p_{1}p_{2}p_{3}...p_{i},$ and
$s=p_{i+1}p_{i+2}p_{i+3}...p_{t},\ 1<i\leq t-1$ , where
$p_{1},p_{2},...,p_{t}$ are primes not necessarily distinct. If $u=rx+1,\
x\in\mathbb{N}\setminus\\{2\\}$, $g\equiv s(mod\ 2s)$ is odd, then there
exists a $k$-ARCS of $K_{u}\times{K}_{g}$.

###### Proof.

One can easily observe that $r=p_{1}p_{2}p_{3}...p_{i}\equiv 0(mod\ 4)$.
Let $u=(4m)x+1,$ $g=s(2y+1)$ is odd, where $x\in\mathbb{N}\setminus\\{2\\},\
4m=r,\ \ m\geq 1,\ y\geq 0$ and $k=rs$.
We establish the proof in two cases
Case (i): $x=1$.
We can write

$\displaystyle K_{r+1}\times K_{g}$ $\displaystyle\cong$ $\displaystyle
K_{r+1}\times K_{s(2y+1)}$ (13) $\displaystyle\cong$
$\displaystyle\\{(K_{r+1}\times
K_{2y+1})\otimes\bar{K}_{s}\\}\oplus(2y+1)(K_{r+1}\times K_{s})$

Graphs in the R.H.S of (13) can be obtained by making $2y+1$ holes of type
$K_{r+1}\times K_{s}$ in $K_{r+1}\times K_{s(2y+1)}$ and identifying the
$s$-subsets of $K_{s(2y+1)}$ (in the resulting graph) into a single vertex and
two of them are adjacent if the corresponding $s$-subsets form a $K_{s,s}$ in
$K_{r+1}\times K_{s(2y+1)}.$ By expanding the vertices into $s$-subsets we get
the first graph in (13).
Now consider

$\displaystyle(K_{r+1}\times K_{2y+1})\otimes\bar{K}_{s}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\oplus...\oplus\mathcal{C}_{r}^{r+1})\otimes\bar{K}_{s},\
\mbox{by case (i) of Theorem \ref{tt3} }$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\otimes\bar{K}_{s})\oplus...\oplus(\mathcal{C}_{r}^{rx+1}\otimes\bar{K}_{s}),$

where each $\mathcal{C}_{r}^{l},\ 1\leq l\leq r+1$, consists of $y$ partial
$C_{r}$-factors of $K_{r+1}\times K_{2y+1}.$ Since each
$\mathcal{C}_{r}^{l}\otimes\bar{K}_{s}\cong
y\\{(2y+1)(C_{r}\otimes\bar{K}_{s})\\}$ and by Theorem 2.9, each
$C_{r}\otimes\bar{K}_{s}$ has $s$ $C_{rs}$-factors. Thus we get $ys$ partial
$C_{rs}$-factors of $(K_{r+1}\times K_{2y+1})\otimes\bar{K}_{s}$.
Let $A_{0},A_{1},...,A_{r-1},A_{\infty}$ be the parts of $K_{r+1}\times
K_{s}.$ By Theorem 3.2, $K_{r+1}\times K_{s}$ has a partial
$C_{rs}$-factorization $\mathcal{G}=\\{G_{t,h}\cup
G_{h}^{\infty}|t\in\mathbb{Z}_{r},1\leq h\leq\frac{s-1}{2}\\}$ where each
$G_{t,h}$ is a partial $C_{rs}$\- factor missing the partite set
$A_{t+\frac{r}{2}}$ and the subscripts of $A$ are taken modulo $r$; each
$G_{h}^{\infty}$ is a partial $C_{rs}$-factor missing the partite set
$A_{\infty}.$
Finally, adding the partial $C_{rs}$-factors of (13) gives the
$\frac{s(2y+1)-1}{2}$ partial $C_{k}$-factors of $K_{r+1}\times K_{s(2y+1)}.$
Thus, in total we get $(r+1)(\frac{s(2y+1)-1}{2})$ partial $C_{k}$-factors of
$K_{r+1}\times K_{s(2y+1)}.$ Therefore $k$-ARCS of $K_{u}\times{K}_{g}$
exists.
Case (ii): $x>2.$
We can write

$\displaystyle K_{rx+1}\times K_{g}$ $\displaystyle\cong$ $\displaystyle
K_{rx+1}\times K_{s(2y+1)}$ (14) $\displaystyle\cong$
$\displaystyle\\{(K_{rx+1}\times
K_{2y+1})\otimes\bar{K}_{s}\\}\oplus(2y+1)(K_{rx+1}\times K_{s})$

Graphs in the R.H.S of (14) can be obtained by using a similar procedure as in
(13).
Now consider

$\displaystyle(K_{rx+1}\times K_{2y+1})\otimes\bar{K}_{s}$
$\displaystyle\cong$
$\displaystyle\\{\mathcal{C}_{r}^{1}\oplus...\oplus\mathcal{C}_{r}^{rx+1}\\}\otimes\bar{K}_{s},\
\mbox{by case(ii) of Theorem \ref{tt3}}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\otimes\bar{K}_{s})\oplus...\oplus(\mathcal{C}_{r}^{rx+1}\otimes\bar{K}_{s}),$

where each $\mathcal{C}_{r}^{l},\ 1\leq l\leq rx+1$, consists of $y$ partial
$C_{r}$-factors of $K_{rx+1}\times K_{2y+1}.$ Since each
$\mathcal{C}_{r}^{l}\otimes\bar{K}_{s}\cong
y\\{x(2y+1)(C_{r}\otimes\bar{K}_{s})\\}$ and by Theorem 2.9, each
$C_{r}\otimes\bar{K}_{s}$ has $s$ $C_{rs}$-factors. Thus we get $ys$ partial
$C_{rs}$-factors of $(K_{rx+1}\times K_{2y+1})\otimes\bar{K}_{s}$.
Now, we construct the partial $C_{rs}$-factors of $K_{rx+1}\times K_{s}$ as
follows:
Using a similar procedure as in case (ii) of Theorem 4.2, we can write

$\displaystyle K_{rx+1}\times
K_{s}\cong\oplus_{i=0}^{x-1}\big{\\{}(\Gamma^{\prime}_{i}\times
K_{s})\oplus(\Gamma_{i}\times K_{s})\big{\\}},$ (15)

where $\Gamma_{i}$ and $\Gamma^{\prime}_{i}$ are complete graph of order
$4m+1$ and the complete multipartite graph $K_{x}\otimes\bar{K}_{4m}$
respectively.

By Theorem 2.6, $\Gamma^{\prime}_{i}$ has a $C_{4m}$-factorization
$\mathcal{G}^{\prime}_{i}=\\{G^{\prime}_{i,1},G^{\prime}_{i,2},...,G^{\prime}_{i,2m}\\},$
and by Theorem 2.10, $G^{\prime}_{i,j}\times K_{s}$ has a
$C_{rs}$-factorization
$\mathcal{G}^{\prime}_{i,j}=\\{G^{\prime}_{i,j,1},G^{\prime}_{i,j,2},...,G^{\prime}_{i,j,s-1}\\},$
for every $i\in\mathbb{Z}_{x},$ and $j\in\\{1,2,...,2m\\}.$ Hence,
$\cup_{j}\mathcal{G}^{\prime}_{i,j}$ gives a $C_{k}$-factorization of
$\Gamma^{\prime}_{i}\times K_{s}.$

Considering that $\Gamma_{i}\times K_{s}\cong K_{r+1}\times K_{s},$ let
$A_{0},A_{1},...,A_{r-1},A_{\infty}$ be the parts of $K_{r+1}\times K_{s}.$ By
Theorem 3.2, $\Gamma_{i}\times K_{s}(\cong K_{r+1}\times K_{s})$ has a partial
$C_{k}$-factorization $\mathcal{G}_{i}=\\{G_{i,t,h}\cup
G_{i,h}^{\infty}|i\in\mathbb{Z}_{x},\ t\in\mathbb{Z}_{r},\ 1\leq
h\leq\frac{s-1}{2}\\}$ where each $G_{i,t,h}$ is a partial $C_{k}$-factor
missing the partite set $A_{t+\frac{r}{2}}$ and the subscripts of $A$ are
taken modulo $r$; each $G_{i,h}^{\infty}$ is a partial $C_{k}$-factor missing
the partite set $A_{\infty}.$
One can check that $\mathcal{G}=\\{G^{\prime}_{i,j,l}|i\in\mathbb{Z}_{x},1\leq
j\leq 2m,1\leq l\leq s-1\\}\cup\\{G_{i,t,h}\cup
G_{i,h}^{\infty}|i\in\mathbb{Z}_{x},t\in\mathbb{Z}_{r},1\leq
h\leq\frac{s-1}{2}\\}$ gives a partial $C_{k}$-factorization of
$K_{rx+1}\times K_{s}.$
Finally, adding the partial $C_{k}$-factors of (14) gives the
$\frac{s(2y+1)-1}{2}$ partial $C_{k}$-factors of $K_{rx+1}\times K_{s(2y+1)}.$
Thus, in total we get $(rx+1)(\frac{s(2y+1)-1}{2})$ partial $C_{k}$-factors of
$K_{rx+1}\times K_{s(2y+1)}.$ Therefore $k$-ARCS of $K_{u}\times{K}_{g}$
exists.

∎

######  Theorem 4.9.

Let $k=p_{1}p_{2}p_{3}...p_{t}\geq 6$ be even, where
$p_{1},p_{2},p_{3},...,p_{t}$ are primes not necessarily distinct. If $u\equiv
1(mod\ p_{1}p_{2}p_{3}...p_{i})$ and $g\equiv 0(mod\
p_{i+1}p_{i+2}p_{i+3}...p_{t})$, $1\leq i\leq t-1,$
$p_{1},p_{2},p_{3},...,p_{i}$ are odd primes and at least one of the
$p_{i+1},p_{i+2},p_{i+3},...,p_{t}$ is $2$, then there exists a $k$-ARCS of
$(K_{u}\times{K}_{g})(2)$.

###### Proof.

Suppose that $r=p_{1}p_{2}...p_{i}$ and $s=p_{i+1}p_{i+1}...p_{t}$, $1\leq
i\leq t-1$. Let $u=rx+1$, $g=sy$, where $x,y\geq 1$ and $k=rs$, $1\leq i\leq
t-1$.
Now, we write

$\displaystyle(K_{u}\times K_{g})(2)$ $\displaystyle\cong$ $\displaystyle
K_{rx+1}(2)\times K_{g}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\oplus...\oplus\mathcal{C}_{r}^{u})\times
K_{g},\ \mbox{by Theorem \ref{t5}}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\times
K_{sy})\oplus...\oplus(\mathcal{C}_{r}^{u}\times K_{sy}),$

where each $\mathcal{C}_{r}^{j}$, $1\leq j\leq u,$ is a near ${C}_{r}$-factor
of $K_{u}(2)$. Since $\mathcal{C}_{r}^{j}\times K_{sy}\cong x(C_{r}\times
K_{sy}),$ by Theorem 2.10, for each $C_{r}\times K_{sy}$ has $sy-1$
$C_{rs}$-factors. The $C_{rs}$-factors obtained above become the partial
$C_{rs}$-factors of $(K_{rx+1}\times K_{sy})(2)$. Thus, in total we get
$(rx+1)(sy-1)$ partial $C_{rs}$-factors of $(K_{rx+1}\times K_{sy})(2).$
Therefore $k$-ARCS of $(K_{u}\times{K}_{g})(2)$ exists. ∎

######  Theorem 4.10.

Let $k=p_{1}p_{2}p_{3}...p_{t}\equiv 0(mod\ 4)$, where
$p_{1},p_{2},p_{3},..,p_{t}$ are primes not necessarily distinct. If $u\equiv
1(mod\ p_{1}p_{2}p_{3}...p_{i})$ and $g\equiv 0(mod\
p_{i+1}p_{i+2}p_{i+3}...p_{t})$, $1\leq i<t-1,$ at least one of the
$p_{1},p_{2},...,p_{i}$ and $p_{i+1},p_{i+2},...,p_{t}$ is $2$, then there
exists a $k$-ARCS of $(K_{u}\times{K}_{g})(2)$.

###### Proof.

Suppose that $r=p_{1}p_{2}...p_{i}$ and $s=p_{i+1}p_{i+1}...p_{t}$, $1\leq
i\leq t-1$.
We establish the proof in two cases
Case (i) $i=1$ and $p_{1}=2$.
Let $u=2x+1$, $g=2sy$, where $x,y\geq 1$ and $k=2s.$
This is substantially the same proof as in case (i) of Theorem 4.6. The only
difference is that we take $s$ is even.
Case (ii) $1<i<t-1$
Let $u=rx+1$, $g=sy$, where $x,y\geq 1$ and $k=rs$. We can write

$\displaystyle(K_{u}\times K_{g})(2)$ $\displaystyle\cong$ $\displaystyle
K_{rx+1}(2)\times K_{g}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\oplus...\oplus\mathcal{C}_{r}^{u})\times
K_{g},\ \mbox{by Theorem \ref{t4}}$ $\displaystyle\cong$
$\displaystyle(\mathcal{C}_{r}^{1}\times
K_{sy})\oplus...\oplus(\mathcal{C}_{r}^{u}\times K_{sy}),$

where each $\mathcal{C}_{r}^{j}$, $1\leq j\leq u,$ is a near ${C}_{r}$-factor
of $K_{u}(2)$. Since $\mathcal{C}_{r}^{j}\times K_{sy}\cong x(C_{r}\times
K_{sy}),$ and we know that $C_{r}\times K_{sy}\cong(C_{r}\times
K_{y})\otimes\bar{K}_{s}\oplus y(C_{r}\times K_{s}).$ By Theorem 2.10,
$C_{r}\times K_{y}$ has a $y-1$ $C_{r}$-factors, and by Theorem 2.9, each
$C_{r}\otimes\bar{K}_{s}$ has a $sC_{rs}$-factors. By Theorem 2.8,
$C_{r}\times K_{s}$ has a $C_{rs}$-factors. Thus we have obtained $(sy-1)\
C_{k}$-factors of $C_{r}\times K_{sy}$. The $C_{k}$-factors obtained above
become the partial $C_{k}$-factors of $(K_{rx+1}\times K_{sy})(2)$. Thus, in
total we get $(rx+1)(sy-1)$ partial $C_{k}$-factors of $(K_{rx+1}\times
K_{sy})(2).$ Therefore $k$-ARCS of $(K_{u}\times{K}_{g})(2)$ exists. ∎

###### Proof of Theorem 1.2.

Let $k=p_{1}p_{2}p_{3}...p_{t}$, where $p_{1},p_{2},p_{3},...,p_{t}$ are
primes not necessarily distinct.
Necessity follows from Theorem 1.1. Sufficiency can be divided into two cases.
Case (i): When $\lambda=1$, the values of $u$ and $g$ are one of the following

  * (a)

$u=kx+1$, $g\geq 3$ is odd, where $x\in\mathbb{N}\setminus\\{2\\};$

  * (b)

$u=rx+1,\ g\equiv s(mod\ 2s)$ is odd, where $r=p_{1}p_{2}p_{3}...p_{i}\equiv
0(mod\ 4),\ s=p_{i+1}p_{i+2}...p_{t},\ 1<i\leq t-1,\
x\in\mathbb{N}\setminus\\{2\\};$

Case (ii): When $\lambda=2$, the values of $u$ and $g$ are one of the
following

  * (c)

$u\equiv 1(mod\ k)$, $g\geq 2;$

  * (d)

$u\geq 3$ is odd, $g\equiv 0(mod\ k);$

  * (e)

$u=4x$, $g=ky$, $x\in\mathbb{N}\setminus\\{2\\},\ y\geq 1$ is odd, where
$k\geq 6;$

  * (f)

$u=4x$, $g=ky$, $x\in\mathbb{N}\setminus\\{2\\},\ y\geq 2$ is even, where
$k>6$;

  * (g)

$u\equiv 1(mod\ p_{1}p_{2}p_{3}...p_{i})$, $g\equiv 0(mod\
2p_{i+1}p_{i+2}...p_{t})$, $1\leq i<t-1$, where at least one of the
$p_{1},p_{2},...,p_{i}$ is $2$ and $p_{i+1},p_{i+2},...,p_{t}$ are odd primes;

  * (h)

$u\equiv 1(mod\ p_{1}p_{2}p_{3}...p_{i})$, $g\equiv 0(mod\
p_{i+1}p_{i+2}...p_{t})$, $1\leq i\leq t-1$, where $p_{1},p_{2},...,p_{i}$ are
odd primes and at least one of the $p_{i+1},p_{i+2},...,p_{t}$ is $2;$

  * (i)

$u\equiv 1(mod\ p_{1}p_{2}p_{3}...p_{i})$, $g\equiv 0(mod\
p_{i+1}p_{i+2}...p_{t})$, $1\leq i<t-1$, where at least one of
$p_{1},p_{2},...,p_{i}$ and $p_{i+1},p_{i+2},...,p_{t}$ is $2$.

The proof for (a),(b),(c),(d),(e),(f),(g),(h), and (i) follows from Theorems
4.2, 4.8,4.1, 4.3, 4.4, 4.5, 4.6, 4.9, and 4.10.
If $\lambda>2$ is odd (respectively, even), the values for $u$ and $g$ are the
same as that of case(i) (respectively, case(i) and case (2)). Hence $k$-ARCS
of $(K_{u}\times{K}_{g})(\lambda)$ exists. ∎

######  Remark 4.1.

For both even $\lambda\geq 2,\ k\equiv 2(mod\ 4),$ there exists a $k$-ARCS of
$(K_{u}\times{K}_{g})(\lambda)$ if and only if $u\geq 3$, $g\geq 2$,
$\lambda(g-1)\equiv 0(mod\ 2)$, $g(u-1)\equiv 0(mod\ k)$ except possibly
$(u,k)\in\\{(8,4s+2),(4t+2,4s+2)|s,t\geq 1\\}$ and $(u,g,k)\in\\{(4t,6y,6)|\
t\geq 1\ \mbox{and}\ y\geq 2\ \mbox{is even}\\}.$

When $\lambda=2$ proof for the above statement is immediately follows from
Theorems 4.1, 4.3 \- 4.6, 4.7, and 4.9. If $\lambda>2$ is even, the values for
$u$ and $g$ are the same as that of Theorems 4.1, 4.3 \- 4.6, 4.7, and 4.9.
Hence $k$-ARCS of $(K_{u}\times{K}_{g})(\lambda)$ exists.

##  5 Conclusion

In this paper, we have settled the existence of $k$-ARCS of
$(K_{u}\times{K}_{g})(\lambda)$, for $k\equiv 0(mod\ 4)$ with few possible
exceptions. Our results also gives a partial solution to the existence of
modified cycle frames of complete multipartite multigraphs.

## Acknowledgments:

First author thank the Periyar University for its support through URF grant
no: PU/ AD-3/URF/015723/2020.
Second author thank NBHM for its support through PDF grant no:
2/40(22)/2016/R&D-11/15245.
Corresponding author thank DST, New Delhi for its support through FIST grant
no: SR/FIST/MSI-115/2016 (Level-I).

## References

  * [1] R.J.R. Abel and A. Assaf, Modified group divisible designs with block size 5 and $\lambda=1,$ Discrete Math., 256 (2002) 1-22.
  * [2] B. Alspach, P.J. Schellenberg, D.R. Stinson, and D. Wagner, The oberwolfach problem and factors of uniform odd length cycles, J. Combin. Theory Ser. A, 52 (1989) 20-43.
  * [3] A. Assaf, Modified group divisible designs, Ars Combin., 29 (1990) 13-20.
  * [4] A. Assaf and R. Wei, Modified group divisible designs with block size 4 and $\lambda=1,$ Discrete Math., 195 (1999) 15-25.
  * [5] M. Buratti, H. Cao, D. Dai, and T. Traetta, A complete solution to the existence of $(k,\lambda)$ -cycle frame of type $g^{u},$ J.Combin. Designs, 25 (2016) 197-230.
  * [6] J. Burling and K. Heinrich, Near 2-factorizations of $2K_{n}$ : cycles of even length, Graphs and Combin., 5 (1989) 213-221.
  * [7] H. Cao, M.Niu, and C. Tang, On the existence of cycle frames and almost resolvable cycle systems, Discrete Math., 311 (2011) 2220-2232.
  * [8] H. Cao, Y. Wu, and H. Zhou, Modified frames with block size 3, J. Combin. Designs, 16 (2008) 351-363.
  * [9] V. Chitra, A. Shanmuga Vadivu, and A. Muthusamy, $C_{4p}$ -frame of complete multipartite multigraphs, Aequationes Math., 85 (2013) 563-579.
  * [10] G. Ge and Y. Miao, “Frames and resolvability”in CRC Handbook of Combinatorial Designs, C.J. Colbourn and J.H. Dinitz (Editors), 1996.
  * [11] G. Ge, J. Wang, and R. Wei, MGDD with block size 4 and its application to sampling designs, Discrete Math., 272 (2003) 277-283.
  * [12] K. Heinrich, C.C. Lindner, and C. A. Rodger, Almost resolvable decomposition of $2K_{n}$ into cycles of odd length, J. Combin. Theory Ser. A, 49 (1988) 218-232.
  * [13] H. Enomoto, T. Miyamoto, and K. Ushio, $C_{k}$ -factorization of complete bipartite graphs, Graphs and Combin., 4 (1988) 111-113.
  * [14] J.D. Horton, B.K. Roy, P.J. Schellenberg, and D.R. Stinson, On decomposing graphs into isomorphic uniform 2-factors, Annals of Discrete Math., 27 (1985) 297-319.
  * [15] W. Imrich and S. Klavzar, Product graphs-structure and recognition, Wiley Interscience Series in Discrete Mathematics and Optimization, 2000\.
  * [16] R. Laskar, Decomposition of some composite graphs into hamiltonian cycles, Proc. 5th Hungarian Coll. Kesathely 1976, North Holland, (1978) 705-716.
  * [17] R.S. Manikandan and P. Paulraja, $C_{p}$ -decompositions of some regular graphs, Discrete Math., 306 (2006) 429-451.
  * [18] R.S. Manikandan and P. Paulraja, Hamiltonian decompositions of the tensor product of a complete graph and a complete bipartite graph, Ars combin., 80 (2006) 33-44.
  * [19] R.S. Manikandan and P. Paulraja, $C_{5}$ -decompositions of the tensor product of complete graphs, Australas.J.Combin., 37 (2007) 285-293.
  * [20] M. Mishima and H.L. Fu, Resolvable even- cycle systems with a 1 -rotational automorphism, J. Combin. Designs, 11 ( 2003) 394-407.
  * [21] A. Muthusamy and P. Paulraja, Factorization of product graphs into cycles of uniform length, Graphs and Combin., 11 (1995) 69-90.
  * [22] A. Muthusamy and A. Shanmuga Vadivu, Cycle frames of complete multipartite multigraphs -III, J. Combin. Designs, 22 (2014) 473-487.
  * [23] M. Niu and H. Cao, More results on cycle frames and almost resolvable cycle systems, Discrete Math., 312 (2012) 3392-3405.
  * [24] P. Paulraja and S. Sampath Kumar, Resolvable even cycle decompositions of the tensor product of complete graphs, Discrete Math., 311 (2011) 1841-1850.
  * [25] D.R. Stinson, Frames for kirkman triple systems, Discrete Math., 65 ( 1987) 289-300.