Let \(K = K(a,p;\lambda_1,\lambda_2)\) be the multigraph with: the number of vertices in each part equal to \(a\); the number of parts equal to \(p\); the number of edges joining any two vertices of the same part equal to \(\lambda_1\); and the number of edges joining any two vertices of different parts equal to \(\lambda_2\). The existence of \(C_4\)-factorizations of \(K\) has been settled when \(a\) is even; when \(a \equiv 1 \ (\mbox{mod } 4)\) with one exception; and for very few cases when \(a \equiv 3 \ (\mbox{mod } 4)\). The existence of \(C_z\)-factorizations of \(K\) has been settled when \(a \equiv 1 \ (\mbox{mod } z)\) and \(\lambda_1\) is even; when \(a \equiv 0 \ (\mbox{mod } z)\); and when \(z=2a\) where both \(a\) and \(\lambda_1\) is even. In this paper, we give a construction for \(C_z\)-factorizations of \(K\) for \(z \in \{ 4,4a \}\) when \(a\) is even.
Let \(K = K(a,p; \lambda_1, \lambda_2)\) denote the graph formed from \(p\) vertex-disjoint copies of the multigraph \(\lambda_1 K_a\) by joining each pair of vertices in different copies with \(\lambda_2\) edges. The vertex set, \(V(K)\), is always chosen to be \(\mathbb{Z}_a \times \mathbb{Z}_p\), with parts \(\mathbb{Z}_a \times \{j\}\) for each \(j \in \mathbb{Z}_p\); naturally, each part induces a copy of \(\lambda_1 K_a\).We say the vertex \((i,j)\) is on level i and in part j. An edge is said to be a mixed edge if it joins vertices in different parts, and is said to be a pure edge (in part \(j\)) if it joins two vertices in the \(j\)th part.
Let \(C_z\) denote a cycle of length \(z\). A \(C_z\)-factorization is a \(2\)-factorization such that each component of each \(2\)-factor is a cycle of length \(z\); each \(2\)-factor of a \(C_z\)-factorization is known as a \(C_z\)-factor. \(C_z\)-factorizations are also known as resolvable \(C_z\)-decompositions. A \(C_{ \{z_1,z_2,…,z_k\} }\)-factorization is a 2-factorization such that each 2-factor is a \(C_w\)-factor where \(w \in \{ z_1, z_2, …, z_k \}\).
There has been considerable interest recently in \(C_z\)-decompositions of various graphs, such as complete graphs and complete mutipartite graphs. In the resolvable case, these results are collectively known as addressing the Oberwolfach problem. More recently, the existence problem for \(C_z\)-decompositions of \(K\) for \(z \in \{3,4\}\) has been solved [3, 4, 5]. Such decompositions are known as \(C_z\)–group-divisible designs with two associate classes, following the notation of Bose and Shimamoto who considered the existence problem for \(K_z\)-group divisible designs. The reason for this name is that the structure can be thought of as partitioning \(ap\) symbols, or vertices, into \(p\) sets of size \(a\) in such a way that symbols that are in the same set in the partition occur together in \(\lambda_1\) blocks, and are known as first associates, whereas symbols that are in different sets in the partition occur together in \(\lambda_{2}\) blocks, and are known as second associates [2].
\(C_z\)-factorizations of \(K\) have also been of interest[3]. Recently the existence of a \(C_4\)-factorization of \(K\) has been completely settled when \(a\) is even [1] and when \(a \equiv 1 \ (\mbox{mod } 4)\) with one exception [10, 11]. Some work has also been doen for the case where \(a \equiv 3 \ (\mbox{mod } 4)\) [6]. A general construction for \(C_z\)-factorizations of \(K\) when \(z\) is even, \(a \equiv 1 \ (\mbox{mod } z)\), and \(\lambda_1\) is even; when \(a \equiv 0 \ (\mbox{mod } z)\) [12]; and when \(z=2a\) where \(a\) and \(\lambda_1\) are even [8]. In this paper, we give a construction for \(C_z\)-factorizations of \(K\) for \(z \in \{4,4a\}\) when all parameters are even.
Lemma 1.1. Let \(z=4a\) where \(a\) is even. If there exists a \(C_z\)-factorization of \(K \left( a,p;\lambda_1,\lambda_2 \right)\), then:
(a) \(p \equiv 0 \ (\mbox{mod } 4)\),
(b) \(\lambda_1\) is even, and
(c) \(\lambda_2 > 0\).
Proof. Since the number of \(z\)-cycles in each \(C_z\)-factor is the number of vertices divided by \(z\), \(z\) must divide \(ap\), and since \(a = z/4\), \(p \equiv 0 \ (\mbox{mod } 4)\).
Each vertex is joined with \(\lambda_1\) edges to each of the \((a – 1)\) other vertices in its own part and with \(\lambda_2\) edges to each of the \(a(p – 1)\) vertices in the other parts; so the degree of each vertex is: \[\displaystyle d_K (v) = \lambda_1 (a – 1) + \lambda_2 a (p – 1).\]
Clearly, since \(K\) has a \(C_z\)-factorization, it is regular of even degree. The second term is even since \(a\) is even. The first term must therefore be even, so since \((a-1)\) is odd, \(\lambda_1\) must be even. Since \(a < z\), each \(C_z\)-factor must contain mixed edges; hence \(\lambda_2 >0\). ◻
Lemma 1.2. Let \(z=4a\) where \(a\) is even. If there exists a \(C_z\)-factorization of \(K(a,p;\lambda_1,\lambda_2)\), then \(\lambda_1 \leq \lambda_2 a (p – 1)\).
Proof. Since \(a < z\), each \(C_z\)-factor contains at most \((a-1)\) pure edges in each part. So each \(C_z\)-factor contains at most \((a-1)p\) pure edges. Since there are \(\lambda_1 \binom{a}{2} p\) pure edges, the number of \(C_z\)-factors in any \(C_z\)-factorization is at least: \[\displaystyle \frac{\lambda_1 \binom{a}{2} p}{(a – 1)p} = \frac{\lambda_1 a}{2}.\]
Each \(C_z\)-factor has \(ap\) edges, of which at most \((a – 1)p = ap – p\) are pure, so there are at least \(p\) mixed edges in any \(C_z\)-factor. Then the number of mixed edges in any \(C_z\)-factorization is at least: \[\displaystyle \frac{\lambda_1 a p}{2}.\]
Therefore, this number must be at most the number of mixed edges, \(\lambda_2 \binom{p}{2} a^2\), in \(K\): \[\displaystyle \frac{\lambda_1 ap}{2} \leq \lambda_2 \binom{p}{2} a^2,\] so \[\displaystyle \lambda_1 \leq \lambda_2 a (p – 1).\] ◻
Lemma 1.3. Let \(a\) be even. There exists a cyclical decomposition of \(K_a\) into edge-disjoint Hamiltonian paths such that the ends of the paths are vertices \(i\) and \(i + a/2\) for \(i \in \mathbb{Z}_{a/2}\).
Proof. Let \(i \in \mathbb{Z}_{a/2}\). The \(i\)th such Hamiltonian path is \[h_i = \big(i, i+1, i+(a-1), i+2, i+(a-2), \dots, i+(a/2 – 1), i+(a/2 + 1), i+(a/2) \big).\]
See Figure 2.
Note that \[K_a = \bigcup_{i \in \mathbb{Z}_{a/2}} h_i,\] and the ends of the Hamiltonian paths are always \(i\) and \(i+a/2\) \((\text{mod} \; a)\). Let \[H_a = \{ h_i | i \in \mathbb{Z}_{a/2} \} .\] ◻
Theorem 1.4. [7] Suppose \(z\) is even and \(p \equiv 0 \ (\mbox{mod } z)\). \(C_{z}\)-factorizations of \(\lambda K_p\) exist for all even \(\lambda\).
Theorem 1.5. [9] ] Suppose \(z > 2\). There exists a \(C_z\)-factorization of \(K(a,p;0,1)\) if and only if \(K \ne K(6,2;0,1)\) where \(z=6\).
Theorem 1.6. [1] Let \(a\) be even. There exists a \(C_4\)-factorization of \(K(a,p;\lambda_1, \lambda_2)\).
When \(z=4a\), there are two cases to consider with respect to the upper bound on \(\lambda_1\):
(a) \(\lambda_1 = 0\) or \(\lambda_2 a (p-1)\),
(b) \(\lambda_1 < \lambda_2 a (p-1)\).
If \(\lambda_1\) is equal to zero or its upper bound, then all of the factors in the factorization of \(K\) will be \(C_{4a}\)-factors; however, if \(\lambda_1\) is greater than zero but less than its upper bound, then some of the factors in the factorization of \(K\) will be \(C_{4a}\)-factors while others will be \(C_4\)-factors. Specifically, any factor that uses pure edges will be a \(C_{4a}\)-factor while any factor consisting entirely of mixed edges will be a \(C_4\)-factor.
Theorem 2.1. Let \(z = 4a\) where \(a \geq 2\) and \(\lambda_2 > 0\) are even. There exists a \(C_{\{4,4a\}}\)-factorization of \(K = K(a,p; \lambda_1, \lambda_2)\) if and only if
(a) \(p \equiv 0 \ (\mbox{mod } 4)\),
(b) \(\lambda_1\) is even, and
(c) \(\lambda_1 \leq \lambda_2 a (p-1)\).
Proof. The necessity of these conditions follows from Lemmas 1.1 and 1.2. So now assume that \(K\) satisfies conditions (1–3). If \(\lambda_1 = 0\), then the required factorization is given by Theorem 1.5. So we may also assume that \(\lambda_1 > 0\).
Given part size \(a\), there are \(a\) mixed differences, \(0\), \(1\), … \(a-1\), between the levels of the vertices in each part. Given two parts, \(m\) and \(n\), an edge of mixed difference \(0\) would join the vertex on level \(\ell\) in part \(m\) to the vertex on level \(\ell\) in part \(n\). An edge of mixed difference \(d\) would join a vertex on level \(\ell\) in part \(m\) to the vertex on level \((\ell+d) \; (\text{mod } a)\) in part \(n\).
Using Theorem 1.4, let \[\displaystyle \pi = \{ \pi_s \ | \ s \in \mathbb{Z}_{ \lambda_2 (p-1)/2 } \} ,\] be the \(s^{th}\) \(C_4\)-factor of a \(C_4\)-factorization of \(\lambda_2 K_p\). For each \(s \in \mathbb{Z}_{ \lambda_2(p-1)/2 }\), \(d \in \mathbb{Z}_a\), and \(\ell \in \mathbb{Z}_a\), let \[M(s,d,\ell) = \{ ( (\ell,c_1), (\ell+d,c_2), (\ell,c_3), (\ell+d,c_4)) \ | \ (c_1, c_2, c_3, c_4) \in \pi, c_1 < c_2, c_3, c_4 \},\] be a \(4\)-cycle consisting entirely of mixed edges. See Figure 3 for an example.
Then for each \(s \in \mathbb{Z}_{\lambda_2(p-1)/2}\) and for each \(d \in \mathbb{Z}_a\), define the following \(C_4\)-factor of \(K(a,p;0,\lambda_2)\) that consists entirely of mixed edges: \[M(s,d) = \bigcup_{\ell \in \mathbb{Z}_{a}} M(s,d,\ell).\]
Define \[M^+(s,d,\ell) = \{ ( (\ell,c_1), (\ell+d,c_2)), ((\ell,c_3), (\ell+d,c_4)) \ | \ (c_1, c_2, c_3, c_4) \in \pi, c_1 < c_2, c_3, c_4 \},\] and \[M^-(s,d,\ell) = \{ ( (\ell,c_1), (\ell+d,c_4)), ((\ell +d, c_2), (\ell, c_3)) \ | \ (c_1, c_2, c_3, c_4) \in \pi, c_1 < c_2, c_3, c_4 \},\] such that \[M(s,d,\ell) = M^+(s,d,\ell) \cup M^-(s,d,\ell) ,\] and \[M(s,d) = \bigcup_{\ell \in \mathbb{Z}_a} M^+(s,d,\ell) \cup \bigcup_{\ell \in \mathbb{Z}_a} M^-(s,d,\ell) .\]
See Figure 4 for an example of \(M^+(s,d,\ell)\) and \(M^-(s,d,\ell)\).
Notice that these \(C_4\)-factors can be used to produce a \(C_4\)-factorization of \(K(a,p;0,\lambda_2)\), namely: \[\bigcup_{s \in \mathbb{Z}_{\lambda_2(p-1)/2}} \bigcup_{d \in \mathbb{Z}_a} M(s,d).\]
However, we have pure edges to use too, which is accomplished by spreading the edges of the \(4\)-cycles in \(M(s,d)\) among \(a\) \(C_{4a}\)-factors \(p\) edges at a time. Each such \(C_{4a}\)-factor contains \(p\) mixed edges of \(M(s,d)\) for some \(d \in \mathbb{Z}_a\) together with a Hamiltonian path in each part. More specifically, for each \(\ell \in \mathbb{Z}_{a}\) and \(k \in \mathbb{Z}_{p}\), using Lemma 1.3, let \(h_{\ell}(k)\) be the Hamiltonian path of a cyclical, edge-disjoint Hamiltonian path decomposition of \(K_a\) on the vertex set \(\mathbb{Z}_{a} \times \{k\}\) where the ends of the path are \(\ell\) and \(\ell+a/2\) \((\text{mod} \; a)\).
For \(s \in \mathbb{Z}_{ \lambda_2(p-1)/2 }\), \(d \in \mathbb{Z}_a\), and \(\ell \in \mathbb{Z}_a\), let \[\begin{aligned} P(s,d,\ell) &= \{ h_{\ell}(c_1) \cup h_{\ell + d}(c_2) \cup h_{\ell}(c_3) \cup h_{\ell + d}(c_4) \cup M^+(s,d,\ell) \cup M^-(s,d,\ell + a/2) \ | \\ &\phantom{000} (c_1, c_2, c_3, c_4) \in \pi_s, c_1 < c_2, c_3, c_4 \} , \end{aligned}\] be such a \(C_{4a}\)-factor of \(K\); see Figure 5 for an example. Notice that
\[P(s,d) = \bigcup_{ \ell \in \mathbb{Z}_{a} } P(s,d,\ell),\] contains
(a) each pure edge in each part exactly twice, and
(b) precisely the mixed edges in \(M(s,d)\).
Let \(\displaystyle S = \{ (s,d) \ | \ s \in \mathbb{Z}_{\lambda_2 (p – 1)}, d \in \mathbb{Z}_a \}\). Let \(\displaystyle S_1 \subseteq S\) have size \(\displaystyle \frac{\lambda_1}{2}\). Notice that by condition 3. of the theorem, \(\lambda_1 \leq \lambda_2 a (p – 1)\), so \(\displaystyle |S_1| = \frac{\lambda_1}{2} \leq \frac{\lambda_2 a (p – 1)}{2} = |S|\), so such a set \(|S_1|\) exists. Then \[\displaystyle \bigcup_{(s,d) \in S_1} P (s,d) ,\] is a set of \(\displaystyle \frac{\lambda_1 a}{2}\) \(C_{4a}\)-factors that contains each pure edge 2\(|S_1| = \lambda_1\) times by (a), and uses precisely the mixed edges in \[\displaystyle \bigcup_{(s,d) \in S_1} M(s,d),\] by (b). Therefore, the required \(C_{\{4,4a\}}\)-factorization of \(K\) is defined by \[P = \left( \displaystyle \bigcup_{(s,d) \in S_1} P(s,d) \right) \cup \left( \bigcup_{(s,d) \in S \setminus S_1} M(s,d) \right).\]
Notice that \[\begin{aligned} |P| = & a|S_1| + |S \setminus S_1| \\ = & \frac{\lambda_1 a}{2} + \frac{\lambda_2 a (p-1)}{2} – \frac{\lambda_1}{2} \\ = & \frac{\lambda_1 (a-1)}{2} + \frac{\lambda_2 a (p-1)}{2}, \end{aligned}\] as required. ◻