International Journal of Scientific & Engineering Research Volume 2, Issue 10, Oct-2011 1

ISSN 2229-5518

Decomposition of

Cr [ Km ]

into

sunlet graphs

A. D. Akinola

Abstract— In this paper,it has been proved that

Cr [K m ]

(which is the wreath product of cycle and complem ent of

n | rm2

a complet e graph n

can be decompose into sunlet graph n , n = rm if and only if

and m is even.

2000 Mathem atics subject classification: 05B30, 05C70

Keywords: Graph decom position,sunlet graph, wreath product of cycle and complement of a complet e graph.

——————————  ——————————

1 INTRODUCTION

Cycles

Crm . R.Anitha etal [7] worked on

We begin with a few definitions.A graph

Cr [ Km ] is a graph which arises from the

N-sun (sunlet graph) decomposition
of complete ,complete Bipartite and some
cycle Cr
by replacing each vertex x by m
harary graphs . Little attention has
independent vertices and each edge xy by

x' y' , x' y' ',..., x' ym1 ; x' ' y' ,..., x' ' ym

.
been paid to the same problem for the

graph Cr [K m ] . A significant and useful result is that of Sotteau [8] who discover

,..., x m y' ,..., x m ym

A graph G with q edges is said to be decomposable into graph H if it can
be written as the union of edge-disjoint copies of H so that every edge in G belongs to one and only one copy of H . Although much work has gone into decomposition of complete graphs into

k cycles(See [4] for good survey).Alspach

and Gavlas [1] have shown the necessary and sufficient condition for Cm to decompose the complete graph Kn
when m and n are either both odd and
even.M. Sajna [2] have shown that for the case when m and n are of opposite parity.N.J. Cavenagh and etal [3] have worked on decomposition of complete
multipartite graphs into cycles of even
necessary and sufficient conditions for the decomposition of complete bipartite graphs into k cycles.

2 DEFINITIONS AND TERMINOLOGY

2.1 Definition

Sunlet graph Lr is a graph with cycle Cr

whereby each vertex of the cycle is attached to one pendant vertex .Each sunlet graph contains r vertices with r edges.

2.2 Definition

We will define a function on the vertices of a graph G = Cr [K m ] as
length.D. Froncek etal worked on

c : V (G)  xN  N

i.e for every vertex

decomposition of complete graph into blownup cycles Cr [ [K2 ] . R. Haggkvist [5] gave lemma on cycle decomposition. N.J.

Cavenagh [10] have shown that the graph

x  G , c( x)  xij where i, j  N .

2.3 Definition

All graphs in this paper are simple .We

Cr [ Km ]

can be decompose into cycle
use Km

to denote the complete graph

Cr . R. Laskar [11] has proved that the

on m vertices. Km
denote the

graph Cr [ Km ]

can be decompose into
complement of K m . An r-cycle is a cycle

International Journal of Scientific & Engineering Research Volume 2, Issue 10, Oct-2011 2

ISSN 2229-5518

of length r and is denoted by Cr . Let

 ( x'i )

and  ( x''i )

represent pendant

Cr [ Km ]

stand for a cycle in which every
vertices.Attached each pendant vertices

vertex is replaced by m isolated vertices

 ( x'i )

to each vertex x'i
in C 'r
and

and every edge by Km, m

and Cr [K m ]

 ( x' 'i )

to each vertex x''i in C ''r
, C ''r
contains vertex xij

; i = 1,…, r and j =

with pendant vertices  ( x'i ) , ( x' 'i )

attached respectively gives 2 sunlet graphs
0,…,m-1. Let Ln

be a sunlet graph with n
vertices and n edges.
with 2r vertices.Hence Cr [K 2 ]
can be

2.4 Definition

Let G be a graph without loops and
decompose into 2 sunlet graphs with 2r
vertices

L  (H1 , H 2 ,..., H m )

a list of graphs.The

3.2 Lemma

Let r,m be positive even integers such that
list L is proper if G has a subgraph
isomorphic with H i , i = 1, 2,…,m

n = rm then Cr [ Km ]

can be decompose

and |E (G)|= | E (H i ) |

i 1

where E(G)
into m sunlet graph Lr .

Proof:

denotes the edge set of G .The
list L is said to pack G if G is the edge-

First observe that Cr [ K 2 ]

can be
disjoint union of the graphs
decompose into 2 sunlet graphs with 2r

vertices.Then set m = 2t and decompose

G1 , G2 ,...,Gm (G  G1  G2  ...  Gm )

C [K ]

into t 2 cycles C .Denote vertices
where Gi is isomorphic with H i
for

r t r

i = 1,2,…,m .An even list where each entry

in i - th part of Cr [Kt ]
by xij
for j = 0,
occurs an even number of times. The
,…,t- 1 and create t cycles
graph G is said to have an M-

xij x2 j x3 j ...xr 1 j xrj

for j = 0,1,…, t-1. Next
decomposition if the proper list
(M,M,…,M) packs G,that is M|G.
combine these cycles into one cycle Crt

by replacing each edge x1 j x2 j

with

3. DECOMPOSITION OF Cr [ Km ]

INTO EDGEDISJOINT SUNLET

x1 j x2 j 1 .Now apply mappings s

0, 1,…, t- 1 defined as follows:
for s =

GRAPHS

3.1 Lemma

s ( xij )  xij

s ( xij )  xij  s

for i odd and
for i even. This is the

The graph Cr [K 2 ]

can be decompose
desired decomposition into cycles
into 2 sunlet graphs with 2r vertices.

Proof.

Crt .Now take each cycle

Crt ,make it back into Crt [ K 2 ]

and

From the definition of the graph Cr [ K2 ]

(denoted by Cr [2] ), each vertex x

decompose Crt [K 2 ]

into 2 sunlet graphs

L2 rt  Lrm  Ln .Hence Ln

decomposes
in Cr

is replaced by a pair of two

Cr [K m ]

for r,m even and n = rm.

independent vertices x', x' '

and each

Each graph Crt [ K 2 ]

gives 2 sunlet
edge xy is replaced by four edges

x' y', x' y' ', x' ' y', x'' y'' First form 2

graphs Ln and we have t graph Crt [K 2 ]
cycles C'r
and C' 'r
with vertex set x'i
which implies that we have 2t = m sunlet

graphs Ln .Hence Cr [K m ] decomposes

and x' 'i ] respectively, i = 1,…, r. Define a
into m sunlet graphs Ln .

mapping Á by  ( x'i )  x''i 1

and

 ( x''i )  x'i 1 , i is calculated modulo r.

3.3 Lemma

International Journal of Scientific & Engineering Research Volume 2, Issue 10, Oct-2011 3

ISSN 2229-5518

If r is a positive odd integers and m a positive even integers such that n =
rm,then sunlet graph Ln .decomposes
follows:

s ( xij )  xij

for i odd and

s ( xij )  xi  j  s

for i even and i = r.m

Cr [ Km ] .

Proof:

We have r- 1 even since r is odd.Set m = 2t.

Now take each Crt ,make it into Crt [ K 2 ]

and decompose it into two sunlet
First create k cycles Cr 1 in Cr 1[K m ] as
Graphs L2 rt

= Lrm  Ln Hence sunlet

in lemma (2).Then take complete tripartite
graph Ln

decompose Cr [K m ]

for r odd.

graph Kt ,t ,t

with partite sets X i  {xij}

Therefore for m 2 , r

odd, Cr [ Km ]

can
for i = 1, r – 1, r and j = 0, 1,…, t- 1 and
decompose it into triangles using well
known construction via latin square.i.e
be decomposes into m sunlet graph Ln .

Construct t  t

latin square and consider

3.4 Lemma

each element in the form (a ,b, c) where a
If sunlet graph Ln

decomposes Cr [ Km ] ,

denotes the row,b denotes the column and

c denotes the entry with

0  a, b, c  t  1 .Each cycle is of the

n = rm, then m is even.

Proof:

Each vertex in Cr [Km ]

has degree 2m.
form (1, a) , (r- 1, b) , (r, c)

For L to decompose C [K ]

with

n r m

Then for every triangle x1a xr 1b xrc

n = rm,3w+p must be equal to 2m where w,

replace the edge x1a xr 1b

in an

p represent the number of times

appropriate Cr 1

by the edges xr 1b xrc

the vertex xij

in Cr [K m ]

appears in the

and xrc x1a

to obtain cycle Cr :

decomposition with degree 3 and 1 respectively and w + p = m .Suppose m is

Therefore we have Cr | Cr [Kt ] .

odd,let there exist a vertex xij

in Cr [Km ]

Case 1 :Suppose

is even.

such that it exist in each sunlet graph Ln
Join 2 cycles Cr
into one cycle to give

that decomposes Cr [K m ] .The sum of its

C2 r : i.e

degree in all the sunlet graphs Ln
is 3w+p.

xij x2 j x3 j ...xr 1 j xrj xij1x2 j 1...xrj  2 ,

In all the cases for the values of w and p,

j  0,1,...,t  2

3w+p 6= 2m.which implies that Ln
does
Now apply mapping s
for s = 0, 1,…,

not decomposes Cr [K m ]

for m odd but

t- 1 defined as follows:

for all m even,3w + p = 2m.The result also

s ( xij )  xij

for i odd and s ( xij )  xij  s

follows from [8] for r > 2.Hence the result.
for i even and i = r.
This is the desired decomposition into

cycles C2 r .Now take each C2 r , make

3.5 Theorem

If G = Cr [ Km ]
can be decompose into

it into C2r [K2 ] . and decompose it into

cycle Cr
then G(2) can be decompose
two sunlet graphs L4 r . .

into 2m2 sunlet graphs with 2r vertices.

Proof:

Case 2: Suppose

, is odd

From the previous observation all we need

2 to show is that Cr [2]

decomposes
Join the cycles Cr by replacing each edge

into 2 copies of sunlet graphs with 2r

x1 j x2 j with x1 j x2 j 1 . in order to

vertices.By Lemma (3.1) , Cr [K2 ]

can
create t cycles Crt .Then apply mapping
be decompose into 2 sunlet graphs with 2r

s for s = 0, 1,…t - 1 defined as
vertices.Hence we have 2m sunlet

International Journal of Scientific & Engineering Research Volume 2, Issue 10, Oct-2011 4

ISSN 2229-5518

graph L2r
since we have m cycles Cr

r  m

< 2r with

from the cycle decomposition of Cr [ Km ]

m(m  2)  0(mod r)

r [ m ]

,then C K
can
be decomposed into sunlet graph Ln of
3.6 Lemma
length n for all m  r
with

Necessary conditions for Ln to

m(m  2)  0(mod r) .

decompose Cr [ Km ]

whenever n = rm are:

Proof:

(a) m must be positive even integers.

Suppose that Cr [K m ]

can be
(b) r  3

(c) The number of edges n divides the
decomposed into sunlet graphs Ln

whenever m(m  2)  0(mod r) and

number of edges in Cr [ Km ] .

r  m

< 2r.Let m and r be positive even

Proof:

(a) The result follows from lemma (3.4)
that m must be positive integers.
integers such that
m(m  2)  0(mod r) .Let m = pr + t for
integers p with 0 < t < r .Observe that
(b) It follows from lemma (3.2) and (3.3).

m(m  2)  0(mod r)

implies that m or
(c) It follows from the fact that the number
m  2 is a multiple of r. If m = pr+t then t
of edges n of Ln
has to be a
is either 0 or 2 .Since r is even, then
multiple of m since the total number of

r(r  2)  0(modt ) as well .Partition the

edges in Cr [Km ]

is rm .Thus for such

edge set of Cr [K m ]

into m sets such that
decomposition to exist, we have that n|rm.
each set induces a subgraph isomorphic to

3.7 Theorem

Let m, n be positive even integers and
sunlet graph Ln

in such a way that

r  3 , n = rm,if Ln

decomposes Cr [ Km ]

vertices will have degree 3 and

then the 2 sunlet graphs such that each
vertex appears once with degree 3 and
vertices have degree 1.If there exist a vertex xij such that the degree of the
1 in each sunlet graph Ln
respectively is a
4 regular graph which can be decompose
vertex xij
is either 3 or 1.i.e for Ln to
into 2 hamiltonian cycles.

Proof:

Suppose the sunlet graph Ln
decomposes
decompose

Cr [K m ] ,  deg(xij )  2m, xij  V ( Ln )

i 1

which follows from lemma (3.2).We

Cr [ Km ] ,let m = 2t.Then by lemma (3.1)

now use induction on p.It is true from

and lemma (3.2) and [8]; Crt| Cr [Kt ] .Let
lemma (3.2) that Ln

decomposes Cr [ Km ]

G = Cr [Kt ] . then by theorem (3.4) G(2)
can be decompose into sunlet graphs with
for p = 1.Suppose p > 1,assume that it is
true for p = k.Suppose p = k+1,then

m = (k + 1) r + t.

2rt = rm vertices.The
join of these 2 sunlet graphs gives 4
regular graphs which can be decompose

,  deg(xij ) 

3((k  1)r  t )

 (k  1)r  t

2 ,

into 2 hamilton cycles which follows from the result of Bermond etal [9].
3.8 Theorem

Let r, m, n be positive even integers satisfying 3 < r · m. If Cr [ Km ] , can be decomposed into sunlet graph Ln of
length n = rm for all m in the range

i 1  2((k  1)r  t )  2m

It is true for p = k+ 1,therefore it is true for all integer p. Therefore Ln

decomposes Cr [Km ]

for all m > r.Hence the result.
4 Main result

International Journal of Scientific & Engineering Research Volume 2, Issue 10, Oct-2011 5

ISSN 2229-5518

4.1 Theorem

Let Cr [Km ]  G

with rm2
Let G = Cr [K m ]
with rm
edges, r ,m even .Let H be a collection of m
edges r, m even, n = rm ,let H be a collection of m disjoint sunlet graphs on 2n vertices .Then G(2)  L'2n  L' '2n

where L'2 n  L''2n  H .

disjoint sunlet graphs Ln , n = rm. Then

G(2)  G1  G 2  G 3  G 4

where

G1  G 2  G 3  G 4  H .

Therefore

Proof:

H | G(2) .

Therefore H | G (2)

First show that G(2)  L'2n L' '2n . From

Proof:

Assume that H consists of disjoint sunlet
lemma (3.2), Ln

decomposes Cr [ Km ]

into m sunlet graph with n vertices.i.e

graphs Ln with lengths n1 , n2 ,..., nnm

k 1

Lni decomposes Cr [Km ]  G .Next

Where m rm2  nm . Let G consist of

show that Ln 2 k decomposes G(2).It is
sufficient to show that Lnk (2)

k 1

set of vertices xij , i  1,..., r

can be decompose into 2 copies of Ln 2 k

And

j  0,1,..., m  1

with rm 2
edges and G(2) be a graph with

, k = 1,...,m. First form 2 cycles C'nk

4rm 2

edges and 2rm
vertices.Let
and C ' 'nk
with vertex set x'ij

G1 , G 2 , G 3 , G 4

be the subgraph of G(2)
and x' 'ij .Define a mapping f by
with equal number of vertices and edges

f ( x'ij )  y'ij and

f ( x' 'ij )  y' 'ij

i.e

G1 contains the set of vertices {x' }

where

y'ij , y' 'ij represent the pendant ij

vertices of Lnk (2) .Attached each pendant

with edge set {x'ij x'i 1 j } .

G 2 contains the set of vertices {x' ' }

vertices

f ( x'ij ), f ( x' 'ij ) to each vertex ij

x'ij , x' 'ij

in C'nk , C' 'nk

respectively.

with edge set {x' 'ij x''i 1 j }.

C 'nk , C ' 'nk

with pendant vertices

G contains the set of vertices

f ( x'ij ), f ( x' 'ij )

{x'ij , x' 'i 1 j } with edge set {x'ij x''i 1 j } 2

attached respectively gives 2 sunlet graphs L'2 nk , L''2nk . Therefore Lnk (2) can be decompose into 2 sunlet graph L'2 nk , L''2nk .i.e

Lnk (2)  L'2 nk L' '2nk .Therefore

G 4 contains the set of

vertices {x' 'ij , x'i 1 j } with edge set

{x' 'ij x'i 1 j }

Since each G a , a  1,2,3,4

consists of rm edges then G a
partition G(2) that is

G(2)  Lnk (2) 

k 1 .

G(2)  G1

 G 2

 G 3

 G 4 .

m m Each G a

has sunlet graph decomposition

 L'2nk  L''2 nk  L'2 n  L' '2n

which follows from lemma (3.2).Then

k 1

Where

k 1

a a

G  L nk m

k 1

L2 n  L2nk .Hence H | G(2) since

k 1

L'2n  L' '2 n  H .

4.2. Theorem

Therefore G a  H

Hence

H | G (2) .

4.3 Corollary

International Journal of Scientific & Engineering Research Volume 2, Issue 10, Oct-2011 6

ISSN 2229-5518

Let Cr [Km ]  G

be a graph with sunlet

graphs L1n ,..., Ll n , from L [ K ] , as

graph decomposition (that is a decomposition into edge-disjoint sunlet graphs).Then any proper even list of sunlet graphs Ln , n = rm packs G(2). Proof:

n l

follows:

Form the cycle Cn from l  l , latin

square as

(1, u)(2, v)(3, u)...( m  1, v)( n , ) ,

A sunlet graph in G(2) is a cycle together 2 2
with pendant vertices attached
to each vertex of the cycle.Assume that
where u is the row ,v is the column and 
is the entry in the latin square. Next
join each vertex of the cycle to pendant

  (Ln1 , Ln1, Ln1 , Ln1, Ln 2 , Ln 2 , Ln 2 , Ln 2 , Lnm , Lnm , Lnvme,rLtincme,s)

xij

for l  
in order to get
is a proper even list of sunlet graphs on n
vertices.Where n is the order of G.
sunlet graph Ln .Therefore

L [K ]  L 1  ...  Ll n .Hence sunlet

n l n

Ln1  Ln 2  ...  Lnm be a sunlet graph

graph L decomposes C [K

] for any

decomposition of G.

Let Lnk  Ln , k  1,..., m .By theorem

(4.2),

positive integer l .

4.5 Corollary

r ml

L (2) 

La nk , a  1,2,3,4 i.e

Let G  Cr [ K m ]

be a graph with sunlet

k 1

graph decomposition then any even

Lnk (2)  L nk  L nk  L nk  L nk

list of sunlet graph Ln

packs G(l ) for

1 2 3 4

where L1nk  L2 nk  L3nk  L4 nk Whence

G(2)  Ln1 (2)  L n 2 (2)  ...  Lnm (2)

 L1n1  L2 n1  L3n1  L4 n1  L1n 2  L2 n 2  L3n 2

 L4 n 2  ...  L1nm  L2 nm  L3nm  L4 nm

any positive integer l.

Proof:

Assume that Cr [K m ] decomposes into m

sunlet graph Ln , from theorem (4.4)

Ln (l )

decomposes into l sunlet graph
Therefore proper even list of sunlet graphs packs G(2) .Hence the result .

4.4 Theorem
Ln for any positive integer l.

Cr [K ml ]

 Ln1 (l )  Ln 2 (l )  ...  Lnm (l )

If the graph Cr [K m ]

decomposes into

1  ...  L l 2

 ...  L 1

 ...  Ll 2

sunlet graph Ln , n = rm, r,m even,

then the graph Cr [K ml ] decomposes into sunlet graphs Ln for any positive

Which is an even list of Ln .Hence any proper even list of sunlet graph Ln
integer l .

Proof:

From the previous observation Ln

packs G(l )

4.6 Theorem
for any positive integer l .

decompose Cr [K m ] , n = rm, r,m even.

If the graph Cr [K m ]

decomposes into

Next show that Ln [ Kl ] , can be

sunlet graph Ln , n = rm , m even,

ndecompose into l 2 , copies of L .

then the graph Cr [ K ml ]

decomposes into
Label the vert ices of

Ln [K l ] , as

sunlet graph Lnl

Proof:

for any positive integer l.

x a ij ,1  a  l ,Then form the sunlet

Suppose Cr [K m ]

decomposes into m
sunlet graphs Ln
which follows from

International Journal of Scientific & Engineering Research Volume 2, Issue 10, Oct-2011 7

ISSN 2229-5518

lemma (3.2)and (3.3).It is sufficient to

4.8 Theorem

show that Ln (l )

can be decompose

The graph Cr [K m ]

can be decompose
into sunlet graph Lnl
where Lnl
is a
into sunlet graph Ln , if and only if n
sunlet graph on nl vertices.Next form

divides rm2 , n  rm

and m is even.
sunlet graph Lnl

from Ln (l ) .The cycle in

Proof:

Ln give rise to Cn [Kl ] in Ln (l ) .

The necessary condition follows from lemma (3.6) that is the number of edges

Cn [Kl ]

can be decompose into l cycles

in Cr [ Km ]

is rm ,so n must divides

2 rm 2

for a decomposition to occur.If

Cnl

by lemma (3.2),(3.3).Then join

n > rm,a vertex must be repeated within each sunlet graph which is impossible.

each vertex in each l cycles Cnl

to the
If n < rm,then there is a vertex which does
not appear in the sunlet graph which is
pendant vertices xl ij to get l sunlet
also impossible for such decomposition to occur.So n = rm.
graphs

Lnl

i.e

To show that if n | rm2

then Ln

Ln (l )  Lnl1  Lnl 2  Lnll

decomposes Cr [K m ] , it is sufficient to

Hence Lnl

decomposes Cr [K ml ]

for any

show that if r | n

n | rm2 .

and m | n

then
positive integer l.
Case 1: r divides n
4.7 Corollary

Write n  rq 2t

where t, q is a positive

Let G  Cr [ K m ]

be a graph with sunlet
integer and from lemma (3.6),
graph decomposition,then any proper

rq 2t | rm2 ,so qt | m ,and we can write

even list of sunlet graph Lnl
for any positive integer l .

packs G(l )

m  qq't .Also rq 2t  rqq't ,so

q  q' .Next consider C [K ] , the degree

r t

Proof:

Assume that proper list of sunlet

  (L nl1 , L nl1,..., L nl1 , L nl 2 ,

of each vertex is 2t which is even.Each vertex appears t times in the sunlet graph

Lrt

1 2 l 1

graphs

l 1 l

decomposition which follows from

lemma (3.2) and lemma (3.3).By theorem

..., L nl 2 ,..., L nlm ,..., L nlm

(4.4),the graph Cr [K

qq 't ]

can be
is the proper list of sunlet graphs Lnl .Let
decompose into sunlet graph

Lrt .Applying theorem (4.6),we have that

Ln1  Ln 2  ...  Lnm

decomposition of G.i.e
be a sunlet graph

Cr [K

qq 't ]

decomposes into sunlet graph

L  L 2

for q  q' .Hence if r

Lnk  Ln , k  1,2,..., m . By theorem (4.6),

rqq 't

rq t

1 2 l

Lnk (l )  L nlk  L nlk  ...  L nlk .

L nlk  L nlk  ...  L nlk

divides n then Cr [K m ]
decomposition.
has sunlet graph

1 2 l

Whence
Case 2: m divides n

Write n  mt'

for any positive integer

G(l )  Ln1 (l )  Ln 2 (l )  ...  Lnm (l )

t ' 3

and m  qq'

1 2 l 1

 (L nl1  L nl1  ...  L nl1  L nl 2 

Ther
Case 2a: Suppose m  2(mod 4)
and let

l 1 l

...  L nl 2  ...  L nlm  ...  L nlm

q = 2,then q'  1(mod q) .By lemma (3.1)

efore any even list of sunlet graphs Lnl

packs G(l ) .

Ct '[Kqq '

] decomposes into sunlet graph

Lt ' q

and by theorem (4.6), Ct '[Kqq ' ]

International Journal of Scientific & Engineering Research Volume 2, Issue 10, Oct-2011 8

ISSN 2229-5518

decomposes into sunlet graph

Lt 'qq '  Lt 'm .Hence sunlet graph Ln

decomposes Cr [ Km ] for r  t ' .

Case 2b: Suppose m  0(mod 4) .Let q =
[6] D. Froncek, P. Kovar, M. Kubesa, Decomposition of complete graphs into blown-up cycles Cm[2]; Discrete Mathematics 310 (2010),1003-1015.
[7] R. Anitha, R.S. Lekshmi, N-sun
decomposition of complete,complete
2,then

q'  0(mod q) . Ct '[ Kqq' ]

bipartite
and some harary graphs; Int. J. of

decomposes into sunlet graph Lt 'q by

Computational and Mathematical

lemma (3.1),also Ct '[Kqq ' ]

decomposes
sciences 2 Winter (2008).
[8] D. Sotteau; Decomposition of Km;n

into sunlet graph Lt ' qq '  Lt ' m

by theorem
³K¤ m;n into cycles (circuit) of length

(4.6).Hence sunlet graph Ln
decomposes
2k, Journal of Comb. Theory,Series B

Cr [ Km ] for r  t ' . Since sunlet graph

Lrqq' , decomposes Cr [Kqq ' ] for both q' = positive odd integer and q' =positive even integer,therefore it is true for all positive

integer q' .Hence if m divides n then

Cr [ Km ] has sunlet graph decomposition. Since q = 2 all through for m  qq' ,it follows that for sunlet graph Ln to

decompose Cr [ Km ] ,m must be an even integer which also follows from lemma (3.4) .

References

[1] B. Alspach, H. Gavlas, Cyle decomposition of Kn and Kn ¡ I,J. Combin. Theory Ser.B,81 (2001), 77-99.
[2] M. Sajna, Cycle decomposition of Kn
and Kn ¡ I ,Ph.D Thesis,Simon
Fraser University 1999.
[3] N.J. Cavenagh, E.J. Billington, Decomposition of complete multipartite graphs into cycles of even length;Graphs and Combinatorics (2000) 16,
49-65.
[4] C.C. Linder, C.A. Rodger, Decomposition into cycles II; Cycle systems
in contemporary design theory: a collectuin of surveys, J.H. Dinitz and D.R. Stinson (Editors), Wiley,New York,
1992, 325-369.
[5] R. Haggkvist, A lemma on cycle decompositions; Annals of Discrete Mathematics 27 (1985), 227-232.
30,(1981),75-81.
[9] J.C. Bermond, O. Favaron, M. Maheo, Hamilton decomposition of cayley
graphs of degree 4;J. Comb. Theory Ser. B
46,(1989),142-153.
[10] N.J. Cavenagh, Decomposition of complete tripartite graphs into k cycles; Australasian J. of Combinatorics 18 (1998)
193-200.
[11] R. Laskar, Decomposition of some composite graphs into hamilton cycles, Pro. 5th Hungarian coll. keszthely 1976, North Holland, 1978, 705-
716.
A. D. Akinola
Department of Mathematics, College of Natural Science, University of Agriculture, Abeokuta,Ogun State, Nigeria. email:abolaopeyemi@yahoo.co.uk