On the existence of cycle frames and almost resolvable cycle systems

AbstractSuppose H is a complete m-partite graph Km(n1,n2,…,nm) with vertex set V and m independent sets G1,G2,…,Gm of n1,n2,…,nm vertices respectively. Let G={G1,G2,…,Gm}. If the edges of λH can be partitioned into a set C of k-cycles, then (V,G,C) is called a k-cycle group divisible design with index λ, denoted by (k,λ)-CGDD. A (k,λ)-cycle frame is a (k,λ)-CGDD (V,G,C) in which C can be partitioned into holey 2-factors, each holey 2-factor being a partition of V∖Gi for some Gi∈G. Stinson et al. have resolved the existence of (3,λ)-cycle frames of type gu. In this paper, we show that there exists a (k,λ)-cycle frame of type gu for k∈{4,5,6} if and only if g(u−1)≡0(modk), λg≡0(mod2), u≥3 when k∈{4,6}, u≥4 when k=5, and (k,λ,g,u)≠(6,1,6,3). A k-cycle system of order n whose cycle set can be partitioned into (n−1)/2 almost parallel classes and a half-parallel class is called an almost resolvable k-cycle system, denoted by k-ARCS(n). Lindner et al. have considered the general existence problem of k-ARCS(n) from the commutative quasigroup for k≡0(mod2). In this paper, we give a recursive construction by using cycle frames which can also be applied to construct k-ARCS(n)s when k≡1(mod2). We also update the known results and prove that for k∈{3,4,5,6,7,8,9,10,14} there exists a k-ARCS(2kt+1) for each positive integer t with three known exceptions and four additional possible exceptions