## C 4 AND C 6 DECOMPOSITION OF THE TENSOR PRODUCT OF COMPLETE GRAPHS

1 OPEYEMI OYEWUMI AND 2 ABOLAPE DEBORAH AKWU

Abstract. Let G be a simple and finite graph. A graph is said to be decomposed into subgraphs H 1 and H 2 which is denoted by G = H 1 ⊕ H 2 , if G is the edge disjoint union of H 1 and H 2 . If G = H 1 ⊕ H 2 ⊕ H 3 ⊕···⊕ H k , where H H H 1 , 2 , 3 , ..., H k are all isomorphic to H , then G is said to be H -decomposable. Futhermore, if H is a cycle of length m then we say that G is C m -decomposable and this can be written as C m | G . Where G × H denotes the tensor product of graphs G and H , in this paper, we prove the necessary and sufficient conditions for the existence of C 4 -decomposition (respectively, C 6 -decomposition ) of K m × K n . Using these conditions it can be shown that every even regular complete multipartite graph G is C 4 -decomposable (respectively, C 6 -decomposable) if the number of edges of G is divisible by 4 (respectively, 6).

## 1. Introduction

Let C m , K m and K m -I denote cycle of length m , complete graph on m vertices and complete graph on m vertices minus a 1-factor respectively. By an m -cycle we mean a cycle of length m . Let K n,n denote the complete bipartite graph with n vertices in each bipartition set and K n,n -I denote K n,n , with a 1-factor removed. All graphs considered in this paper are simple and finite. A graph is said to be decomposed into subgraphs H 1 and H 2 which is denoted by G = H 1 ⊕ H 2 , if G is the edge disjoint union of H 1 and H 2 . If G = H 1 ⊕ H 2 ⊕···⊕ H k , where H H 1 , 2 , ..., H k are all isomorphic to H , then G is said to be H -decomposable. Futhermore, if H is a cycle of length m then we say that G is C m -decomposable and this can be written as C m | G . A k -factor of G is a k -regular spanning subgraph. A k -factorization of a graph G is a partition of the edge set of G into k -factors. A C k -factor of a graph is a 2-factor in which each component is a cycle of length k . A resolvable k -cycle decomposition (for short k -RCD) of G denoted by C k || G , is a 2-factorization of G in which each 2-factor is a C k -factor.

For two graphs G and H their tensor product G × H has vertex set V ( G ) × V ( H ) in which two vertices ( g , h 1 1 ) and ( g , h 2 2 ) are adjacent whenever g g 1 2 ∈ E G ( ) and h h 1 2 ∈ E H ( ). From this, note that the tensor product of graphs is distributive over edge disjoint union of graphs, that is if G = H 1 ⊕ H 2 ⊕···⊕ H k , then G × H = ( H 1 × H ) ⊕ ( H 2 × H ) ⊕···⊕ ( H k × H ). Now, for h ∈ V ( H ), V ( G ) × h = ( { v, h ) | v ∈ V ( G ) } is called a column of vertices of G × H corresponding to h . Further, for y ∈ V ( G ), y × V ( H ) = { ( y, v ) | v ∈ V ( H ) } is called a layer of vertices of G × H corresponding to y . It is true that K m × K 2 is isomorphic to the complete bipartite graph K m,m

2010 Mathematics Subject Classification. 05C70.

Key words and phrases. cycle decomposition, tensor product, complete graph.

1 Present Address: Air Force Institute of Technology, Kaduna, Nigeria.

2 Present Address: Federal University of Agriculture, Makurdi, Nigeria.

with the edges of a perfect matching removed, i.e. K m × K 2 ∼ = K m,m -I , where I is a 1-factor of K m,m .

The Lexicographic product G ∗ H of two graphs G and H is the graph having the vertex set V ( G ) × V ( H ), in which two vertices ( g , h 1 1 ) and ( g , h 2 2 ) are adjacent if either g , g 1 2 ∈ E G ( ); or g 1 = g 2 and h , h 1 2 ∈ E H ( ).

The problem of finding C k -decomposition of K 2 n +1 or K 2 n -I where I is a 1factor of K 2 n , is completely settled by Alspach, Gavlas and ˇ ajna in two different S papers (see [2, 17]). A generalization to the above complete graph decomposition problem is to find a C k -decomposition of K m ∗ K n , which is the complete m -partite graph in which each partite set has n vertices. The study of cycle decompositions of K m ∗ K n was initiated by Hoffman et al. [6]. In the case when p is a prime, the necessary and sufficient conditions for the existence of C p -decomposition of K m ∗ K n , p ≥ 5 is obtained by Manikandan and Paulraja in [10, 11, 13]. Billington [3] has studied the decomposition of complete tripartite graphs into cycles of length 3 and 4. Furthermore, Cavenagh and Billington [5] have studied 4-cycle, 6-cycle and 8-cycle decomposition of complete multipartite graphs. Billington et al. [4] have solved the problem of decomposing ( K m ∗ K n ) into 5-cycles. Similarly, when p ≥ 3 is a prime, the necessary and sufficient conditions for the existence of C 2 p -decomposition of K m ∗ K n is obtained by Smith (see [19]). For a prime p ≥ 3, it was proved in [20] that C 3 p -decomposition of K m ∗ K n exists if the obvious necessary conditions are satisfied. As the graph K m × K n ∼ = K m ∗ K n -E nK ( m ) is a proper regular spanning subgraph of K m ∗ K n . It is therefore natural to think about the cycle decomposition of K m × K n .

/negationslash

The results in [10, 11, 13] also gives the necessary and sufficient conditions for the existence of a p -cycle decomposition, (where p ≥ 5 is a prime number) of the graph K m × K n . In [12] it was shown that the tensor product of two regular complete multipartite graph is Hamilton cycle decomposable. Muthusamy and Paulraja in [14] proved the existence of C kn -factorization of the graph C k × K mn , where mn = 2(mod 4) and k is odd. Paulraja and Kumar [16] showed that the necessary conditions for the existence of a resolvable k -cycle decomposition of tensor product of complete graphs are sufficient when k is even. In this paper, we prove the necessary and sufficient conditions for K m × K n , where m,n ≥ 2, to have a C 4 -decomposition (respectively, C 6 -decomposition). Among other results, here we prove the following main results. It is not surprising that the conditions in Theorem 1.1 and Theorem 1.2 are 'symmetric' with respect to m and n since K m × K n ∼ = K n × K m .

Theorem 1.1. For m,n ≥ 2 , C 4 | K m × K n if and only if either

- (1) n ≡ 0 ( mod 4) and m is odd,
- (2) m ≡ 0 ( mod 4) and n is odd or
- (3) m or n ≡ 1 ( mod 4)

Theorem 1.2. For 2 ≤ m,n,C 6 | K m × K n if and only if m ≡ 1 or 3 ( mod 6) or n ≡ 1 or 3 ( mod 6) .

Theorem 1.3. Let m be an even integer and m ≥ 6 , then C 6 | K m -I × K n if and only if m ≡ 0 or 2 ( mod 6)

## 2. Preliminaries

- 2.1. Definition. Let ρ be a permutation of the vertex set V of a graph G . For any subset U of V , ρ acts as a function from U to V by considering the restriction of ρ to U . If H is a subgraph of G with vertex set U , then ρ H ( ) is a subgraph of G provided that for each edge xy ∈ E H ( ), ρ x ρ y ( ) ( ) ∈ E G ( ). In this case, ρ H ( ) has vertex set ρ U ( ) and edge set { ρ x ρ y ( ) ( ) : xy ∈ E H ( ) } .

Next, we give some existing results on cycle decomposition of complete graphs.

Theorem 2.1. [7] Let m be an odd integer and m ≥ 3 . If m ≡ 1 or 3 ( mod 6) then C 3 | K m .

Theorem 2.2. [17] Let n be an odd integer and m be an even integer with 3 ≤ m ≤ n . The graph K n can be decomposed into cycles of length m whenever m divides the number of edges in K n .

Now we have the following lemma, this lemma gives the cycle decomposition of the complete graph K m into cycles of length 3 and 4.

Lemma 2.3. For m ≡ 5( mod 6) , there exist positive integers p and q such that K m is decomposable into p 3 -cycles and q 4 -cycles.

Proof. Let the vertices of K m be 0 , 1 , ..., m -1. The 4-cycles are ( i, i +1+2 s, i -1 , i + 2+2 ) s , s = 0 1 , , ..., ( m i / -) 2 -2 , i = 1 3 , , ..., m -4. The 3-cycles are ( m -1 , i -1 , i ) , i = 1 3 , , ..., m -2. Hence the proof. /square

The following theorem is on the complete bipartite graph minus a 1-factor, it was obtained by Ma et. al [9].

Theorem 2.4. [9] Let m and n be positive integers. Then there exist an m cycle system of K n,n -I if and only if n ≡ 1 ( mod 2) , m ≡ 0 ( mod 2) , 4 ≤ m ≤ 2 n and n n ( -1) ≡ 0 ( mod m ) .

From the theorem above we have the following corollary.

Corollary 2.5. The graph K n,n -I , where I is a 1 -factor of K n,n -I admits a C 4 decomposition if and only if n ≡ 1 ( mod 4) .

The following result is on the complete bipartite graphs.

Theorem 2.6. [18] The complete bipartite graph K a,b can be decomposed into cycles of length 2 k if and only if a and b are even, a ≥ k , b ≥ k and 2 k divides ab .

The next result is on cycle decomposition of complete graph minus a 1-factor.

Theorem 2.7. [17] Let n be an even integer and m be an odd integer with 3 ≤ m ≤ n . The graph K n -I can be decomposed into cycles of length m whenever m divides the number of edges in K n -I .

## 3. C 4 Decomposition of C m × K n

We begin this section with the following lemma.

Lemma 3.1. C 4 | C 3 × K 4 .

/negationslash

Proof. Following from the definition of the tensor product of graphs, let U 1 = { u , v 1 1 , w 1 } , U 2 = { u , v 2 2 , w 2 } , ... , U 4 = { u , v 4 4 , w 4 } form the partite sets of vertices in the product C 3 × K 4 . For 1 ≤ i, j ≤ 4, surely U i ∪ U j , i = j induces a K 3 3 , -I , where I is a 1-factor of K 3 3 , .

A C 4 decomposition of C 3 × K 4 is given below:

{ u , v 1 4 , u 2 , w 3 } { , u , v 1 3 , u 4 , w 2 } { , u , v 1 2 , u 3 , w 4 } { , u , v 2 3 , w 2 , v 1 } { , u , v 3 1 , w 3 , v 4 } , { u , w 2 1 , v 3 , w 4 } { , u , w 3 2 , v 4 , w 1 } { , u , v 4 1 , w 4 , v 2 } and { u , w 4 1 , v 2 , w 3 } /square

Next, we have the following lemma which follows from Lemma 3.1.

## Lemma 3.2. C 4 | C 3 × K 5 .

Proof. Suppose we fix the 4-cycles already given in Lemma 3.1, clearly the graph which remains after removing the edges of C 3 × K 4 from C 3 × K 5 can be decomposed into 3 copies of K 2 4 , . Now, by Theorem 2.6 the graph K 2 4 , can be decomposed into cycles of length 4. Hence C 4 | C 3 × K 5 . /square

The following theorem is an extension of Lemma 3.1 and Lemma 3.2.

Theorem 3.3. C 4 | C 3 × K n if and only if n ≡ 0 or 1 ( mod 4) .

/negationslash

Proof. Suppose that C 4 | C 3 × K n . The graph C 3 × K n has 3 n n ( -1) edges. For C 4 | C 3 × K n it implies that n n ( -1) ≡ 0 (mod 4). Hence n ≡ 0 or 1 (mod 4). Following the definition of tensor product of graphs, let U 1 = { u , v 1 1 , w 1 } , U 2 = { u , v 2 2 , w 2 } ,..., U n = { u , v n n , w n } form the partite sets of vertices in the product C 3 × K n . For 1 ≤ i, j ≤ n , surely U i ∪ U j , i = j induces a K 3 3 , -I , where I is a 1-factor of K 3 3 , .

Next, we prove the sufficiency in two cases.

Case 1. Whenever n ≡ 0(mod 4). Let n = 4 t where t ≥ 1.

Next we note that C 3 × K n ∼ = ( C 3 × K 4 ) + ( C 3 × K 4 ) + ( C 3 × K 4 ) + · · · + ( C 3 × K 4 ) + H ∗ , H ∗ is the graph containing the edges of C 3 × K n which are not covered by these t copies of C 3 × K 4 . By Lemma 3.1 the product C 3 × K 4 admits a C 4 -decomposition.

Furthermore, we define the set U = { u , u 1 2 , ..., u p } , V = { v , v 1 2 , ..., v p } and W = { w , w 1 2 , ..., w p } where p = n/ 4 and for j = 1 2 , , ..., p , u j = { u i | 4 j -3 ≤ i ≤ 4 j } , v j = { v i | 4 j -3 ≤ i ≤ 4 j } and w j = { w i | 4 j -3 ≤ i ≤ 4 j } .

Now, H ∗ is decomposable into graphs isomorphic to K 4 4 , n -4 . Indeed, the K 4 4 , n -4 graphs in the decomposition of H ∗ are induced by ( u i ∪ v 1 ∪ v 2 ∪ · · · ∪ v p ) \ v i , ( u i ∪ w 1 ∪ w 2 ∪ · · · ∪ w p ) \ w i and ( v i ∪ w 1 ∪ w 2 ∪ · · · ∪ w p ) \ w i , i = 1 2 , , ..., p . By Theorem 2.6 C 4 | K 4 4 , n -4 . Therefore we have decomposed C 3 × K n into 4-cycles when n ≡ 0(mod 4).

Case 2. Whenever n ≡ 1(mod 4). Let n = 4 t +1 where t ≥ 1. By removing U 1 , we obtain a copy of C 3 × K n -1 , so we may apply Case 1. The remaining structure can be decomposed into 3 K 2 4 , t and by Theorem 2.6 C 4 | K 2 4 , t . Therefore C 4 | C 3 × K n when n ≡ 1(mod 4). /square

## 4. C 6 Decomposition of C 3 × K n

Theorem 4.1. For all n , C 6 | C 3 × K n .

Proof. Following from the definition of tensor product of graphs, let U 1 = { u , v 1 1 , w 1 } , U 2 = { u , v 2 2 , w 2 } , ... , U n = { u , v n n , w n } form the partite set of vertices in C 3 × K n .

/negationslash

Also, U i and U j has an edge in C 3 × K n for 1 ≤ i, j ≤ n and i = j if the subgraph induce K 3 3 , -I , where I is a 1-factor of K 3 3 , . Now, each subgraph U i ∪ U j is isomorphic to K 3 3 , -I . But K 3 3 , -I is a cycle of length six. Hence the proof. /square

Example 4.2. The graph C 3 × K 7 can be decomposed into cycles of length 6 . Solution. Let the partite sets (layers) of the tripartite graph C 3 × K 7 be U = { u , u 1 2 , ..., u 7 } , V = { v , v 1 2 , ..., v 7 } and W = { w , w , ..., w 1 2 7 } . We assume that the vertices of U, V and W having same subscripts are the corresponding vertices of the partite sets. A 6 -cycle decomposition of C 3 × K 7 is given below:

{ u , v 1 2 , w 1 , u 2 , v 1 , w 2 } { , u , v 1 3 , w 1 , u 3 , v 1 , w 3 } { , u , v 2 3 , w 2 , u 3 , v 2 , w 3 } , { u , v 1 4 , w 1 , u 4 , v 1 , w 4 } { , u , v 2 4 , w 2 , u 4 , v 2 , w 4 } { , u , v 3 4 , w 3 , u 4 , v 3 , w 4 } , { u , v 1 5 , w 1 , u 5 , v 1 , w 5 } { , u , v 2 5 , w 2 , u 5 , v 2 , w 5 } { , u , v 3 5 , w 3 , u 5 , v 3 , w 5 } , { u , v 4 5 , w 4 , u 5 , v 4 , w 5 } { , u , v 1 6 , w 1 , u 6 , v 1 , w 6 } { , u , v 2 6 , w 2 , u 6 , v 2 , w 6 } , { u , v 3 6 , w 3 , u 6 , v 3 , w 6 } { , u , v 4 6 , w 4 , u 6 , v 4 , w 6 } { , u , v 5 6 , w 5 , u 6 , v 5 , w 6 } , { u , v 1 7 , w 1 , u 7 , v 1 , w 7 } { , u , v 2 7 , w 2 , u 7 , v 2 , w 7 } { , u , v 3 7 , w 3 , u 7 , v 3 , w 7 } , { u , v 4 7 , w 4 , u 7 , v 4 , w 7 } { , u , v 5 7 , w 5 , u 7 , v 5 , w 7 } { , u , v 6 7 , w 6 , u 7 , v 6 , w 7 } .

## 5. C m Decomposition of C m × K n

Next, we establish the following lemma.

## Lemma 5.1. For all n ≥ 3 , C 4 | C 4 × K n .

/negationslash

Proof. From the definition of tensor product of graphs, let U 1 = { u , v 1 1 , w 1 , x 1 } , U 2 = { u , v 2 2 , w 2 , x 2 } , ... , U n = { u , v n n , w n , x n } form the partite sets of vertices in the product C 4 × K n . Also, for 1 ≤ i, j ≤ n and i = , j U i ∪ U j induces K 4 4 , -2 I , where I is a 1-factor of K 4 4 , . Now, each set U i ∪ U j is isomorphic to K 4 4 , -2 I . But K 4 4 , -2 I admits a 4-cycle decomposition. Hence the proof. /square

## Lemma 5.2. C 6 | C 6 × K 2

Proof. Let the partite set of the bipartite graph C 6 × K 2 be { u , u 1 2 , ..., u 6 } , { v , v 1 2 , ..., v 6 } . We assume that the vertices having the same subscripts are the corresponding vertices of the partite sets. Now C 6 × K 2 can be decomposed into 6-cycles which are { u , v 1 2 , u 3 , v 4 , u 5 , v 6 } and { v , u 1 2 , v 3 , u 4 , v 5 , u 6 } . /square

## Theorem 5.3. For all n , C 6 | C 6 × K n .

/negationslash

Proof. Let the partite set of the 6-partite graph C 6 × K n be U = { u , u 1 2 , ..., u n } , V = { v , v 1 2 , ..., v n } , W = { w , w , ..., w 1 2 n } , X = { x , x 1 2 , ..., x n } , Y = { y , y 1 2 , ..., y n } and Z = { z , z 1 2 , ..., z n } : we assume that the vertices of U, V, W, X, Y and Z having the same subscripts are the corresponding vertices of the partite sets. Let U 1 = { u , v 1 1 , w 1 , x 1 , y 1 , z 1 } , U 2 = { u , v 2 2 , w 2 , x 2 , y 2 , z 2 } , ..., U n = { u , v n n , w n , x n , y n , z n } be the sets of these vertices having the same subscripts. By the definition of the tensor product, each U i , 1 ≤ i ≤ n is an independent set and the subgraph induced by each U i ∪ U j , 1 ≤ i, j ≤ n and i = j is isomorphic to C 6 × K 2 . Now by Lemma 5.2 the graph C 6 × K 2 admits a 6-cycle decomposition. This completes the proof. /square

Furthermore, we quote the following result on decomposition of the tensor product of graphs into cycles of odd length.

Lemma 5.4. [11] For k ≥ 1 and m ≥ 3 , C 2 k +1 | C 2 k +1 × K m

The next theorem is an extension of Lemma 5.4.

Theorem 5.5. For m ≥ 3 and n ≥ 2 , C m | C m × K n

Proof. We shall split the proof of this lemma into two cases.

Case 1. When m = 2 k +1, k ≥ 1

The proof of this case is immediate from Lemma 5.4.

Case 2. When m = 2 k , k ≥ 2

/negationslash

Following from the definition of tensor product of graphs, let U 1 = { u , u 1 1 2 1 , u 3 1 , ..., u m 1 } , U 2 = { u , u 1 2 2 2 , u 3 2 , ..., u m 2 } , ... , U n = { u , u 1 n 2 n , u 3 n , ..., u m n } form the partite sets of vertices in the product C m × K n . Now, for 1 ≤ i, j ≤ n and i = , the subgraph induced j by U i ∪ U j is isomorphic to K m,m -( m -2) I , where I is a 1-factor of K m,m . But K m,m -( m -2) I admits an m -cycle decomposition. Hence the proof. /square

## 6. Proof of the Main Theorem

Proof of Theorem 1.1. Assume that C 4 | K m × K n , for some m and n with 2 ≤ m,n . Then every vertex of K m × K n has even degree and 4 divides the number of edges of K m × K n . These two conditions translates to ( m -1)( n -1) being even and 8 | mn m ( -1)( n -1) respectively. Hence by the first fact, m or n has to be odd, i.e. has to be congruent to 1 or 3 or 5 (mod 6). The second condition is satisfied precisely when one of the following holds.

- (1) n ≡ 0 (mod 4) and m is odd,
- (2) m ≡ 0 (mod 4) and n is odd, or
- (3) m or n ≡ 1 (mod 4).

Next we proceed to prove the sufficiency in two cases.

Case 1. Since the tensor product is commutative, we may assume that m is odd and so m ≡ 1 or 3 or 5 (mod 6). Suppose that n ≡ 0 (mod 4).

Subcase 1. Let m ≡ 1 or 3 (mod 6)

Now since m ≡ 1 or 3 (mod 6) it implies that by Theorem 2.1 C 3 | K m . Therefore, the graph K m × K n = (( C 3 × K n ) ⊕···⊕ ( C 3 × K n )). But n ≡ 0 (mod 4) therefore by Theorem 3.3 we have that C 4 | C 3 × K n . Hence C 4 | K m × K n .

Subcase 2. Let m ≡ 5(mod 6)

By Lemma 2.3, there exist positive integers p and q such that K m is decomposable into p 3-cycles and q 4-cycles. Hence K m × K n has a decomposition into p copies of C 3 × K n and q copies of C 4 × K n . By Theorem 3.3 C 4 | C 3 × K n and also Lemma 5.1 shows that C 4 | C 4 × K n . Hence C 4 | K m × K n .

Case 2. By commutativity of the tensor product we assume that m ≡ 1 (mod 4). The graph K m × K n = (( K m × K 2 ) ⊕··· ⊕ ( K m × K 2 )). Since m ≡ 1 (mod 4), by Corollary 2.5, C 4 | K m,m -I , and K m × K 2 ∼ = K m,m -I . Hence C 4 | K m × K n . This completes the proof. /square

Proof of Theorem 1.2. Assume that C 6 | K m × K n for some m and n with 2 ≤ m,n . Then every vertex of K m × K n has even degree and 6 divides in the number of edges of K m × K n . These two conditions translate to ( m -1)( n -1) being even and 6 | m m ( -1) n n ( -1) respectively. Hence, by the first fact m or n has to be odd, i.e., has to be congruent to 1 or 3 or 5 (mod 6). The second fact can now be used to show that they cannot both be congruent to 5 (mod 6). It now follows that m ≡ 1 or 3 (mod 6) or n ≡ 1 or 3 (mod 6).

Conversely, let m ≡ 1 or 3 (mod 6). By Theorem 2.1, C 3 | K m and hence K m × K n = (( C 3 × K n ) ⊕··· ⊕ ( C 3 × K n )). Since C 6 | C 3 × K n by Theorem 4.1. Finally, if n ≡ 1 or 3 (mod 6), the above argument can be repeated with the roles of m and n interchanged to show again that C 6 | K m × K n . This completes the proof.

Proof of Theorem 1.3. Assume that C 6 | K m -I × K ,m n ≥ 6. Certainly, 6 | mn m ( -2)( n -1). But we know that if 6 | m m ( -2) then 6 | mn m ( -2)( n -1). But m is even therefore m ≡ 0 or 2 (mod 6).

Conversely, let m ≡ 0 or 2 (mod 6). Notice that for each m , m m ( -2) 2 is a multiple of 3. Thus by Theorem 2.7 C 3 | K m -I and hence K m -I × K n = (( C 3 × K n ) ⊕ · · · ⊕ ( C 3 × K n )). From Theorem 4.1 C 6 | C 3 × K n . The proof is complete.

## 7. CONCLUSION

In view of the results obtained in this paper we draw our conclusion by the following remark and corollary.

Remark 7.1. The product K m × K n can also be viewed as an even regular complete multipartite graph. So by the conditions given in Theorem 1.1 we have that every even regular complete multipartite graph G is C 4 -decomposable if the number of edges of G is divisible by 4 .

Corollary 7.2. For any simple graph G . If

- (1) C 3 | G then C 6 | G × K n , whenever n ≥ 2 .
- (2) C 6 | G then C 6 | G × K n , whenever n ≥ 2 .

Proof. We only need to show that C 3 | G . Applying Theorem 4.1 gives the result. /square

## Comments

The results presented in this work are split in two different papers [1, 15].

## References

- [1] A. D. Akwu and O. Oyewumi, C 6 decomposition of the tensor product of complete graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, In Press.
- [2] B. Alspach and H. Gavlas, Cycle decompositions of K n and K n -I , J. Combin. Theory Ser. B 81 (2001) 7799.
- [3] E.J. Billington, Decomposing complete tripartite graphs into cycles of length 3 and 4, Discrete Math. 197/198 (1999) 123-135.
- [4] E.J. Billington, D.G. Hoffman and B.M. Maenhaut, Group divisible pentagon systems, Util. Math. 55 (1999) 211-219.
- [5] N.J. Cavenagh and E.J. Billington, Decompositions of complete multipartite graphs into cycles of even length, Graphs Combin. 16 (2000) 49-65.
- [6] D. G. Hoffman, C. C. Linder and C. A. Rodger, On the construction of odd cycle systems, J. Graph Theory 13 (1989) 417-426.
- [7] T.P. Kirkman, On a problem in combinations, Cambridge and Dublin Math. J. 2 (1847) 191-204.
- [8] C.C. Lindner and C.A. Rodger, Design Theory (CRC Press New York, 1997).
- [9] J. Ma, L. Pu and H. Shen, Cycle decomposition of K n,n -I , SIAM J. Discrete Math. 20 (2006) 603-609.
- [10] R.S. Manikandan and P. Paulraja, C p -decompositions of some regular graphs, Discrete Math. 306 (2006) 429-451.

- [11] R.S. Manikandan and P. Paulraja, C 5 -decompositions of the tensor product of complete graphs, Australas. J. Combin. 37 (2007) 285-293.
- [12] R.S. Manikandan and P. Paulraja, Hamilton cycle decompositions of the tensor product of complete multipartite graphs, Discrete Math. 308 (2008)3586-3606.
- [13] R.S. Manikandan and P. Paulraja, C 7 -decompositions of the tensor product of complete graphs, Discussiones Mathematicae Graph Theory 37 (2017) 523-535.
- [14] A. Muthusamy and P. Paulraja, Factorizations of product graphs into cycles of uniform length, Graphs Combin. 11 (1995) 69-90.
- [15] O. Oyewumi and A. D. Akwu, C 4 decomposition of the tensor product of complete graphs, Electronic Journal of Graph Theory and Applications, In Press.
- [16] P. Paulraja and S. S. Kumar, Resolvable even cycle decompositions of the tensor product of complete graphs. Discrete Math. 311 (2011) 1841-1850.
- [17] M. ˇ ajna, S Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Designs 10 (2002) 27-78.
- [18] D. Sotteau, Decomposition of K m,n ( K ∗ m,n ) into cycles (circuits) of length 2 k , J. Combinatorial Theory (Series B), 30(1981) 75-81.
- [19] B. R. Smith, Decomposing complete equipartite graphs into cycles of length 2 p , J. Combin. Des. 16 (2006) 244-252.
- [20] B. R. Smith, Complete equipartite 3 p -cycle systems, Australas J. Combin. 45 (2009) 125-138.

Opeyemi Oyewumi

General Studies Department, Air Force Institute of Technology, Kaduna, Nigeria E-mail address : opeyemioluwaoyewumi@gmail.com

Abolape Deborah Akwu

Department of Mathematics, Federal University of Agriculture, Makurdi, Nigeria E-mail address : abolaopeyemi@yahoo.co.uk
Opeyemi Oyewumi Abolape D. Akwu
$C_4$ and $C_6$ decomposition of the tensor product of complete graphs
Let $G$ be a simple and finite graph. A graph is said to be
\textit{decomposed} into subgraphs $H_1$ and $H_2$ which is denoted by $G= H_1
\oplus H_2$, if $G$ is the edge disjoint union of $H_1$ and $H_2$. If $G= H_1
\oplus H_2 \oplus H_3 \oplus \cdots \oplus H_k$, where\ $H_1$,$H_2$,$H_3$, ...,
$H_k$ are all isomorphic to $H$, then $G$ is said to be $H$-decomposable.
Futhermore, if $H$ is a cycle of length $m$ then we say that $G$ is
$C_m$-decomposable and this can be written as $C_m|G$. Where $ G\times H$
denotes the tensor product of graphs $G$ and $H$, in this paper, we prove the
necessary and sufficient conditions for the existence of $C_4$-decomposition
(respectively, $C_6$-decomposition ) of $K_m \times K_n$. Using these
conditions it can be shown that every even regular complete multipartite graph
$G$ is $C_4$-decomposable (respectively, $C_6$-decomposable) if the number of
edges of $G$ is divisible by $4$ (respectively, $6$).