The $\lambda$-fold Spectrum Problem for the Orientations of the 6-Cycle

Adams, Peter; Bunge, Ryan C.; Dulowski, Jordan; El-Zanati, Saad I.; Kenney, Maddillon; Odabası, Ugur; Zale, Kaitlyn

doi:10.61091/jcmcc122-30

Abstract

1. Introduction
2. Examples of Small Designs
3. General Constructions

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 122
Pages: 361-370

Research article

The $λ$ -fold Spectrum Problem for the Orientations of the 6-Cycle

^¹, ^², ^², ^², ^², ^³, ^²

¹The University of Queensland, QLD 4072, Australia

²Illinois State University, Normal, IL 61790-4520, USA

³Istanbul University-Cerrahpasa, Istanbul, 34320, Turkey

Received: 11/05/2020
Accepted: 16/12/2020
Published: 30/09/2024

Copyright Link
License

Abstract

The λ-fold complete symmetric directed graph of order v, denoted ^λK_v^*, is the directed graph on v vertices and λ directed edges in each direction between each pair of vertices. For a given directed graph D, the set of all v for which ^λK_v^* admits a D-decomposition is called the λ-fold spectrum of D. In this paper, we settle the λ-fold spectrum of each of the nine non-isomorphic orientations of a 6-cycle.

Keywords: Spectrum problem, Directed graph, Directed cycl

1. Introduction

If $a$ and $b$ are integers with $a \leq b$ , we let $[a, b]$ denote the set ${a, a + 1, \dots, b}$ . For a graph (or directed graph) $D$ , we use $V (D)$ and $E (D)$ to denote the vertex set of $D$ and the edge set (or arc set) of $D$ , respectively. Furthermore, we use $^{λ} D$ to denote the multigraph (or directed multigraph) with vertex set $V (D)$ and $λ$ copies of each edge (or arc) in $E (D)$ . For a simple graph $G$ , we use $G^{*}$ to denote the symmetric digraph with vertex set $V (G^{*}) = V (G)$ and arc set $E (G^{*}) = ⋃_{{u, v} \in E (G)} {(u, v), (v, u)}$ . Hence, $^{λ} K_{v}^{*}$ is the $λ$ -fold complete symmetric directed graph of order $v$ .

A decomposition of a directed multigraph $K$ is a collection $Δ = {D_{1}, D_{2}, \dots, D_{t}}$ of subgraphs of $K$ such that each directed edge, or arc, of $K$ appears in exactly one $D_{i} \in Δ$ . If each $D_{i}$ in $Δ$ is isomorphic to a given digraph $D$ , the decomposition is called a $D$ -decomposition of $K$ . A $D$ -decomposition of $K$ is also known as a $(K, D)$ -design. The set of all $v$ for which $K_{v}^{*}$ admits a $D$ -decomposition is called the spectrum of $D$ . Similarly, the set of all $v$ for which ${^{λ} K}_{v}^{*}$ admits a $D$ -decomposition is called the $λ$ -fold spectrum of $D$ .

The reverse orientation of $D$ , denoted $R e v D$ , is the digraph with vertex set $V (D)$ and arc set ${(v, u) : (u, v) \in E (D)}$ . We note that the existence of a $D$ -decomposition of $K$ necessarily implies the existence of a $R e v D$ -decomposition of $R e v K$ . Since $K_{v}^{*}$ is its own reverse orientation, we note that the spectrum of $D$ is equal to the spectrum of $R e v D$ .

The necessary conditions for a digraph $D$ to decompose ${^{λ} K}_{v}^{*}$ include

(a) ] $| V (D) | \leq v$ ,
(b) ] $| E (D) |$ divides $λ v (v - 1)$ , and
(c) ] $gcd {o u t d e g r e e (x) : x \in V (D)}$ and $gcd {i n d e g r e e (x) : x \in V (D)}$ both divide $λ (v - 1)$ .

The spectrum problem for certain subgraphs (both bipartite and non-bipartite) of $K_{4}^{*}$ has already been studied. When $D$ is a cyclic orientation of $K_{3}$ , then a $(K_{v}^{*}, D)$ -design is known as a Mendelsohn triple system. The spectrum for Mendelsohn triple systems was found independently by Mendelsohn [1]and Bermond [2]. When $D$ is a transitive orientation of $K_{3}$ , then a $(K_{v}^{*}, D)$ -design is known as a transitive triple system. The spectrum for transitive triple systems was found by Hung and Mendelsohn [3]. There are exactly four orientations of a 4-cycle (i.e., a quadrilateral). It was shown in [4]that if $D$ is a cyclic orientation of a 4-cycle, then a $(K_{v}^{*}, D)$ -design exists if and only if $v \equiv 0$ or $1 (\mod 4)$ and $v \neq 4$ . The spectrum problem for the remaining three orientations of a 4-cycle were setled in [5]. In [6], Alspach et al. showed that $K_{v}^{*}$ can be decomposed into each of the four orientations of a $5$ -cycle (i.e., a pentagon) if and only if $v \equiv 0$ or $1 (\mod 5)$ . In [7], it is shown that for positive integers $m$ and $v$ with $2 \leq m \leq v$ the directed graph $K_{v}^{*}$ can be decomposed into directed cycles (i.e., with all the edges being oriented in the same direction) of length $m$ if and only if $m$ divides the number of arcs in $K_{v}^{*}$ and $(v, m) \notin {(4, 4), (6, 3), (6, 6)}$ . Also recently [8], Odabaşı settled the spectrum problem for all possible orientations of a $7$ -cycle.

There are nine non-isomorphic orientations of a $6$ -cycle. We denote these with $D_{1}$ , $D_{2}$ , …, $D_{9}$ as seen in Figure 1. The $λ$ -fold spectrum problem was settled for the directed $6$ -cycle (i.e., $D_{1}$ ) in [9]. In this work, we settle this problem for the remaining eight orientations. Our main result, which is proved in Section 3, is as follows.

Theorem 1. Let $D$ be an orientation of a $6$ -cycle and let $λ$ and $v$ be positive integers such that $v \geq 6$ . There exists a $D$ -decomposition of $^{λ} K_{v}^{*}$ if and only if $λ v (v - 1) \equiv 0 (\mod 3)$ and neither of the following hold

$(D, λ, v) = (D_{1}, 1, 6)$ or
$D = D_{9}$ and $λ (v - 1)$ is odd.

From the necessary conditions stated earlier, we have the following.

Lemma 1. Let $D \in {D_{2}, D_{3}, \dots, D_{8}}$ and let $λ$ and $v$ be positive integers such that $v \geq 6$ . There exists a $D$ -decomposition of $^{λ} K_{v}^{*}$ only if $λ v (v - 1) \equiv 0 (\mod 3)$ . Furthermore, there exists a $D_{9}$ -decomposition of $^{λ} K_{v}^{*}$ only if $λ v (v - 1) \equiv 0 (\mod 3)$ and $λ (v - 1) \equiv 0 (\mod 2)$ .

In 1978, Bermond, Huang, and Sotteau [9]showed that with the exception that there is no $D_{1}$ -decomposition of $K_{6}^{*}$ , these necessary conditions are sufficient for $D_{1}$ .

Theorem 2. For integers $v \geq 6$ and $λ \geq 1$ , there exists a $D_{1}$ -decomposition of ${^{λ} K}_{v}^{*}$ if and only if $λ v (v - 1) \equiv 0 (\mod 6)$ and $(λ, v) \neq (1, 6)$ .

The remainder of this paper is dedicated to establishing sufficiency of the above necessary conditions. We achieve this by exhibiting constructions for the desired decompositions (see Section 3) using certain small examples (see Section 2). Henceforth, each of the graphs in Figure 1, with vertices labeled as in the figure, will be represented by $D_{i} [v_{1}, v_{1}, \dots, v_{6}]$ .

Figure 1 The Nine Orientations of a $6$ -cycle

For $m \geq 2$ , the following result of Sotteau proves the existence of $2 m$ -cycle decompositions of complete bipartite graphs.

Theorem 3 ([10]). Let $x$ , $y$ , and $m$ be positive integers such that $m \geq 2$ . There exists a $2 m$ -cycle decomposition of $K_{2 x, 2 y}$ if and only if $m ∣ 2 x y$ and $min {2 x, 2 y} \geq m$ .

Consider an orientation of a 6-cycle that is isomorphic to its own reverse, i.e. any $D_{i}$ in Figure 1 such that $i \notin {7, 8}$ . By definition of reverse orientation, the set ${D_{i}, R e v D_{i}}$ is an obvious $D_{i}$ -decomposition of $C_{6}^{*}$ (the symmetric digraph with a 6-cycle as the underlying simple graph). Since a $G$ -decomposition of a graph $K$ necessarily implies a $G^{*}$ -decomposition of the digraph $K^{*}$ , we get the following corollary from the case $m = 3$ in Theorem 3.

Corollary 1. Let $D \in {D_{1}, D_{2}, D_{3}, D_{4}, D_{5}, D_{6}, D_{9}}$ . There exists a $D$ -decomposition of $K_{2 x, 2 y}^{*}$ if $3 ∣ x y$ and $min {x, y} \geq 2$ .

2. Examples of Small Designs

We first present several $D_{i}$ -decompositions of various graphs for $i \in [2, 9]$ . Beyond establishing existence of necessary base cases, these decompositions are used extensively in the general constructions seen in Section 3.

If $i, v_{1}, v_{2}, \dots, v_{6}$ are integers and $D \in {D_{1}, D_{2}, \dots, D_{9}}$ , we define $D [v_{1}, v_{2}, \dots, v_{6}] + i$ to indicate $D [v_{1} + i, $ $ v_{2} + i, $ $ \dots, $ $ v_{6} + i]$ . Similarly, if the vertices of $D$ are ordered pairs in $Z_{m} \times Z_{n}$ , then $D [(u_{1}, v_{1}), $ $ (u_{2}, v_{2}), $ $ \dots, $ $ (u_{6}, v_{6})] + (i, 0)$ means the digraph $D [(u_{1} + i, v_{1}), $ $ (u_{2} + i, v_{2}), $ $ \dots, $ $ (u_{6} + i, v_{6})]$ . We also use the convention that both $\infty + i$ and $\infty + (i, 0)$ result in simply $\infty$ .

Example 1. Let $V (K_{6}^{*}) = Z_{5} \cup {\infty}$ and let $\begin{aligned} Δ_{2} = { & D_{2} [0, 3, 4, 2, 1, \infty] + i : i \in Z_{5}}, \\ * Δ_{3} = { & D_{3} [0, 4, 1, 3, 2, \infty] + i : i \in Z_{5}}, \\ Δ_{4} = { & D_{4} [0, 1, 2, 4, \infty, 3] + i : i \in Z_{5}}, \\ Δ_{5} = { & D_{5} [0, 1, 3, 2, \infty, 4], D_{5} [1, 3, 4, \infty, 2, 0], D_{5} [2, 4, 1, \infty, 3, 0], \\ * & D_{5} [4, 1, 2, 3, \infty, 0], D_{5} [3, 0, \infty, 1, 2, 4]}, \\ Δ_{6} = { & D_{6} [0, 1, 3, 2, 4, \infty] + i : i \in Z_{5}}, \\ Δ_{7} = { & D_{7} [0, 1, 3, 4, 2, \infty] + i : i \in Z_{5}}, \\ * Δ_{8} = { & D_{8} [0, \infty, 1, 3, 2, 4] + i : i \in Z_{5}} . \end{aligned}$ Then $Δ_{i}$ is a $D_{i}$ -decomposition of $K_{6}^{*}$ for $i \in [2, 8]$ .

Example 2. Let $V ({^{2} K^{*}}_{6}) = Z_{5} \cup {\infty}$ and let $Δ_{9} = ⋃_{i \in Z_{5}} {D_{9} [0, 1, 2, 3, 4, \infty] + i, D_{9} [\infty, 0, 2, 4, 1, 3] + i} .$ Then $Δ_{9}$ is a $D_{9}$ -decomposition of ${^{2} K^{*}}_{6}$ .

Example 3. Let $V (K_{7}^{*}) = Z_{7}$ and let $\begin{aligned} Δ_{2} = { & D_{2} [0, 1, 4, 6, 5, 2], D_{2} [0, 4, 1, 5, 3, 6], D_{2} [0, 5, 4, 2, 6, 3], \\ * & D_{2} [1, 6, 4, 3, 2, 5], D_{2} [4, 0, 3, 1, 6, 2], D_{2} [5, 0, 1, 2, 3, 4], \\ * & D_{2} [6, 0, 2, 1, 3, 5]}, \\ Δ_{3} = { & D_{3} [3, 1, 0, 6, 2, 4], D_{3} [4, 5, 1, 0, 3, 6], D_{3} [2, 0, 6, 5, 3, 1], \\ * & D_{3} [1, 6, 5, 2, 0, 4], D_{3} [0, 5, 4, 2, 6, 3], D_{3} [5, 3, 2, 1, 4, 0], \\ * & D_{3} [6, 4, 3, 2, 5, 1]}, \\ Δ_{4} = { & D_{4} [0, 1, 3, 2, 6, 4] + i : i \in Z_{7}}, \\ Δ_{5} = { & D_{5} [0, 1, 3, 6, 5, 2] + i : i \in Z_{7}}, \\ Δ_{6} = { & D_{6} [0, 1, 2, 3, 4, 5], D_{6} [0, 2, 1, 3, 5, 6], D_{6} [0, 3, 1, 6, 2, 4], \\ * & D_{6} [3, 2, 4, 5, 1, 6], D_{6} [3, 4, 6, 0, 2, 5], D_{6} [5, 1, 4, 0, 3, 6], \\ * & D_{6} [6, 2, 5, 0, 1, 4]}, \\ Δ_{7} = { & D_{7} [0, 1, 3, 5, 2, 6] + i : i \in Z_{7}}, \\ Δ_{8} = { & D_{8} [0, 6, 2, 5, 3, 1] + i : i \in Z_{7}}, \\ * Δ_{9} = { & D_{9} [0, 1, 2, 4, 6, 3] + i : i \in Z_{7}} . \end{aligned}$ Then $Δ_{i}$ is a $D_{i}$ -decomposition of $K_{7}^{*}$ for $i \in [2, 9]$ .

Example 4. Let $V ({^{3} K^{*}}_{8}) = Z_{7} \cup {\infty}$ and let $\begin{aligned} D_{1} [0, 1, 2, 3, 5, 4], D_{1} [0, 2, 1, 3, 6, \infty], D_{1} [0, 3, 1, 5, 2, \infty], \\ Δ_{2} = ⋃_{i \in Z_{7}} { & D_{2} [0, 1, 2, 3, 5, 4] + i, D_{2} [0, 2, 1, 3, 6, \infty] + i, \\ * & D_{2} [0, 3, 1, 5, 2, \infty] + i, D_{2} [0, 4, 2, 3, 5, \infty] + i}, \\ Δ_{3} = ⋃_{i \in Z_{7}} { & D_{3} [0, 1, 2, 3, 5, 6] + i, D_{3} [0, 2, 3, 5, 1, \infty] + i, \\ * & D_{3} [0, 3, 1, 6, 4, \infty] + i, D_{3} [0, 4, 1, 5, 2, \infty] + i}, \\ Δ_{4} = ⋃_{i \in Z_{7}} { & D_{4} [0, 1, 2, 3, 5, 6] + i, D_{4} [0, 2, 1, 3, 6, \infty] + i, \\ * & D_{4} [0, 3, 1, 5, 2, \infty] + i, D_{4} [0, 5, 2, 6, 1, \infty] + i}, \\ Δ_{5} = ⋃_{i \in Z_{7}} { & D_{5} [0, 1, 2, 3, 5, 4] + i, D_{5} [0, 2, 1, 3, 6, \infty] + i, \\ * & D_{5} [0, 3, 5, 2, 6, \infty] + i, D_{5} [0, 4, 6, 3, 2, \infty] + i}, \\ Δ_{6} = ⋃_{i \in Z_{7}} { & D_{6} [0, 1, 2, 3, 4, 5] + i, D_{6} [0, 2, 4, 3, 6, \infty] + i, \\ * & D_{6} [0, 3, 5, 2, 6, \infty] + i, D_{6} [0, 4, 2, 5, 1, \infty] + i}, \\ Δ_{7} = ⋃_{i \in Z_{7}} { & D_{7} [0, 1, 2, 3, 5, 6] + i, D_{7} [0, 2, 3, 5, 1, \infty] + i, \\ * & D_{7} [0, 3, 1, 2, 4, \infty] + i, D_{7} [0, 4, 1, 5, 2, \infty] + i}, \\ Δ_{8} = ⋃_{i \in Z_{7}} { & D_{8} [0, 1, 2, 3, 4, 5] + i, D_{8} [0, 2, 6, \infty, 4, 3] + i, \\ * & D_{8} [0, 3, 1, \infty, 5, 2] + i, D_{8} [0, 3, 1, \infty, 5, 2] + i} . \end{aligned}$ Then $Δ_{i}$ is a $D_{i}$ -decomposition of ${^{3} K^{*}}_{8}$ for $i \in [2, 8]$ .

Example 5. Let $V ({^{6} K^{*}}_{8}) = Z_{7} \cup {\infty}$ and let $\begin{aligned} Δ_{9} = ⋃_{i \in Z_{7}} { & D_{9} [0, 1, 2, 3, 4, 5] + i, D_{9} [0, 1, 2, 3, 4, 5] + i, \\ * & D_{9} [0, 2, 6, 3, \infty, 5] + i, D_{9} [0, 2, 6, 3, \infty, 5] + i, \\ D_{9} [0, 2, 6, 3, \infty, 5] + i, D_{9} [0, 3, 1, 6, 2, \infty] + i, \\ * & D_{9} [0, 3, 1, 5, 6, \infty] + i, D_{9} [0, 3, 1, 5, 6, \infty] + i} . \end{aligned}$ Then $Δ_{9}$ is a $D_{9}$ -decomposition of ${^{6} K^{*}}_{8}$ .

Example 6. Let $V (K_{9}^{*}) = (Z_{4} \times Z_{2}) \cup {\infty}$ . For brevity we use $i_{j}$ to denote the ordered pair $(i, j) \in V (K_{9}^{*})$ , and we (continue to) use the convention that $\infty + i_{0} = \infty$ . Let $\begin{aligned} Δ_{2} = ⋃_{i \in Z_{4}} { & D_{2} [0_{0}, 3_{0}, \infty, 3_{1}, 1_{1}, 1_{0}] + i_{0}, D_{2} [0_{0}, 2_{0}, 3_{1}, \infty, 3_{0}, 2_{1}] + i_{0}, \\ * & D_{2} [0_{1}, 3_{1}, 2_{1}, 1_{0}, 1_{1}, 2_{0}] + i_{0}}, \\ Δ_{3} = ⋃_{i \in Z_{4}} { & D_{3} [0_{0}, 3_{1}, 0_{1}, 3_{0}, 2_{1}, \infty] + i_{0}, D_{3} [0_{0}, 2_{0}, 1_{0}, \infty, 3_{1}, 0_{1}] + i_{0}, \\ * & D_{3} [0_{1}, 2_{0}, 3_{0}, 3_{1}, 1_{0}, 2_{1}] + i_{0}}, \\ Δ_{4} = ⋃_{i \in Z_{4}} { & D_{4} [0_{0}, 3_{0}, 2_{0}, 0_{1}, 1_{1}, 3_{1}] + i_{0}, D_{4} [0_{1}, 3_{0}, 1_{0}, \infty, 1_{1}, 0_{0}] + i_{0}, \\ * & D_{4} [0_{1}, 1_{1}, \infty, 3_{0}, 2_{1}, 2_{0}] + i_{0}}, \\ Δ_{5} = ⋃_{i \in Z_{4}} { & D_{5} [0_{0}, 3_{0}, 0_{1}, 2_{0}, 2_{1}, 3_{1}] + i_{0}, D_{5} [0_{0}, 2_{0}, 1_{0}, 1_{1}, 2_{1}, \infty] + i_{0}, \\ * & D_{5} [0_{1}, 2_{1}, 1_{0}, 3_{1}, 0_{0}, \infty] + i_{0}}, \\ Δ_{6} = ⋃_{i \in Z_{4}} { & D_{6} [0_{0}, 1_{1}, 2_{0}, \infty, 2_{1}, 3_{1}] + i_{0}, D_{6} [\infty, 3_{0}, 0_{0}, 0_{1}, 2_{0}, 3_{1}] + i_{0}, \\ * & D_{6} [0_{1}, 0_{0}, 2_{0}, 1_{0}, 3_{1}, 1_{1}] + i_{0}}, \\ Δ_{7} = ⋃_{i \in Z_{4}} { & D_{7} [0_{0}, 3_{0}, 0_{1}, 2_{0}, 2_{1}, 3_{1}] + i_{0}, D_{7} [0_{0}, 2_{0}, 3_{0}, 3_{1}, 0_{1}, \infty] + i_{0}, \\ * & D_{7} [0_{1}, 2_{1}, 1_{0}, 3_{1}, 0_{0}, \infty] + i_{0}}, \\ Δ_{8} = ⋃_{i \in Z_{4}} { & D_{8} [0_{0}, \infty, 0_{1}, 2_{1}, 1_{0}, 3_{1}] + i_{0}, D_{8} [0_{1}, 3_{0}, 0_{0}, 3_{1}, 2_{1}, 2_{0}] + i_{0}, \\ * & D_{8} [0_{1}, \infty, 0_{0}, 2_{0}, 3_{0}, 3_{1}] + i_{0}}, \\ Δ_{9} = ⋃_{i \in Z_{4}} { & D_{9} [0_{0}, \infty, 2_{1}, 3_{0}, 0_{1}, 3_{1}] + i_{0}, D_{9} [0_{0}, 3_{0}, 1_{1}, 3_{1}, 2_{0}, 0_{1}] + i_{0}, \\ * & D_{9} [0_{1}, 0_{0}, 3_{0}, 1_{0}, \infty, 1_{1}] + i_{0}} . \end{aligned}$ Then $Δ_{i}$ is a $D_{i}$ -decomposition of $K_{9}^{*}$ for $i \in [2, 9]$ .

Example 7. Let $V (K_{10}^{*}) = Z_{5} \times Z_{2}$ . For brevity we use $i_{j}$ to denote the ordered pair $(i, j) \in V (K_{10}^{*})$ . Let $\begin{aligned} Δ_{2} = ⋃_{i \in Z_{5}} { & D_{2} [0_{0}, 1_{1}, 1_{0}, 0_{1}, 4_{1}, 2_{1}] + i_{0}, D_{2} [0_{0}, 1_{0}, 4_{1}, 1_{1}, 2_{1}, 3_{0}] + i_{0}, \\ * & D_{2} [0_{1}, 3_{0}, 1_{0}, 2_{1}, 4_{0}, 0_{0}] + i_{0}}, \\ Δ_{3} = ⋃_{i \in Z_{5}} { & D_{3} [0_{0}, 4_{1}, 1_{1}, 2_{1}, 1_{0}, 4_{0}] + i_{0}, D_{3} [0_{1}, 0_{0}, 1_{0}, 3_{0}, 4_{1}, 1_{1}] + i_{0}, \\ * & D_{3} [0_{1}, 1_{0}, 3_{1}, 0_{0}, 2_{1}, 2_{0}] + i_{0}}, \\ Δ_{4} = ⋃_{i \in Z_{5}} { & D_{4} [0_{0}, 4_{1}, 0_{1}, 2_{0}, 1_{1}, 3_{0}] + i_{0}, D_{4} [0_{0}, 2_{0}, 3_{1}, 3_{0}, 0_{1}, 2_{1}] + i_{0}, \\ * & D_{4} [0_{0}, 1_{0}, 2_{0}, 3_{1}, 2_{1}, 0_{1}] + i_{0}}, \\ Δ_{5} = ⋃_{i \in Z_{5}} { & D_{5} [0_{0}, 4_{0}, 2_{0}, 3_{1}, 4_{1}, 2_{1}] + i_{0}, D_{5} [0_{0}, 3_{0}, 2_{1}, 3_{1}, 1_{1}, 1_{0}] + i_{0}, \\ * & D_{5} [0_{0}, 4_{1}, 3_{0}, 1_{1}, 1_{0}, 3_{1}] + i_{0}}, \\ Δ_{6} = ⋃_{i \in Z_{5}} { & D_{6} [0_{0}, 4_{0}, 2_{1}, 1_{0}, 3_{0}, 0_{1}] + i_{0}, D_{6} [0_{0}, 1_{1}, 1_{0}, 0_{1}, 4_{1}, 2_{1}] + i_{0}, \\ * & D_{6} [0_{1}, 4_{1}, 2_{1}, 4_{0}, 3_{0}, 1_{0}] + i_{0}}, \\ Δ_{7} = ⋃_{i \in Z_{5}} { & D_{7} [0_{0}, 1_{0}, 0_{1}, 3_{1}, 4_{1}, 3_{0}] + i_{0}, D_{7} [0_{0}, 2_{1}, 3_{0}, 0_{1}, 2_{0}, 3_{1}] + i_{0}, \\ * & D_{7} [0_{0}, 0_{1}, 4_{1}, 1_{1}, 1_{0}, 4_{0}] + i_{0}}, \\ Δ_{8} = ⋃_{i \in Z_{5}} { & D_{8} [0_{0}, 1_{0}, 1_{1}, 0_{1}, 2_{1}, 2_{0}] + i_{0}, D_{8} [0_{0}, 4_{1}, 1_{1}, 2_{1}, 1_{0}, 4_{0}] + i_{0}, \\ * & D_{8} [0_{1}, 4_{0}, 2_{1}, 0_{0}, 4_{1}, 2_{0}] + i_{0}} . \end{aligned}$ Then $Δ_{i}$ is a $D_{i}$ -decomposition of $K_{10}^{*}$ for $i \in [2, 8]$ .

Example 8. Let $V ({^{2} K^{*}}_{10}) = Z_{10}$ and let $\begin{aligned} Δ_{9} = ⋃_{i \in Z_{10}} { & D_{9} [0, 4, 8, 7, 9, 1] + i, D_{9} [0, 5, 2, 3, 1, 4] + i, \\ * & D_{9} [0, 9, 2, 7, 1, 8] + i} . \end{aligned}$ Then $Δ_{9}$ is a $D_{9}$ -decomposition of ${^{2} K^{*}}_{10}$ .

Example 9. Let $V ({^{3} K^{*}}_{11}) = Z_{11}$ and let $\begin{aligned} Δ_{2} = ⋃_{i \in Z_{11}} { & D_{2} [0, 5, 1, 2, 4, 7] + i, D_{2} [0, 5, 1, 2, 4, 7] + i, \\ * & D_{2} [0, 6, 1, 2, 4, 7] + i, D_{2} [0, 2, 1, 10, 9, 3] + i, \\ * & D_{2} [0, 4, 1, 6, 3, 2] + i}, \\ Δ_{3} = ⋃_{i \in Z_{11}} { & D_{3} [0, 2, 1, 3, 6, 5] + i, D_{3} [0, 2, 1, 3, 6, 5] + i, \\ * & D_{3} [0, 2, 1, 5, 9, 3] + i, D_{3} [0, 1, 7, 2, 10, 6] + i, \\ * & D_{3} [0, 3, 1, 8, 4, 7] + i}, \\ Δ_{4} = ⋃_{i \in Z_{11}} { & D_{4} [0, 1, 7, 10, 2, 6] + i, D_{4} [0, 1, 7, 10, 2, 6] + i, \\ * & D_{4} [0, 1, 7, 10, 2, 6] + i, D_{4} [0, 4, 6, 10, 1, 2] + i, \\ * & D_{4} [0, 9, 10, 3, 1, 2] + i}, \\ Δ_{5} = ⋃_{i \in Z_{11}} { & D_{5} [0, 1, 2, 5, 10, 4] + i, D_{5} [0, 1, 2, 5, 10, 4] + i, \\ * & D_{5} [0, 1, 2, 5, 10, 4] + i, D_{5} [0, 2, 4, 1, 3, 7] + i, \\ * & D_{5} [0, 2, 4, 1, 10, 3] + i}, \\ Δ_{6} = ⋃_{i \in Z_{11}} { & D_{6} [0, 1, 3, 6, 10, 4] + i, D_{6} [0, 1, 3, 6, 10, 4] + i, \\ * & D_{6} [0, 1, 3, 6, 10, 4] + i, D_{6} [0, 5, 3, 2, 4, 10] + i, \\ * & D_{6} [0, 10, 4, 2, 5, 8] + i}, \\ Δ_{7} = ⋃_{i \in Z_{11}} { & D_{7} [0, 1, 3, 6, 10, 7] + i, D_{7} [0, 1, 3, 6, 10, 7] + i, \\ * & D_{7} [0, 1, 3, 6, 10, 7] + i, D_{7} [0, 6, 5, 10, 4, 9] + i, \\ * & D_{7} [0, 10, 4, 5, 3, 9] + i}, \\ Δ_{8} = ⋃_{i \in Z_{11}} { & D_{8} [0, 1, 3, 6, 2, 5] + i, D_{8} [0, 1, 3, 6, 2, 5] + i, \\ * & D_{8} [0, 1, 3, 6, 2, 5] + i, D_{8} [0, 6, 4, 8, 10, 9] + i, \\ * & D_{8} [0, 6, 5, 9, 3, 10] + i}, \\ Δ_{9} = ⋃_{i \in Z_{11}} { & D_{9} [0, 1, 2, 4, 6, 3] + i, D_{9} [0, 1, 2, 4, 6, 3] + i, \\ * & D_{9} [0, 1, 2, 4, 6, 3] + i, D_{9} [0, 5, 1, 8, 2, 6] + i, \\ * & D_{9} [0, 5, 1, 8, 2, 7] + i} . \end{aligned}$ Then $Δ_{i}$ is a $D_{i}$ -decomposition of ${^{3} K^{*}}_{11}$ for $i \in [2, 9]$ .

Example 10. Let $V (K_{3, 4}^{*}) = Z_{7}$ with vertex partition ${{0, 1, 2}, $ $ {3, 4, 5, 6}}$ and let $\begin{aligned} Δ_{7} = { & D_{7} [0, 3, 1, 4, 2, 6], D_{7} [3, 0, 5, 1, 6, 2], D_{7} [2, 5, 1, 6, 0, 4], \\ * & D_{7} [5, 2, 3, 1, 4, 0]}, \\ Δ_{8} = { & D_{8} [0, 4, 2, 5, 1, 6], D_{8} [3, 2, 5, 0, 4, 1], D_{8} [1, 3, 0, 6, 2, 4], \\ * & D_{8} [6, 2, 3, 0, 5, 1]} . \end{aligned}$ Then $Δ_{i}$ is a $D_{i}$ -decomposition of $K_{3, 4}^{*}$ for $i \in {7, 8}$ .

Example 11. Let $V (K_{6, 6}^{*}) = Z_{6} \times Z_{2}$ with the obvious vertex bipartition. For brevity we use $i_{j}$ to denote the ordered pair $(i, j) \in V (K_{6, 6}^{*})$ . Let $\begin{aligned} Δ_{7} = ⋃_{i \in Z_{6}} { & D_{7} [0_{0}, 5_{1}, 1_{0}, 1_{1}, 5_{0}, 2_{1}] + i_{0}, D_{7} [0_{1}, 5_{0}, 3_{1}, 0_{0}, 1_{1}, 1_{0}] + i_{0}}, \\ Δ_{8} = ⋃_{i \in Z_{6}} { & D_{8} [0_{0}, 4_{1}, 5_{0}, 1_{1}, 4_{0}, 0_{1}] + i_{0}, D_{8} [0_{1}, 0_{0}, 5_{1}, 4_{0}, 2_{1}, 5_{0}] + i_{0}} . \end{aligned}$ Then $Δ_{i}$ is a $D_{i}$ -decomposition of $K_{6, 6}^{*}$ for $i \in {7, 8}$ .

3. General Constructions

For two edge-disjoint graphs (or digraphs) $G$ and $H$ , we use $G \cup H$ to denote the graph (or digraph) with vertex set $V (G) \cup V (H)$ and edge (or arc) set $E (G) \cup E (H)$ . Furthermore, given a positive integer $x$ , we use $x G$ to denote the edge-disjoint union of $x$ copies of $G$ , which are not necessarily vertex-joint. If $G$ and $H$ are vertex-disjoint, then we use $G \lor H$ to denote the join of $G$ and $H$ , which has vertex set $V (G) \cup V (H)$ and edge (or arc) set $E (G) \cup E (H) \cup {{u, v} : u \in V (G), v \in V (H)}$ . To illustrate the different types of notation described here, consider that $K_{13}$ can be viewed as $(K_{6} \cup K_{6}) \lor K_{1} \cup K_{6, 6} = K_{7} \cup K_{7} \cup K_{6, 6}$ . (Note that the join precedes the union in the order of operations.)

We first prove a result about decompositions of $K_{4, 6}^{*}$ , $K_{6, 6}^{*}$ , and $K_{6, 8}^{*}$ .

Lemma 2. For $D \in {D_{2}, D_{3}, \dots, D_{9}}$ , then there exists a $D$ -decomposition of $K_{4, 6}^{*}$ , $K_{6, 6}^{*}$ and $K_{6, 8}^{*}$ .

Proof. Let $D \in {D_{2}, D_{3}, \dots, D_{9}}$ . The result follows from Corollary 1 for $D \notin {D_{7}, D_{8}}$ . For $i \in {7, 8}$ , a $D_{i}$ -decomposition of $K_{3, 4}^{*}$ (and hence of $K_{6, 4}^{*}$ and $K_{6, 8}^{*}$ ) exists by Example 10. Moreover, $D_{7}$ – and $D_{8}$ -decompositions of $K_{6, 6}^{*}$ are given in Example 11.

We now give our constructions for decompositions of $^{λ} K_{v}^{*}$ in the following lemmas, which cover values of $v$ working modulo $6$ . The main result is summarized in Theorem 4.

Lemma 3. Let $λ$ and $v$ be positive integers such that $v \equiv 0 (\mod 6)$ . If $D \in {D_{2}, D_{3}, \dots, D_{8}}$ , then there exists a $D$ -decomposition of $^{λ} K_{v}^{*}$ . Furthermore, if $λ$ is even, then there exists a $D_{9}$ -decomposition of $^{λ} K_{v}^{*}$ .

Proof. Let $D \in {D_{2}, D_{3}, \dots, D_{9}}$ . If $v = 6$ and $D \neq D_{9}$ , then the result follows from $λ$ copies of a $D$ -decomposition of $K_{6}^{*}$ (see Example 1). If $v = 6$ , $λ$ is even, and $D = D_{9}$ , then the result follows from $λ / 2$ copies of a $D_{9}$ -decomposition of ${^{2} K^{*}}_{6}$ (see Example 2). For the remainder of the proof, we let $v = 6 x$ for some integer $x \geq 2$ , and we assume $λ$ is even whenever $D = D_{9}$ . Finally,

we note that $K_{6 x} = x K_{6} \cup (\binom{x}{2}) K_{6, 6}$ . Thus ${^{λ} K^{*}}_{6 x} = x ({^{λ} K^{*}}_{6}) \cup (\binom{x}{2}) ({^{λ} K^{*}}_{6, 6})$ , and the result follows from the existence of $D$ -decompositions of ${^{λ} K^{*}}_{6}$ and ${^{λ} K^{*}}_{6, 6}$ , where the latter decomposition follows from $λ$ copies of a $D$ -decomposition of $K_{6, 6}^{*}$ (see Lemma 2).

Lemma 4. Let $λ$ and $v$ be positive integers such that $v \equiv 1 (\mod 6)$ and $v \geq 7$ . If $D \in {D_{2}, D_{3}, \dots, D_{9}}$ , then there exists a $D$ -decomposition of $^{λ} K_{v}^{*}$ .

Proof. If $v = 7$ , then the result follows from $λ$ copies of a $D$ -decomposition of $K_{7}^{*}$ (see Example 3). For the remainder of the proof, we let $v = 6 x + 1$ for some integer $x \geq 2$ . We note that $K_{6 x + 1} = (x K_{6}) \lor K_{1} \cup (\binom{x}{2}) K_{6, 6} = x K_{7} \cup (\binom{x}{2}) K_{6, 6}$ . Thus ${^{λ} K^{*}}_{6 x + 1} = x ({^{λ} K^{*}}_{7}) \cup (\binom{x}{2}) ({^{λ} K^{*}}_{6, 6})$ , and the result follows from the existence of $D$ -decompositions of ${^{λ} K^{*}}_{7}$ and ${^{λ} K^{*}}_{6, 6}$ .

Lemma 5. Let $λ$ and $v$ be positive integers such that $λ \equiv 0 (\mod 3)$ , $v \equiv 2 (\mod 6)$ , and $v \geq 8$ . If $D \in {D_{2}, D_{3}, \dots, D_{8}}$ , then there exists a $D$ -decomposition of $^{λ} K_{v}^{*}$ . Furthermore, if $λ \equiv 0 (\mod 6)$ , then there exists a $D_{9}$ -decomposition of $^{λ} K_{v}^{*}$ .

Proof. Let $D \in {D_{2}, D_{3}, \dots, D_{9}}$ . If $v = 8$ and $D \neq D_{9}$ , then the result follows from $λ / 3$ copies of a $D$ -decomposition of ${^{3} K^{*}}_{8}$ (see Example 4). If $v = 8$ , $λ \equiv 0 (\mod 6)$ , and $D = D_{9}$ , then the result follows from $λ / 6$ copies of a $D_{9}$ -decomposition of ${^{6} K^{*}}_{8}$ (see Example 5).

Next, for $v = 14$ , we note that ${^{λ} K^{*}}_{14} = {^{λ} K^{*}}_{8} \cup {^{λ} K^{*}}_{6} \cup {^{λ} K^{*}}_{8, 6}$ . Thus the result follows from the existence of $D$ -decompositions of ${^{λ} K^{*}}_{8}$ , ${^{λ} K^{*}}_{6}$ and and ${^{λ} K^{*}}_{8, 6}$ .

For the remainder of the proof, we let $v = 6 x + 8$ for some integer $x \geq 2$ and $λ = 3 y$ for some integer $y \geq 1$ , and we assume $y$ is even whenever $D = D_{9}$ . Finally, we note that $K_{6 x + 8} = K_{8} \cup x K_{6} \cup x K_{8, 6} \cup (\binom{x}{2}) K_{6, 6}$ . Thus ${^{λ} K^{*}}_{6 x + 8} = {^{λ} K^{*}}_{8} \cup x ({^{λ} K^{*}}_{6}) \cup x ({^{λ} K^{*}}_{8, 6}) \cup (\binom{x}{2}) ({^{λ} K^{*}}_{6, 6})$ , and the result follows from the existence of $D$ -decompositions of ${^{λ} K^{*}}_{8}$ , ${^{λ} K^{*}}_{6}$ , ${^{λ} K^{*}}_{8, 6}$ , and ${^{λ} K^{*}}_{6, 6}$ .

Lemma 6. Let $λ$ and $v$ be positive integers such that $v \equiv 3 (\mod 6)$ and $v \geq 9$ . If $D \in {D_{2}, D_{3}, \dots, D_{9}}$ , then there exists a $D$ -decomposition of $^{λ} K_{v}^{*}$ .

Proof. If $v = 9$ , then the result follows from $λ$ copies of a $D$ -decomposition of $K_{9}^{*}$ (see Example 6). For $v = 15$ , we note that ${^{λ} K^{*}}_{15} = ({^{λ} K^{*}}_{8} \cup {^{λ} K^{*}}_{6}) \lor {^{λ} K^{*}}_{1} \cup {^{λ} K^{*}}_{8, 6} = {^{λ} K^{*}}_{9} \cup {^{λ} K^{*}}_{7} \cup {^{λ} K^{*}}_{8, 6}$ , and the result follows from the existence of $D$ -decompositions of ${^{λ} K^{*}}_{9}$ , ${^{λ} K^{*}}_{7}$ (see Lemma 4), and ${^{λ} K^{*}}_{8, 6}$ .

For the remainder of the proof, we let $v = 6 x + 9$ for some integer $x \geq 2$ . Finally, we note that $K_{6 x + 9} = (K_{8} \cup x K_{6}) \lor K_{1} \cup x K_{8, 6} \cup (\binom{x}{2}) K_{6, 6} = K_{9} \cup x K_{7} \cup x K_{8, 6} \cup (\binom{x}{2}) K_{6, 6}$ . Thus ${^{λ} K^{*}}_{6 x + 9} = {^{λ} K^{*}}_{9} \cup x ({^{λ} K^{*}}_{7}) \cup x ({^{λ} K^{*}}_{8, 6}) \cup (\binom{x}{2}) ({^{λ} K^{*}}_{6, 6})$ , and the result follows from the existence of $D$ -decompositions of ${^{λ} K^{*}}_{9}$ , ${^{λ} K^{*}}_{7}$ , ${^{λ} K^{*}}_{8, 6}$ , and ${^{λ} K^{*}}_{6, 6}$ .

Lemma 7. Let $λ$ and $v$ be positive integers such that $v \equiv 4 (\mod 6)$ and $v \geq 10$ . If $D \in {D_{2}, D_{3}, \dots, D_{8}}$ , then there exists a $D$ -decomposition of $^{λ} K_{v}^{*}$ . Furthermore, if $λ$ is even, then there exists a $D_{9}$ -decomposition of $^{λ} K_{v}^{*}$ .

Proof. Let $D \in {D_{2}, D_{3}, \dots, D_{9}}$ . If $v = 10$ and $D \neq D_{9}$ , then the result follows from $λ$ copies of a $D$ -decomposition of $K_{10}^{*}$ (see Example 7). If $v = 10$ , $λ$ is even, and $D = D_{9}$ , then the result follows from $λ / 2$ copies of a $D_{9}$ -decomposition of ${^{2} K^{*}}_{10}$ (see Example 8). For the remainder of the proof, we let $v = 6 x + 4$ for some integer $x \geq 2$ , and we assume $λ$ is even whenever $D = D_{9}$ .

Next, we note that $K_{6 x + 4} = K_{4} \cup x K_{6} \cup x K_{4, 6} \cup (\binom{x}{2}) K_{6, 6} = K_{10} \cup (x - 1) K_{6} \cup (x - 1) K_{4, 6} \cup (\binom{x}{2}) K_{6, 6}$ . Thus ${^{λ} K^{*}}_{6 x + 4} = {^{λ} K^{*}}_{10} \cup (x - 1) ({^{λ} K^{*}}_{6}) \cup (x - 1) ({^{λ} K^{*}}_{4, 6}) \cup (\binom{x}{2}) ({^{λ} K^{*}}_{6, 6})$ , and the result follows from the existence of $D$ -decompositions of ${^{λ} K^{*}}_{10}$ , ${^{λ} K^{*}}_{6}$ (see Lemma 3), ${^{λ} K^{*}}_{4, 6}$ , and ${^{λ} K^{*}}_{6, 6}$ .

Lemma 8. Let $λ$ and $v$ be positive integers such that $λ \equiv 0 (\mod 3)$ , $v \equiv 5 (\mod 6)$ , and $v \geq 11$ . If $D \in {D_{2}, D_{3}, \dots, D_{9}}$ , then there exists a $D$ -decomposition of $^{λ} K_{v}^{*}$ .

Proof. If $v = 11$ , then the result follows from $λ / 3$ copies of a $D$ -decomposition of ${^{3} K^{*}}_{11}$ (see Example 9). For the remainder of the proof, we let $v = 6 x + 5$ for some integer $x \geq 2$ . Finally, we note that $K_{6 x + 5} = (K_{4} \cup x K_{6}) \lor K_{1} \cup x K_{4, 6} \cup (\binom{x}{2}) K_{6, 6} = K_{11} \cup (x - 1) K_{7} \cup (x - 1) K_{4, 6} \cup (\binom{x}{2}) K_{6, 6}$ . Thus ${^{λ} K^{*}}_{6 x + 5} = {^{λ} K^{*}}_{11} \cup (x - 1) ({^{λ} K^{*}}_{7}) \cup (x - 1) ({^{λ} K^{*}}_{4, 6}) \cup (\binom{x}{2}) ({^{λ} K^{*}}_{6, 6})$ , and the result follows from the existence of $D$ -decompositions of ${^{λ} K^{*}}_{11}$ , ${^{λ} K^{*}}_{7}$ (see Lemma 4), ${^{λ} K^{*}}_{4, 6}$ , and ${^{λ} K^{*}}_{6, 6}$ .

Combining the previous results from Lemmas 3 through 8 with Theorem 2 and Lemma 1, we obtain our main theorem, which we restate here.

Theorem 4. Let $D$ be an orientation of a $6$ -cycle and let $λ$ and $v$ be positive integers such that $v \geq 6$ . There exists a $D$ -decomposition of $^{λ} K_{v}^{*}$ if and only if $λ v (v - 1) \equiv 0 (\mod 3)$ and neither of the following hold

$(D, λ, v) = (D_{1}, 1, 6)$ or
$D = D_{9}$ and $λ (v - 1)$ is odd.

References:

Mendelsohn, N.S., 1971. A generalization of Steiner triple systems. In A.O.L. Atkin & J.B. Birch (Eds.), Computers in Number Theory (pp. 323–339). Academic Press.
Bermond, J.C., 1974. An application of the solution of Kirkman’s schoolgirl problem: The decomposition of the symmetric oriented complete graph into 3-circuits. Discrete Mathematics, 8, pp.301–304.
Hung, H.Y. and Mendelsohn, N.S., 1973. Directed triple systems. Journal of Combinatorial Theory, Series B, 14, pp.310–318.
Schönheim, J., 1975. Partition of the edges of the directed complete graph into 4-cycles. Discrete Mathematics, 11, pp.67–70.
Harary, F., Heinrich, K. and Wallis, W.D., 1978. Decomposition of complete symmetric digraph into the four oriented quadrilaterals. In Springer Lecture Notes in Mathematics (Vol. 686, pp. 165–173).
Alspach, B., Heinrich, K. and Varma, B.N., 1979. Decompositions of complete symmetric digraphs into the oriented pentagons. Journal of the Australian Mathematical Society, Series A, 28, pp.353–361.
Alspach, B., Gavlas, H., Šajna, M. and Verrall, H., 2003. Cycle decompositions IV: Complete directed graphs and fixed length directed cycles. Journal of Combinatorial Theory, Series A, 103, pp.165–208.
Odabaşı, U. The spectrum problem for the orientations of the 7-cycle. Preprint.
Bermond, J.C., Huang, C. and Sotteau, D., 1978. Balanced cycle and circuit design: Even cases. Ars Combinatoria, 5, pp.293–318.
Sotteau, D., 1981. Decomposition of $K_{m, n}$ into cycles (circuits) of length $2 k$ . Journal of Combinatorial Theory, Series B, 30, pp.75–81.

[1] Mendelsohn, N.S., 1971. A generalization of Steiner triple systems. In A.O.L. Atkin & J.B. Birch (Eds.), Computers in Number Theory (pp. 323–339). Academic Press.

[2] Bermond, J.C., 1974. An application of the solution of Kirkman’s schoolgirl problem: The decomposition of the symmetric oriented complete graph into 3-circuits. Discrete Mathematics, 8, pp.301–304.

[3] Hung, H.Y. and Mendelsohn, N.S., 1973. Directed triple systems. Journal of Combinatorial Theory, Series B, 14, pp.310–318.

[4] Schönheim, J., 1975. Partition of the edges of the directed complete graph into 4-cycles. Discrete Mathematics, 11, pp.67–70.

[5] Harary, F., Heinrich, K. and Wallis, W.D., 1978. Decomposition of complete symmetric digraph into the four oriented quadrilaterals. In Springer Lecture Notes in Mathematics (Vol. 686, pp. 165–173).

[6] Alspach, B., Heinrich, K. and Varma, B.N., 1979. Decompositions of complete symmetric digraphs into the oriented pentagons. Journal of the Australian Mathematical Society, Series A, 28, pp.353–361.

[7] Alspach, B., Gavlas, H., Šajna, M. and Verrall, H., 2003. Cycle decompositions IV: Complete directed graphs and fixed length directed cycles. Journal of Combinatorial Theory, Series A, 103, pp.165–208.

[8] Odabaşı, U. The spectrum problem for the orientations of the 7-cycle. Preprint.

[9] Bermond, J.C., Huang, C. and Sotteau, D., 1978. Balanced cycle and circuit design: Even cases. Ars Combinatoria, 5, pp.293–318.

[10] Sotteau, D., 1981. Decomposition of $K_{m, n}$ into cycles (circuits) of length $2 k$ . Journal of Combinatorial Theory, Series B, 30, pp.75–81.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

The $λ$ -fold Spectrum Problem for the Orientations of the 6-Cycle

Abstract

1. Introduction

2. Examples of Small Designs

3. General Constructions

References:

Information

Guidelines

CP Initiatives

Follow CP

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

The λ-fold Spectrum Problem for the Orientations of the 6-Cycle

Abstract

1. Introduction

2. Examples of Small Designs

3. General Constructions

References:

Information

Guidelines

CP Initiatives

Follow CP

The $λ$ -fold Spectrum Problem for the Orientations of the 6-Cycle