# Sunlet Decomposition of Certain Equipartite Graphs

Authors: Abolape D. Akwu; Deborah O. A. Ajayi
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

LetL2n stand for the sunlet graph which is a graph that consists of a cycle and an edge terminating in a vertex of degree one attached to each vertex of cycle Cn. The necessary condition for the equipartite graph Kn+I*K̅m to be decomposed into L2n for n≥2 is that the order of L2n must divide n2m2/2, the order of Kn+I*K̅m. In this work, we show that this condition is sufficient for the decomposition. The proofs are constructive using graph theory techniques.


---

## Body

## 1. Introduction

LetCr,  Kn,  K-m denote cycle of length r, complete graph on n vertices, and complement of complete graph on m vertices. For n even, Kn+I denotes the multigraph obtained by adding the edges of a 1-factor to Kn, thus duplicating n/2 edges. The total number of edges in Kn+I is n2/2. The lexicographic product, G*H, of graphs G and H, is the graph obtained by replacing every vertex of G by a copy of H and every edge of G by the complete bipartite graph K|H|,|H|.For a graphH, an H-decomposition of a graph G, H∣G, is a set of subgraphs of G, each isomorphic to H, whose edge set partitions the edge set of G. Note that for any graph G and H and any positive integer m, if H∣G then (H*K-m)∣(G*K-m).LetG be a graph of order n and H any graph. The corona (crown) of G with H, denoted by G⊙H, is the graph obtained by taking one copy of G and n copies of H and joining the ith vertex of G with an edge to every vertex in the ith copy of H. A special corona graph is Cn⊙K1, that is, a cycle with pendant points which has 2n vertices. This is called sunlet graph and denoted by Lq, q=2n.Obvious necessary condition for the existence of ak-cycle decomposition of a simple connected graph G is that G has at least k vertices (or trivially, just one vertex), the degree of every vertex in G is even, and the total number of edges in G is a multiple of the cycle length k. These conditions have been shown to be sufficient in the case that G is the complete graph Kn, the complete graph minus a 1-factor Kn-I [1, 2], and the complete graph plus a 1-factor Kn+I [3].The study of cycle decomposition ofKn*K-m was initiated by Hoffman et al. [4]. The necessary and sufficient conditions for the existence of a Cp-decomposition of Kn*K-m, where p≥5 (p is prime) that (i) m(n-1) is even and (ii) p divides n(n-1)m2, were obtained by Manikandan and Paulraja [5, 6]. Similarly, when p≥3 is a prime, the necessary and sufficient conditions for the existence of a C2p-decomposition of Kn*K-m were given by Smith [7]. For a prime number p≥3, Smith [8] showed that C3p-decomposition of Kn*K-m exists if the obvious necessary conditions are satisfied. In [9], Anitha and Lekshmi proved that the complete graph Kn and the complete bipartite graph Kn,n for n even have decompositions into sunlet graph Ln. Similarly, in [10], it was shown that the complete equipartite graph Kn*K-m has a decomposition into sunlet graph of length 2p, for a prime p.We extend these results by considering the decomposition ofKn+I*K-m into sunlet graphs and prove the following result.Letm≥2, n>2, and q≥6 be even integers. The graph Kn+I*K-m can be decomposed into sunlet graph of length q if and only if q divides n2m2/2, the number of edges in Kn+I*K-m.


## 2. Proof of the Result

To prove the result, we need the following.Lemma 1 (see [10]).
Forr≥3, L2r decomposes Cr*K-2.Lemma 2.
For any integerr>2 and a positive even integer m, the graph Cr*K-m has a decomposition into sunlet graph Lq, for q=rm.Proof
Case  1 (r is even). First observe that Cr*K-2 can be decomposed into 2 sunlet graphs with 2r vertices. Now, set m=2t and decompose Cr*K-t into cycles Crt. To decompose Cr*K-t into t-cycles Crt, denote vertices in ith part of Cr*K-t by xi,j for j=1,…,t, i=1,2,…,r and create t base cycles x1,jx2,jx3,j⋯xr-1,jxr,j. Next, combine these base cycles into one cycle Crt by replacing each edge x1,jx2,j with x1,jx2,j+1. To create the remaining cycles Crt, we apply mappings ϕs for s=0,1,…,t-1 defined on the vertices as follows.
Subcase  1.1 (i odd). Consider
(1)ϕs(xi,j)=xi,j.
This is the desired decomposition into cycles Crt.
Subcase  1.2 (i even). Consider
(2)ϕs(xi,j)=xi,j+s.
This is the desired decomposition into cycles Crt.
Now take each cycleCrt, and make it back into Crt*K-2. Each Crt*K-2 decomposes into 2 sunlet graphs L2rt (by Lemma 1), and we have Cr*K-m decomposing into sunlet graphs with length rm for r even. Note that
(3)Cr*K-2t=(Cr*K-t)*K-2.Case  2 (r is odd)
Subcase 2.1 (m≡2(mod4)). Set m=2t. First create t cycles C(r-1)t in Cr-1*K-t as in Case 1. Then, take complete tripartite graph Kt,t,t with partite sets Xi={xi,j} for i=1,r-1,r and j=1,…,t and decompose it into triangles using well-known construction via Latin square, that is, construct t×t Latin square and consider each element in the form (a,b,c) where a denotes the row, b denotes the column, and c denotes the entry with 1≤a,b,c≤t. Each cycle is of the form x(1,a),  x(r-1,b),  x(r,c). Then, for every triangle x1,axr-1,bxr,c, replace the edge x1,axr-1,b in each C(r-1)t, by the edges xr-1,bxr,c and xr,cx1,a to obtain cycles Crt. Therefore, Crt∣Cr*K-t. Now take each cycle Crt, make it into Crt*K-2, and by Lemma 1, Crt*K-2 has a decomposition into sunlet graphs L2rt=Lq.
Subcase 2.2 (m≡0(mod4)). Set m=2t. The graph Cr*K-t decomposes into Hamilton cycle Crt by [11]. Next, make each cycle Crt into Crt*K-2. Each graph Crt*K-2 decomposes into sunlet graph L2rt by Lemma 1.Theorem 3.
Letr,  m be positive integers satisfying r,m≡0(mod4), then Lr decomposes Cr*K-m.Proof.
Let the partite sets (layers) of ther-partite graph Cr*K-m be U1,U2,…,Ur. Set m=2t. Obtain a new graph from Cr*K-m as follows.
Identify the subsets of vertices{xi,j}, for 1≤i≤r and 1≤j≤m/2 into new vertices xi1, and identify the subset of vertices {xi,j} for 1≤i≤r and m/2+1≤j≤m into new vertices xi2 and two of these vertices xik, where k=1,2, are adjacent if and only if the corresponding subsets of vertices in Cr*K-m induce Kt,t. The resulting graph is isomorphic to Cr*K-2. Next, decompose Cr*K-2 into cycles Cr/2 as follows: xk,1xk+1,1,…,xd,1xd-1,2,…,xk+1,2,xk,1(4)k=1,r4+1,r2+1,3r4+1,…,r-r4+1,d=r4+k,
where k,  d are calculated modulo r.
To construct the remaining cycles, apply mappingϕ defined on the vertices.
Subcase 1.1 (i odd in each cycle). Consider
(5)ϕ(xi,j)=xi,j+1.
This is the desired decomposition of Cr*K-2 into cycles Cr/2.
Subcase 1.2 (i even in each cycle). Consider
(6)ϕ(xi,j)=xi,j.
This is the desired decomposition of Cr*K-2 into cycles Cr/2.
By lifting back these cyclesCr/2 of Cr*K-2 to Cr*K-2t, we get edge-disjoint subgraphs isomorphic to Cr/2*K-t. Obtain a new graph again from Cr/2*K-t as follows.
For eachj,1≤j≤t/2, identify the subsets of vertices {xi,2j-1,xi,2j}, where 1≤i≤r/2 into new vertices xij, and two of these vertices xij are adjacent if and only if the corresponding subsets of vertices in Cr/2*K-t induce K2,2. The resulting graph is isomorphic to Cr/2*K-t/2. Then, decompose Cr/2*K-t/2 into cycles Cr/2. Each Cr/2*K-t/2 decomposes into cycles Cr/2 by [12]. By lifting back these cycles Cr/2 of Cr/2*K-t/2 to Cr/2*K-t, we get edge-disjoint subgraph isomorphic to Cr/2*K-2. Finally, each Cr/2*K-2 decomposes into two sunlet graphs Lr (by Lemma 1), and we have Cr*K-m decomposing into sunlet graphs Lr as required.Theorem 4 (see [12]).
The cycleCm decomposes Ck*K-m for every even m>3.Theorem 5 (see [12]).
Ifm and k≥3 are odd integers, then Cm decomposes Ck*K-m.Theorem 6.
The sunlet graphLm decomposes Cr*K-m if and only if either one of the following conditions is satisfied.  (1)
ris a positive odd integer, and m is a positive even integer.(2)
r,  m are positive even integers with m≡0(mod4).Proof.
(1) Setm=2t, where t is a positive integer. Let the partite sets (layers) of the r-partite graph Cr*K-m be U1,U2,…,Ur. For each j, where 1≤j≤t, identify the subsets of vertices {xi,2j-1,xi,2j}, for 1≤i≤r into new vertices xij, and two of these vertices xij are adjacent if and only if the corresponding subsets of vertices in Cr*K-m induce K2,2. The resulting graph is isomorphic to Cr*K-t. Then, decompose Cr*K-t into cycles Ct, where t is a positive integer.
Now,Ct∣Cr*K-t by Theorems 4 and 5.
By lifting back theset-cycles of Cr*K-t to Cr*K-2t, we get edge-disjoint subgraphs isomorphic to Ct*K-2. Each copy of Ct*K-2 decomposes into sunlet graphs of length 2t (by Lemma 1), and we have Cr*K-m decomposing into sunlet graphs of length m as required.
(2) Setm=2t, where t is an even integer since m≡0(mod4).
Obtain a new graphCr*K-t from the graph Cr*K-m as in Case 1. By Theorem 4, Ct∣Cr*K-t. By lifting back these t-cycles of Cr*K-t to Cr*K-2t, we get edge-disjoint subgraphs isomorphic to Ct*K-2. Each copy of Ct*K-2 decomposes into sunlet graph of length 2t (by Lemma 1). Therefore, Lm∣Cr*K-m as required.Remark 7.
In [10], it was shown that
(7)L2r*K-lcanbedecomposedintol2copiesofL2r.
This, coupled with Lemma 1, gives the following.Theorem 8 (see [10]).
The graphCr*K-2l decomposes into sunlet graphs L2r for any positive integer l.Lemma 9 (see [3]).
Letn≥4 be an even integer. Then, Kn+I is Cn-decomposable.Lemma 10 (see [3]).
Letm and n be integers with m odd, n≡2(mod4),  3≤m≤n<2m, and n2≡0(mod2m). Then, Kn+I is Cm-decomposable.Lemma 11 (see [3]).
Letm and n be integers with m odd, n≡0(mod4),  3≤m≤n<2m, and n2≡0(mod2m). Then, Kn+I is Cm-decomposable.We can now prove the major result.Theorem 12.
For any even integersm≥2,  n>2, and q≥6, the sunlet graph Lq decomposes Kn+I*K-m if and only if n2m2/2≡0(modq).Proof.
The necessity of the condition is obvious, and so we need only to prove its sufficiency. We split the problem into the following two cases.
Case  1 (q∣n)
Subcase 1.1 (n>q). Cycle Cn decomposes Kn+I by Lemma 9, and we have
(8)Cn*K-m∣Kn+I*K-m.
Each graph Cn*K-m decomposes into sunlet graph Lq, where q=nm by Lemma 2, and we have Kn+I*K-m decomposing into sunlet graph Lq, where q>n.
Subcase 1.2 (q=n). First, consider n≡0(mod4).
CycleCq decomposes Kq+I by Lemma 9, and we have
(9)Cq*K-m∣Kq+I*K-m.
Now, sunlet graph Lq∣(Cq*K-m) by Theorem 3, and hence sunlet graph Lq decomposes Kn+I*K-m.
Also, considern≡2(mod4).
Supposem=2t. Cycle Cq/2 decomposes Kq+I by Lemma 10, and we have
(10)Cq/2*K-2t∣Kq+I*K-2t.
Now, sunlet graph Lq decomposes Cq/2*K-2t by Theorem 8, and we have Kn+I*K-m decomposing into sunlet graph of length q.
Case  2 (q∣m)
Subcase 2.1 (m≡0(mod4)). Suppose m=q, and by Lemma 9, cycle Cn decomposes Kn+I, and we have
(11)Cn*K-q∣Kn+I*K-q.
Also, sunlet graph Lq decomposes each Cn*K-q by Theorem 6, and we have sunlet graph Lq decomposing Kn+I*K-m.
Subcase 2.2 (m≡2(mod4)). Let m=q and r≤n an odd integer. Cycle Cr decomposes Kn+I, by Lemmas 9, 10, and 11, and we have
(12)Cr*K-q∣Kn+I*K-q.
Now, each Cr*K-q decomposes into sunlet graph Lq by Theorem 6, and we have Kn+I*K-m decomposing into sunlet graph Lq as required.
Subcase 2.3 (m>q). Set m=wq, where w is any positive integer, then by Subcases 2.1 and 2.2, we have
(13)Lq*K-w∣(Kn+I*K-q)*K-w.
Each graph Lq*K-w decomposes into sunlet graph Lq by Remark 7, and we have Kn+I*K-m decomposing into sunlet graph Lq.



---

*Source: 907249-2013-03-19.xml*