# On the Existence of a Cyclic Near-Resolvable (6n+4)-Cycle System of 2K12n+9

Authors: Raja'i Aldiabat; Haslinda Ibrahim; Sharmila Karim
Journal: Journal of Mathematics
 (2019)

---

## Abstract

In this article, we prove the existence of a simple cyclic near-resolvablev-1/2-cycle system of 2Kv for v≡9mod12 by the method of constructing its starter. Then, some new properties and results related to this construction are formulated.


---

## Body

## 1. Introduction

Throughout this paper, all graphs are considered undirected with vertices inZv where v is odd. As usual, Kv will denote the complete graph of order v, and λKv will denote the complete multigraph of order v and multiplicity λ in which every two vertices are joined by λ parallel edges.Ak-cycle system of a graph G=V,E is a multiset C of k-cycles of G whose edge sets partition E. C is said to be cyclic if V=Zv and for each k-cycle C=c1,c2,…,ck in C we have that C+1=c1+1,c2+1,…,ck+1modv is also in C, and it is said to be simple if all its cycles are distinct. A starter of cyclic k-cycle system of G is a multiset S of k-cycles that generates the multiset C by repeated addition of 1 modulo v. A near-k-factor of G is a spanning k‐regular subgraph of G-a for some vertex a in G.Ak-cycle system C of 2Kv is said to be near-resolvable if its cycles can be partitioned into near-2-factors N0,N1,…,Nv-1 and C is denoted by v,k,2-NRCS. In general, it has been shown that there exists a near-resolvable k-cycle system of λKv if and only if λ is even and v≡1modk [1]. Such a near-resolvable k-cycle system is cyclic if it is possible to label the vertices of 2Kv with the elements of the cyclic group Zv in such a way that Ni=N0+i for 0≤i≤v-1, where N0+i denotes the near-2-factor of 2Kv obtained from N0 by adding i modulo v to all its vertices. The near-2-factor N0 is called a starter of cyclic near-resolvable k-cycle system of 2Kv.The existence problem ofk-cycle systems of the complete multigraph λKv has received much attention in recent years; this existence problem has been completely solved by Alspach and Gavlas [2] and by Šajna [3] for the important case when λ=1, and by Alspach et al. [4] for the case λ=2. An easier proof of the existence of odd cycle systems of Kv using the difference method has been reproved by Buratti [5]. Then, Wu and Buratti [6] provided an algorithm to construct an explicit odd k-cycle system of Kv whenever it exists. In particular, the existence of cyclic k-cycle systems of Kv has been solved when v≡1orkmod⁡2k [7, 8], k=v [9], k is even with v>2k [10], k is a prime with the exception of v,k=9,3 [7], k≤32 or k is twice a prime power [11], and k is thrice a prime [12]. Further results on cycle systems are in the surveys [13–15].The necessary and sufficient conditions for the existence of cyclicv-cycle system of λKv and for the existence of simple cyclic p-cycle system of λKp, where p is a prime, have been proved by Buratti et al. [16]. For v≥3 odd, the necessary and sufficient conditions for decomposing λKv into λ-cycles, and into cycles of prime length have been established by Smith in [17]. Shortly later, Bryant et al. [18] proved that the necessary and sufficient conditions for the existence of a k-cycle system of λKv for all 3≤k≤v are that λv-1 is even and k divides the number of edges in λKv. More general results such as the existence problem for decomposing λKv into cycles of varying lengths have been presented in [19, 20].The problem of constructing near-resolvablek-cycle system of Kv has been contributed by many authors. A near-resolvable k-cycle system of Kv has been constructed for k=4 with v≡1mod⁡8 except possibly values v=33,41,57 and except v=9 (for which such a system does not exist) [21], k=10 with v≡5mod⁡20 or v=41 [22], k≥11 with v=4k+1 [23]. Recently, the existence of a near-resolvable k-cycle system of K2km+1 for all m≥1 and k≡2mod⁡4 except possibly for m=2 and k≥14 has been proved by Wang and Cao [24]. Previously, it has been proved that there exists a rm+1,r,2-NRCS for all odd r≥3 and all m≥1 [25]. In 2018, Matsubara and Kageyama [26] proved that a cyclic v,4,2-NRCS exists if and only if v≡1mod⁡4.In Section2, we review some well-known definitions and preliminary results. Some introductory results are formulated in Section 3. Then, in Section 4, we explicitly construct a simple cyclic v,v-1/2,2-NRCS for the case v≡9mod⁡12 using a difference method. Moreover, we formulate some properties which are related to this construction. Finally, Section 5 discusses the conclusions and future work.


## 2. Preliminaries

In this section, we recall briefly some definitions and preliminary results that we used in the sequel. We start with the following definitions.Definition 1 (see [27]).
A path cover of a graphG is a collection of vertex-disjoint paths of G that covers the vertex set of G.Definition 2 (see [5]).
LetG be a graph and xy be an edge in G. The difference of an edge xy is defined as dx,y=±y-x.Definition 3 (see [5, 28]).
LetG=VG,EG be a graph. The multiset (1)∆G=±y-x∣x,y∈VG,xy∈EGis called the list of differences from G. More generally, for a set G=G1,G2,…,Gn of graphs, the list of differences from G is the multiset ∆G=∆G1∪_∆G2∪_…∪_∆Gn which is obtained by linking together the ∆Gi’s.Definition 4 (see [6]).
LetC be a k-cycle in λKv. A cycle orbit of C, denoted as OrbC, is a set of distinct k-cycles in C+i∣i∈Zv. A cycle orbit of C is called full if its cardinality is v; otherwise, the cycle orbit of C is short.
For convenience, we sayC is a full (short) cycle.Definition 5 (see [5, 6]).
LetC be a k-cycle in λKv. The type of C is the cardinality of the set z∈Zv∣C+z=C.From the above definition, it is obvious that if a cycleC is of type 1 d>1, then C is a full (short) cycle.Lemma 6 (see [5]).
IfC is a k-cycle in λKv, then the type of C is a common divisor of k and v.The following lemma is a consequence of the theory developed in [16]. It will be crucial for proving our main results.Lemma 7.
LetS be a multiset of k-cycles of λKv. Then, S is a starter of cyclic k-cycle system of λKv if and only if ∆S covers Zv∗=Zv-0 exactly λ times.


## 3. Introductory Results

In this section, we introduce some definitions, notations, and introductory results required to establish our main results in the next section. We begin with defining relative path, relative cycle, and alternating arithmetic path that will be the basis for constructing the starter of simple cyclic near-resolvable6n+4-cycle system of 2K12n+9.Definition 8.
LetG be a graph of order v, P=x1,x2,…,xk be a k-path of G, and C=x1,x2,…,xk be a k-cycle of G.(1)
Thek-path P¯=v-x1,v-x2,…,v-xk is called the relative path of P.(2)
Thek-cycle C¯=v-x1,v-x2,…,v-xk is called the relative cycle of C.Lemma 9.
LetG be a graph of order v.(1)
IfP is a k-path of G and P¯ is the relative path of P, then ΔP=ΔP¯.(2)
IfC is a k-cycle of G and C¯ is the relative cycle of C, then ΔC=ΔC¯.Proof.
(1)
SupposeP=x1,x2,…,xk and P¯=y1,y2,…,yk are k-path of G and its relative path, respectively. The list of differences from P and P¯ can be defined as(2)ΔP=±xi-xi-1∣i=2,3,…,k,(3)ΔP¯=±yi-yi-1∣i=2,3,…,k. SinceP¯ is the relative path of P, then yi=v-xi, for all i=1,2,…,k. Hence, substituting yi=v-xi into (3), we obtain(4)ΔP¯=±v-xi-v-xi-1∣i=2,3,…,k=±xi-xi-1∣i=2,3,…,k=ΔP. (2)
The proof is similar to part(1).Lemma 10.
LetG be a graph of order v. If C1 is a k-cycle of G and C2 is the relative cycle of C1; then, orbC1≠orbC2.Proof.
LetC1=c1,1,c1,2,…,c1,k be a k-cycle of G and let C2=c2,1,c2,2,…,c2,k be the relative cycle of C1. Assume on the contrary that orbC1=orbC2; then, there exists an integer i∈Zv such that C2=i+C1. This implies that(5)c2,j=i+c1,jfor  allj=1,2,…,k.Since C2 is the relative cycle of C1, then(6)c2,j=v-c1,jfor  allj=1,2,…,k.Solving (5) and (6) for c1,j and c2,j yields(7)c1,j=v-i2andc2,j=v+i2for  allj=1,2,…,k.This contradicts the fact that C1 and C2 are actually k-cycles. Thus, C1 and C2 must have different orbits, so orbC1≠orbC2.An alternating arithmetic path is a path with two sets of vertices satisfying certain conditions, as defined below.Definition 11.
Letm and n be positive integers with n≤m≤n+1. An m+n-alternating arithmetic path, denoted by AAPm+n, is a path of length m+n with vertex set V=x1,x2,…,xm∪y1,y2,…,yn and edge set E=xi,yi∣i=1,2,…,n∪yi,xi+1∣i=1,2,…,m-1, such that the following properties are satisfied:(1)
xi-xi-1 is constant, for all 2≤i≤m.(2)
yi-yi-1 is constant, for all 2≤i≤n.Definition 12.
LetAAPm+n be an m+n-alternating arithmetic path. The list of differences from AAPm+n is the multiset(8)∆AAPm+n=±yi-xi∣1≤i≤n∪_±xi+1-yi∣1≤i≤m-1.According to Definition 11, the m+n-alternating arithmetic path either has odd order 2n+1 when m=n+1 or has even order 2n when m=n. Throughout, we use the following notations for m+n-alternating arithmetic path of odd order and even order, respectively:(9)AAP2n+1=x1,y1,x2,y2,…,xn,yn,xn+1=xi,yi2n+1,AAP2n=x1,y1,x2,y2,…,xn,yn=xi,yi2n.In the following, we define a modulo scalar multiplication on paths and cycles in a finite graph of order v, and then we prove some lemmas that will be used later in order to investigate some properties related to our construction.Definition 13.
Letv, k, and h be positive integers with 1≤h<v and gcdh,v=1. Let G be a graph of order v, P=x1,x2,…,xk be a k-path of G, and C=x1,x2,…,xk be a k-cycle of G.(1)
The modulov multiplication of P and h is the k-path h·P=hx1,hx2,…,hxkmodv.(2)
The modulov multiplication of C and h is the k-cycle h·C=hx1,hx2,…,hxkmodv.Lemma 14.
LetG be a graph of order v and C be a k-cycle of G. If h is any integer such that 1≤h<v and gcdh,v=1, then(1)
h·C=v-h·C¯.(2)
v-h·C=h·C¯.Proof.
(1)
Suppose thatC=x1,x2,…,xk is a k-cycle of G. Then,(10)h·C=hx1,hx2,…,hxkmodv. Sincev2-xi+hv is divisible by v, then v2-xi+hv≡0mod⁡v. Hence, (11)h·C=v2-x1+hv+hx1,v2-x2+hv+hx2,…,v2-xk+hv+hxkmodv=v-x1v-h,v-x2v-h,…,v-xkv-hmodv=v-h·v-x1,v-x2,…,v-xkmodv=v-h·C¯. (2)
From the definition of modulov multiplication of C and v-h, we obtain(12)v-h·C=v-hx1,v-hx2,…,v-hxkmodv=vx1-hx1,vx2-hx2,…,vxk-hxkmodv. Butvxi is divisible by v, and this implies that vxi≡0modv. Hence, (13)v-h·C=-hx1,-hx2,…,-hxkmodv=h·-x1,-x2,…,-xkmodv=h·v-x1,v-x2,…,v-xkmodv=h·C¯.Lemma 15.
Letv and h be integers with 1≤h<v and gcdv,h=1. Then, h·Zv∗=himodv∣i∈Zv∗ covers Zv∗.Proof.
Letx,y∈Zv∗ with x≠y. Assume on the contrary that hxmod⁡v=hymod⁡v=z. Then, we get hx=z+m1v and hy=z+m2v for some integers m1 and m2.
Subtracting the above equations, we obtainhx-hy=m1v-m2v. This implies (14)x-y=vm1-m2h.Since ,y∈Zv∗, then x-y<v and then from (14) we get vm1-m2/h<v. This implies that m1-m2/h<1 and therefore m1-m2<h.
On the other hand, sincegcdv,h=1 and m1-m2<h, then from (14) it follows that x-y is a noninteger rational number. This contradicts the fact that x-y is an integer. Thus, there are no x,y∈Zv∗ such that hxmodv=hymodv, so h·Zv∗ covers Zv∗.Lemma 16.
Letn≥0 be an integer; then, 12n+9 and 6n+4 are relatively prime.Proof.
Letc be an integer such that c divides both 12n+9 and 6n+4. Then, there exists x,y∈Z such that(15)cx=12n+9(16)cy=6n+4.From the equations above, we obtain cx=12n+9=26n+4+1=2cy+1. This implies that cx-2cy=1, and then(17)x-2y=1c.Since x-2y∈Z, then either c=1 or c=-1. Therefore, 1 is the only positive integer which divides both 12n+9 and 6n+4.Now, we define a way of writing the cycle as linked vertex-disjoint paths. This way will be used mainly to prove the existence results in the following section.Definition 17.
LetC be a k-cycle, r≥2 be a positive integer, and P=P1,P2,…,Pr be a path cover of C. The set of r edges in C that links the end of Pi with the start of Pi+1, for all i=1,2,…,r where Pr+1=P1, is called the link set of P.Remark 18.
LetC be a k-cycle, P=P1,P2,…,Pr be a path cover of C, and E′=e1,e2,…,er be a link set of P. The cycle C can be expressed as linked vertex-disjoint paths as follows:(18)C=P1,P2,…,Pr.Lemma 19.
LetC be a k-cycle, P=P1,P2,…,Pr be a path cover of C, and E′=e1,e2,…,er be a link set of P. Then, we have ∆C=∆P∪_∆E′.Proof.
LetVP=⋃i=1rVPi be the set of vertices of P and EP=⋃i=1rEPi the set of edges of P. Based on Definition 3, the list of differences from C is defined as a multiset consisting of the difference for each edge in C as follows:(19)∆C=da,b∣a,b∈VC,ab∈EC.Since P is a path cover of C, then (20)VC=VP.Also, from the definition of link set of P, we obtain (21)EC=EP∪E′.Substituting (20) and (21) into (19) yields(22)∆C=da,b∣a,b∈VP,ab∈EP∪E′=da,b∣a,b∈VP,ab∈EP∪_dei∣ei∈E′=∆P∪_∆E′.To close this section, we provide an example below to demonstrate the concepts discussed in this section.Example 20.
LetG=2K21, C=4,1,3,2,6,11,14,12,13,16 be a 10-cycle of G. Then, the cycle C can be written as linked vertex-disjoint paths as follows:(23)C=AAP14,Q1,AAP24,Q2,where AAP14=4,1,3,2=5-i,i4 and AAP24=11,14,12,13=10+i,15-i4 are 4-alternating arithmetic paths and Q1=6 and Q2=16 are trivial paths. In addition, the set of four edges E′=2,6,6,11,13,16,16,4 that links the paths AAP14,Q1,AAP24 and Q2, respectively, along the cycle C is considered the link set for the path cover P=AAP14,Q1,AAP24,Q2.
Based on Definition8, the relative cycle of C is C¯=17,20,18,19,15,10,7,9,8,5. It is easy to see that the sum of each pair of corresponding vertices of C and its relative cycle is equal to 21 (the order of G).
Sincegcd20,21=1, then(24)20·C=80,20,60,40,120,220,280,240,260,320mod21=17,20,18,19,15,10,7,9,8,5.In other words, C¯=20·C as shown in part (2) of Lemma 14.


## 4. Simple Cyclic Near-Resolvable6n+4-Cycle System of 2K12n+9

In this section, we prove, explicitly and directly, the existence of a simple cyclic near-resolvable6n+4-cycle system of 2K12n+9 by constructing its starter.To construct a simple cyclic near-resolvable6n+4-cycle system of 2K12n+9, it is enough to exhibit a starter of cyclic k-cycle system of 2Kv which satisfies a near-2-factor and contains no two cycles in the same orbit. Let us provide an example to illustrate the above definition.Example 21.
LetG=2K9 and S=C1,C2 be a set of 4-cycles of G such that C1=1,6,5,7 and C2=8,3,4,2.
Easily, it can be observed that the4-cycles of S are vertex-disjoint and cover each nonzero element of Z9 exactly once. Hence, we can say that S is a 2-regular graph satisfying the near-2-factor with focus zero.
In order to show thatS=C1,C2 is a starter of cyclic 4-cycle system of 2K9, we need to calculate the list of differences from S as illustrated in Table 1.Table 1
The list of differences fromS=C1,C2.
4-cycles The list of differences C 1 = 1 , 6 , 5 , 7 5 , 4 , 1 , 8 , 2 , 7 , 6 , 3 C 2 = 8 , 3 , 4 , 2 5 , 4 , 1 , 8 , 2 , 7 , 6 , 3As listed in Table1, each nonzero element of Z9 occurs twice in ∆S=∆C1∪_∆C2. Then, by Lemma 7, S=C1,C2 is a starter set of cyclic 4-cycle system of 2K9.Since the sum of each pair of corresponding vertices ofC1 and C2 is equal to 9 the order of G, then C2 is the relative cycle of C1, and so, by Lemma 10, orbC1≠orbC2. From Definition 4, we conclude that all the generated cycles by repeated addition of 1 modulo 9 to S=C1,C2 contain no repetitions.Now,S satisfies all the conditions to be a starter of simple cyclic near-resolvable 4-cycle system of 2K9. Once the starter set has been provided, all cycles of simple cyclic 9,4,2-NRCS can be generated by repeated addition of 1 modulo 9 as shown in Table 2.Table 2
A simple cyclic near-resolvable 4-cycle system of2K9.
Focus O r b C 1 O r b C 2 i = 0 1 , 6 , 5 , 7 8 , 3 , 4 , 2 i = 1 2 , 7 , 6 , 8 0 , 4 , 5 , 3 i = 2 3 , 8 , 7 , 0 1 , 5 , 6 , 4 i = 3 4 , 0 , 8 , 1 2 , 6 , 7 , 5 i = 4 5 , 1 , 0 , 2 3 , 7 , 8 , 6 i = 5 6 , 2 , 1 , 3 4 , 8 , 0 , 7 i = 6 7 , 3 , 2 , 4 5 , 0 , 1 , 8 i = 7 8 , 4 , 3 , 5 6 , 1 , 2 , 0 i = 8 0 , 5 , 4 , 6 7 , 2 , 3 , 1In the following, we construct a simple cyclic near-resolvable6n+4-cycle system of 2K12n+9. Since the construction is different depending on whether n is odd or even, we classify the construction into two cases: when n is odd and when n is even.Lemma 22.
For any positive odd integern, there exists a simple cyclic near-resolvable 6n+4-cycle system of 2K12n+9.Proof.
Letv=12n+9, where n is a positive odd integer. Let C1 and C2 be the 6n+4-cycles of 2Kv defined as linked vertex-disjoint paths as follows:(25)C1=AAP13n+3,AAP23n+1C2=AAP1¯3n+3,AAP2¯3n+1,where(26)AAP13n+3=4i-3,12n-4i+103n+3,AAP23n+1=6n-4i+6,6n+4i+53n+1,AAP1¯3n+3=v-4i-3,v-12n-4i+103n+3=12n-4i+12,4i-13n+3,AAP2¯3n+1=v-6n-4i+6,v-6n+4i+53n+1=6n+4i+3,6n-4i+43n+1.Since n is a positive odd integer, then any 3n+3-alternating arithmetic path and 3n+1-alternating arithmetic path have even order. As illustrated in Figure 1, the construction of C1 and C2 can be described in terms of their vertices as Ci=ci,1,ci,2,…,ci,6n+4 for i=1,2.
In this way, we note that in the cycleC1 the c1,i’s with i odd and the c1,i’s with i even form the following increasing sequences, respectively:
c 1,1 < c 1,6 n + 3 < c 1,3 < c 1,6 n + 1 < ⋯ < c 1,3 n + 4 < c 1,3 n + 2 in the interval I=1,6n+3 and
c 1,3 n + 3 < c 1,3 n + 1 < c 1,3 n + 5 < c 1,3 n - 1 < ⋯ < c 1,2 < c 1,6 n + 4 in the complement of I in Zv.
In contrast, inC2 the c2,i’s with i odd and the c2,i’s with i even form the following decreasing sequences, respectively:
c 2,1 > c 2,6 n + 3 > c 2,3 > c 2,6 n + 1 > ⋯ > c 2,3 n + 4 > c 2,3 n + 2 in J=6n+6,12n+8 and
c 2,3 n + 3 > c 2,3 n + 1 > c 2,3 n + 5 > c 2,3 n - 1 > ⋯ > c 2,2 > c 2,6 n + 4 in the complement of J in Zv.
Thus, fori=1,2, the vertices in Ci are pairwise distinct and hence Ci is actually 6n+4-cycle.
In the rest of this proof, three parts are considered to prove that the set of cyclesS=C1,C2 satisfies the conditions to be a starter of simple cyclic near-resolvable 6n+4-cycle system of 2Kv.
Part 1. In this part, we prove that S=C1,C2 satisfies the near-two-factor condition. This will be verified by proving that the union of vertex sets of C1 and C2 covers each element of Zv∗ exactly once. The vertex sets of C1 and C2 can be enumerated by the union of vertex sets of all linked paths in both C1 and C2, respectively.(27)VC1=VAAP13n+3∪VAAP23n+1,(28)VC2=VAAP1¯3n+3∪VAAP2¯3n+1,where(29)VAAP13n+3=⋃i=13n+3/24i-3⋃⋃i=13n+3/212n-4i+10=1,5,…,6n+3∪12n+6,12n+2,…,6n+4,VAAP23n+1=⋃i=13n+1/26n-4i+6⋃⋃i=13n+1/26n+4i+5=6n+2,6n-2,…,4∪6n+9,6n+13,…,12n+7,VAAP1¯3n+3=v-i∣i∈VAAP13n+3=12n+8,12n+4,…,6n+6∪3,7,…,6n+5,VAAP2¯3n+1=v-i∣i∈VAAP23n+1=6n+7,6n+11,…,12n+5∪6n,6n-4,…,2.According to the above vertex sets, it can be easily noted that each nonzero element of Zv occurs exactly once in VC1∪_VC2. Since any cycle is a 2-regular graph and VC1∪_VC2=Zv∗, then the set of cycles S=C1,C2 forms near-two-factor with focus zero.
Part 2. This part shows that the set of cycles S=C1,C2 is a starter of cyclic 6n+4-cycle system of 2Kv. For this part, it is sufficient to prove that the list of differences from S covers Zv∗ exactly twice.
Based on Definition3, the list of differences from S is defined as ∆S=∆C1∪_∆C1. Then, from Lemma 19 and Definition 12, the list of differences from C1 is(30)∆C1=∆AAP13n+3∪_d6n+4,6n+2∪_∆AAP23n+1∪_d12n+7,1,where(31)∆AAP13n+3=±yi-xi∣1≤i≤3n+32∪_±xi+1-yi∣1≤i≤3n+12=±12n-8i+13∣1≤i≤3n+32∪_±12n-8i+9∣1≤i≤3n+12=12n+5,12n-3,…,1∪_4,12,…,12n+8∪_12n+1,12n-7,…,5∪_8,16,…,12n+4,∆AAP23n+1=±yi-xi∣1≤i≤3n+12∪_±xi+1-yi∣1≤i≤3n-12=±8i-1∣1≤i≤3n+12∪_±8i+3∣1≤i≤3n-12=7,15,…,12n+3∪_12n+2,12n-6,…,6∪_11,19,…,12n-1∪_12n-2,12n-10,…,10,d6n+4,6n+2=2,12n+7,d12n+7,1=12n+6,3.As shown above, each nonzero element of Zv appears exactly once in ∆C1.
From (25), we can deduce that C2 is the relative cycle of C1. Hence, by part (2) of Lemma 9, we obtain ∆C1=∆C2. Now, we conclude that each nonzero element of Zv appears exactly twice in ∆S. Based on Lemma 7, the set of cycles S=C1,C2 is a starter of cyclic 6n+4-cycle system of 2Kv for all odd positive integer n.
Part 3. We check that all the generated cycles from the starter S=C1,C2 contain no repetitions by showing that all the cycles of S have different orbit.
SinceC2 is the relative cycle of C1, then by Lemma 10, orbC1≠orbC2. Thus, all the generated cycles by repeated addition of 1 modulo v to S=C1,C2 contain no repetitions.
By summing up the former three parts, we have proved that, for any positive odd integern, the set of cycles S=C1,C2 is a starter of simple cyclic near-resolvable 6n+4-cycle system of 2Kv.Figure 1
The construction ofC1 and C2 in 2Kv. n is a positive odd integer.Lemma 23.
For any nonnegative even integern, there exists a simple cyclic near-resolvable 6n+4-cycle system of 2K12n+9.Proof.
Letv=12n+9, where n is a nonnegative even integer. Let C1 and C2 be the 6n+4-cycles of 2Kv defined as linked vertex-disjoint paths as follows:(32)C1=AAP13n+3,AAP23n+1C2=AAP1¯3n+3,AAP2¯3n+1,where(33)AAP13n+3=4i-3,12n-4i+103n+3,AAP23n+1=6n+4i+3,6n-4i+43n+1,AAP1¯3n+3=v-4i-3,v-12n-4i+103n+3=12n-4i+12,4i-13n+3,AAP2¯3n+1=v-6n-4i+6,v-6n+4i+53n+1=6n-4i+6,6n+4i+53n+1.Since n is a nonnegative even integer, then any 3n+3-alternating arithmetic path and 3n+1-alternating arithmetic path have odd order. As shown in Figure 2, the construction of C1 and C2 can be described in terms of their vertices as Ci=ci,1,ci,2,…,ci,6n+4 for i=1,2.
The rest of this proof is similar to the proof of Lemma22, hence omitted.Figure 2
The construction ofC1 and C2 in 2Kv, n is a nonnegative even integer.Theorem 24.
For each positivev≡9mod12, there exists a simple cyclic near-resolvable v-1/2-cycle system of 2Kv.Proof.
The proof is immediate from Lemmas22 and 23.By reviewing the construction of a starter of simple cyclic near-resolvable6n+4-cycle system of 2K12n+9, as shown in Figures 1 and 2, the construction has a butterfly shape in which each cycle represents a side of symmetrical butterfly wings. If given one cycle C of the starter set, the other is the relative cycle of C.Next, some related properties of the starter of simple cyclic near-resolvable6n+4-cycle system of 2K12n+9 will be formulated.Lemma 25.
Letn, h, and v=12n+9 be integers such that 1≤h<v and gcdh,v=1. If S=C1,C2 is a starter of simple cyclic near-resolvable 6n+4-cycle system of 2Kv, then h·VS=himodv∣i∈VC1∪VC2 covers Zv∗.Proof.
SinceS=C1,C2 is a starter of simple cyclic near-resolvable 6n+4-cycle system of 2Kv, then S=C1,C2 satisfies the near-two-factor with focus zero. This implies that VC1∪VC2=Zv∗. Then, by Lemma 15, we obtain the notion that h·VS covers Zv∗.Theorem 26.
Letn, h, and v=12n+9 be integers with 1≤h<v and gcdh,v=1. If S=C1,C2 is a starter of simple cyclic near-resolvable 6n+4-cycle system of 2Kv that satisfies (25) or (32), then h·C1,h·C2 and v-h·C1,v-h·C2 are the same starter of simple cyclic near-resolvable 6n+4-cycle system of 2Kv.Proof.
Suppose thatS=Ci=ci,1,ci,2,…,ci,6n+4∣i=1,2 is a starter of simple cyclic near-resolvable 6n+4-cycle system of 2Kv that satisfies (25) or (32). Then, C2 is the relative cycle of C1 and hence, by part (1) and (2) of Lemma 14, we have (34)h·C1=v-h·C2andh·C2=v-h·C1.To prove that h·C1,h·C2 is a starter of simple cyclic near-resolvable 6n+4-cycle system of 2Kv, we need to prove the following:(1)
h·VS covers Zv∗.(2)
∆h·C1∪_∆h·C2 covers Zv∗ exactly twice.
The first condition is satisfied from Lemma25. Based on the definition of h·C1, for each edge c1,i,c1,i+1 in C1 we have that hc1,i,hc1,i+1modv=x1,i,x1,i+1 is an edge in h·C1.
Supposedi=±c1,i,c1,i+1 is the difference of the edge c1,i,c1,i+1 for i=1,2,…,6n+4, where c1,6n+5=c1,1. Then, the difference of the edge x1,i,x1,i+1 is ±x1,i-x1,i+1=hdimodv, where i=1,2,…,6n+4 and x1,6n+5=x1,1.
SinceS=C1,C2 is a starter of simple cyclic near-resolvable 6n+4-cycle system of 2Kv, then ∆C1∪_∆C2 covers Zv∗ exactly twice. But C2 is the relative cycle of C1; this implies that ∆C1=∆C2=di∣i=1,2,…,6n+4 covers Zv∗ exactly once. Therefore, ∆h·C1=∆h·C2=hdimodv∣i=1,2,…,6n+4 also covers Zv∗ exactly once (from Lemma 15); thus, ∆h·C1∪_∆h·C2 covers Zv∗ exactly twice.In the following example, we construct some of distinct starters of simple cyclic9,4,2-NRCS in accordance with the theorem above.Example 27.
Leth be an integer with 1≤h<9 and gcdh,9=1, G=2K9 with vertices in Z9 and S=C1,C2 be a set of 4-cycles of G where C1=1,6,5,7 and C2=8,3,4,2.In Example21, it is proved that S=C1,C2 is a starter of simple cyclic 9,4,2-NRCS. The next table shows the possible values of h that make the set of cycles h·C1,h·C2 be a starter of simple cyclic 9,4,2-NRCS.In Table3, it can be remarked that each set of cycles h·C1,h·C2 covers Z9∗ exactly once and the list of differences from h·C1,h·C2 covers Z9∗ exactly twice. Therefore, we conclude that for any 1≤h<9 such that gcdh,9=1 both sets h·C1,h·C2 and 9-h·C1,9-h·C2 are the same starter of simple cyclic 9,4,2-NRCS.Table 3
A collection of distinct starters of simple cyclic9,4,2-NRCS.
h h ⋅ C 1 , h ⋅ C 2 ∆ h ⋅ C 1 ∪ _  ∆ h ⋅ C 2 1 or 8 1 , 6 , 5 , 7 , 8 , 3 , 4 , 2 ± 5 , ± 1 , ± 2 , ± 6 ∪ _ ± 5 , ± 1 , ± 2 , ± 6 2 or 7 2 , 3 , 1 , 5 , 7 , 6 , 8 , 4 ± 1 , ± 2 , ± 4 , ± 3 ∪ _ ± 1 , ± 2 , ± 4 , ± 3 4 or 5 4 , 6 , 2 , 1 , 5 , 3 , 7 , 8 ± 2 , ± 4 , ± 1 , ± 3 ∪ _ ± 2 , ± 4 , ± 1 , ± 3The simple cyclic near-resolvable6n+4-cycle system of 2K12n+9 is a v×2 array if its starter is a set of full cycles. By the following theorem, we can answer the question whether the starter of simple cyclic near-resolvable 6n+4-cycle system of 2K12n+9 is set of full cycles or not.Theorem 28.
Ifn is a nonnegative integer, then any starter of simple cyclic near-resolvable 6n+4-cycle system of 2K12n+9 is a set of full cycles.Proof.
LetC1 and C2 be 6n+4-cycles in 2K12n+9. Suppose that S=C1,C2 is a starter of simple cyclic near-resolvable 6n+4-cycle system of 2K12n+9.
From Lemma16, we have that 6n+4 and 12n+9 are relatively prime, which implies that the only positive common divisor of 6n+4 and 12n+9 is 1. By Lemma 6, since the type of any 6n+4-cycle in 2K12n+9 is a common divisor of 6n+4 and 12n+9, it follows that any cycle in S is of type 1. Consequently, any starter of simple cyclic near-resolvable 6n+4-cycle system of 2K12n+9 is a set of full cycles.


## 5. Conclusions

This article has proposed near-resolvablek-cycle system of 2Kv as an edge-decomposition of the complete multigraph 2Kv into v classes of k-cycles such that each class satisfies the near-2-factor. In particular, the difference method has been exploited to construct a simple cyclic near-resolvable v-1/2-cycle system of 2Kv for the odd case v≡9mod12, and this construction has been exemplified for the case v=9. Finally, we have formulated some properties of this construction. We expect that this study can be developed and extended to construct a simple cyclic near-resolvable k-cycle system of 2Kv for the case v odd.



---

*Source: 5276753-2019-08-01.xml*