A bowtie graph is the union of two edge disjoint 3-cycles which share a single vertex. A mixed bowtie is a partial orientation of a bowtie graph. In this paper, we consider decompositions of the complete mixed graph into mixed bowties consisting of a union of two isomorphic copies of mixed triples.
Graph decompositions have a long history in graph theory. The first book to survey the research in this area is Juraj Bosák’s 1990 Decompositions of Graphs [2]. Recently (2024) Graph Theory and Decomposition appeared, including material on both graph decompositions and digraph decompositions [7]. Perhaps the best known graph decomposition is a Steiner triple system, which is equivalent to partitioning the edge set of a complete graph into the edge sets of a collection of 3-cycles. It is well-known that such a decomposition exists if and only if the order of the complete graph is 0 or 1 (mod 6) (see [8]).
A bowtie graph consists of two 3-cycles which share exactly one vertex (Figure 1). A bowtie system of order \(v\) is a partitioning of the edge set of \(K_v\) into the edge sets of a collection of bowties. A bowtie system of order \(v\) exists if and only if \(v\equiv 1\) or 9 (mod 12). The case \(v\equiv 1\) (mod 12) was originally given in [6] and the case \(v\equiv 9\) (mod 12) appeared in [1].
Related to graph and digraph decompositions are mixed graph decompositions. Formally, a mixed graph on \(v\) vertices is an ordered pair \((V,C)\) where \(V\) is a set of vertices with \(|V|=v\), and \(C\) is a set of ordered pairs and unordered pairs of elements of \(V\). The unordered pairs are edges and the ordered pairs are arcs. We denote the edge containing vertices \(v_1\) and \(v_2\) as \(\{v_1, v_2\} = \{v_2, v_1\}\) and we denote the arc containing first vertex \(v_1\) and second vertex \(v_2\) as \((v_1, v_2)\). Notice that for given vertices \(v_1\) and \(v_2\) we allow a mixed graph to have edge \(\{v_1, v_2\}\) and arcs \((v_1, v_2)\) and \((v_2, v_1)\). We do not follow the convention of combining arcs \((v_1, v_2)\) and \((v_2, v_1)\) into the edge \(\{v_1, v_2\}\) (as was done by Harary and Palmer when they first introduced mixed graphs [5]). The complete mixed graph on \(v\) vertices, denoted \(M_v\), is the mixed graph \((V,C)\) where for each pair of distinct vertices \(v_1, v_2\in V\) we have \(\{v_1, v_2\}, (v_1, v_2), (v_2, v_1) \in C\). Therefore there are twice as many arcs as edges in \(M_v\). For \(m\) a mixed subgraph of \(M_v\), an \(m\)-decomposition of \(M_v\) is a set \(\{ m_1, m_2, \ldots, m_k\}\) of edge and arc disjoint isomorphic copies of \(m\) such that the union of the edge sets and arc sets of the \(m_i\) are the edge set and arc set, respectively, of \(M_v\). An \(m\)-decomposition of \(M_v\) is called an \(m\)-system of order \(v\). Since \(M_v\) has twice as many arcs as edges, then a necessary condition for the existence of an \(m\)-system is that \(m\) has twice as many arcs as edges. The first such system to be studied concerned the partial orientations of a 3-cycle, given in Figure 2 and called mixed triples. In the notation of Figure 2, a \(T_i\) decomposition of \(M_v\) is a \(T_i\) triple system of order \(v\). A \(T_i\) triple system of order \(v\) exists if and only if \(v \equiv 1\) (mod 2), except for \(v \in \{3, 5\}\) when \(i=3\) [3].
There are 25 partial orientations of a 6-cycle with with four arcs and two edges. A decomposition of \(M_v\) into such a partially oriented 6-cycle is a mixed hexagon system. Necessary and sufficient conditions for the existence of mixed hexagon systems are given in [4].
A partial orientation of a bowtie graph with four arcs and two edges such that the two resulting mixed triples are isomorphic is a homogeneous mixed bowtie. There are 12 homogeneous mixed bowties up to isomorphism. These are given in Figure 3. A decomposition of \(M_v\) into a collection of \(H_i^j\) mixed bowties is an \(H_i^j\) homogeneous mixed bowtie system (or simply an \(H_i^j\) bowtie system) of order \(v\). The purpose of this paper is to give necessary and sufficient conditions for the existence of \(H_i^j\) homogeneous mixed bowtie systems for all values of \(i\) and \(j\). We adopt the notation given in Figure 3.
Since an \(H_i^j\) decomposition of \(M_v\) implies a \(T_i\) decomposition of \(M_v\) then a necessary condition for the existence of an \(H_i^j\) bowtie system of order \(v\) is \(v\equiv 1\) (mod 2). Another necessary condition for the existence of such a homogeneous mixed bowtie system is that the number of triples in the induced mixed triple system is even, so that \(v\) must be 1 (mod 4). This gives the following necessary condition.
Lemma 3.1. If an \(H_i^j\) homogeneous mixed bowtie system of order \(v\) exists, then \(v\equiv 1\) \((\)mod \(4)\).
Since a \(T_3\) triple system of order 5 does not exist, then an \(H_3^j\) bowtie system of order \(5\) does not exist for any \(j\).
Lemma 3.2. If an \(H_i^j\) decomposition of \(M_5\) exists, then every vertex of \(M_5\) appears exactly once as a center vertex in the decomposition.
Proof. If an \(H_i^j\) decomposition of \(M_5\) exists, then there are five blocks and each vertex appears exactly once in each block. Now the total-degree of each vertex in \(M_5\) is 12, so a given vertex cannot be the center vertex of three blocks since then it could not be in the other two blocks. A given vertex cannot be the center vertex of two blocks since then it could only appear in two other of the blocks and could not appear in all five blocks. A given vertex cannot be the center vertex of none of the blocks, since then in the union of the blocks it would only have total-degree 10. Therefore, any given vertex must appear exactly once as a center vertex. ◻
In mixed bowtie \([a,b,c,d,e]_1^2\), we call \(a\) and \(d\) upper vertices, \(b\) and \(e\) lower vertices, and \(c\) the center vertex. Notice that in \([a,b,c,d,e]_1^2\) the out-degree of each upper vertex is 2 and the total-degree (that is, the edge degree plus the in-degree plus the out-degree) of the center vertex is 4.
Lemma 3.3. An \(H_1^2\) decomposition of \(M_5\) does not exist.
The proof of Lemma 3.3 is lengthy and unelegant, so we give it in the appendix.
Lemma 3.4. An \(H_1^3\) decomposition of \(M_5\) does not exist.
Proof. Assume such a decomposition exists and let \([a,b,c,d,e]_1^3\) be some block of the decomposition. By Lemma 3.2 there must be some block of the decomposition of the form \([\alpha, \beta, d, \gamma, \delta]_1^3\). Since \([a,b,c,d,e]_1^3\) contains the arcs \((d, c)\) and \((d,e)\), and \([\alpha, \beta, d , \gamma, \delta]_1^3\) contains the arcs \((d, \alpha)\) and \((d, \beta)\) then we have \(\alpha, \beta \not\in \{c, e\}\). So it must be that \(\alpha, \beta \in \{ a, b\}\). But then both \([a,b,c,d,e]_1^3\) and \([\alpha, \beta, d, \gamma, \delta]_1^3\) contain edge \(\{a,b\}\), a contradiction. ◻
We now show that the necessary conditions of Lemma 3.1 are sufficient, except in the case \(v=5\) for \(H_1^2\), \(H_1^3\), \(H_2^2\), \(H_2^3\), and \(H_3^j\) where \(j\in \{1, 2, 3, 4, 5, 6\}\) for which we know that no such system exists. We give direct constructions for each system of the admissible orders by presenting a set of base blocks. That is, we take the vertex set of \(M_v\) to be \(\{0, 1, 2, \ldots, v-1\}\) and give a set of isomorphic copies of \(H_i^j\) which, under the cyclic permutation \((0, 1, 2, \ldots, v-1)\), generate all copies of \(H_i^j\) in an \(H_i^j\) bowtie system.
Lemma 4.1. An \(H_1^1\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\).
Proof. Consider the set of mixed bowties: \[\begin{aligned} \left\{ \left[ 2t – i,\, 2t + 1 + i,\, 0,\, 4t – i,\, 1 + i \right]_1^1 \;\middle|\; i = 0, 1, 2, \ldots, t – 1 \right\}. \end{aligned}\]
This is a set of base blocks for an \(H_1^1\) bowtie system of order \(v=4t+1\). ◻
Lemma 4.2. An \(H_1^2\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\), \(v\neq 5\).
Proof. Suppose \(v=4t+1\) where \(t\geq 2\). Consider the set of mixed bowties: \[\begin{aligned} &\left\{ \left[ 4t – 1 – i,\, 4t – 3 – 2i,\, 0,\, 2t + 2 + i,\, 3 + 2i \right]_1^2 \;\middle|\; \begin{array}{l} i = 0, 1, \ldots, t-2, \\ i \neq \dfrac{2t – 5}{3} \end{array} \right\} \\[1ex] &\bigcup\; \left\{ \left[ 4t,\, 4t – 1,\, 0,\, 2t + 1,\, 1 \right]_1^2 \;\middle|\; \dfrac{2t – 5}{3} \notin \mathbb{N} \right\} \\[1ex] &\bigcup\; \left\{ \begin{array}{l} \left[ 4t,\, 4t – 1,\, 0,\, \dfrac{8t + 1}{3},\, \dfrac{4t – 1}{3} \right]_1^2,\\[4mm] \left[ \dfrac{10t + 2}{3},\, \dfrac{8t + 1}{3},\, 0,\, 2t + 1,\, 1 \right]_1^2 \end{array} \;\middle|\; \dfrac{2t – 5}{3} \in \mathbb{N} \right\}. \end{aligned}\] This is a set of base blocks for an \(H_1^2\) bowtie system of order \(v=4t+1\) and \(t\geq 2\). ◻
Lemma 4.3. An \(H_1^3\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\), \(v\neq 5\).
Proof. Suppose \(v=4t+1\) where \(t\geq 2\). Consider the set of mixed bowties: \[\begin{aligned} &\left\{ \left[ 2t – 1 – i,\, 2t + 2 + i,\, 0,\, 2 + i,\, 4 + 2i \right]_1^3 \;\middle|\; \begin{array}{l} i = 0, 1, \ldots, t – 2, \\ i \neq \dfrac{2t – 5}{3} \end{array} \right\} \\[1ex] &\cup\; \left\{ \left[ 2t,\, 2t + 1,\, 0,\, 1,\, 2 \right]_1^3 \;\middle|\; \dfrac{2t – 5}{3} \notin \mathbb{N} \right\} \\[1ex] &\cup\; \left\{ \begin{array}{l} \left[ 2t,\, 2t + 1,\, 0,\, \dfrac{2t + 1}{3},\, \dfrac{4t + 2}{3} \right]_1^3, \\[4mm] \left[ \dfrac{4t + 2}{3},\, \dfrac{8t + 1}{3},\, 0,\, 1,\, 2 \right]_1^3 \end{array} \;\middle|\; \dfrac{2t – 5}{3} \in \mathbb{N} \right\}. \end{aligned}\] This is a set of base blocks for an \(H_1^3\) bowtie system of order \(v=4t+1\) and \(t\geq 2\). ◻
The complete mixed graph \(M_v\) is self-converse, and the converse of \(H_1^j\) is \(H_2^j\) for \(j=1, 2, 3\), so an \(H_1^j\) decomposition of \(M_v\) exists if and only if an \(H_2^j\) decomposition of \(M_v\) exists for (respectively) \(j=1, 2, 3\). Lemmas 4.1, 4.2 and 4.3 therefore imply the sufficient conditions for the existence of an \(H_2^j\) decomposition of \(M_v\), as follows.
Lemma 4.4. An \(H_2^j\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\) where \(j\in \{1,2,3\}\), and \(v\neq 5\) when \(j\in \{2, 3\}\).
Lemma 4.5. An \(H_3^1\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\), \(v\geq 9\).
Proof. We consider several cases.
Case 1(a). Suppose \(v = 9\). Consider the following set of mixed bowties: \[\left\{ \left[1,\, 5,\, 0,\, 8,\, 2\right]_3^1,\; \left[6,\, 8,\, 0,\, 7,\, 3\right]_3^1 \right\}.\]
Case 1(b). Suppose \(v\equiv 1\) (mod 8), say \(v=8t+1\) where \(t\geq 2\). Consider the set of mixed bowties: \[\begin{aligned} &\left\{ [6t – 1 – i,\, 7t + 2 + i,\, 0,\, 8t – 1 – i,\, t + 2 + i]_3^1 \;\middle|\; i = 0, 1, \ldots, t – 2,\; i \neq \frac{t – 3}{2} \right\} \\ &\cup\;\left\{ [1 + i,\, 5t – i,\, 0,\, 7t – i,\, 2t + 1 + i]_3^1 \;\middle|\; i = 0, 1, \ldots, t – 1 \right\} \\ &\cup\;\left\{ [6t,\, 7t + 1,\, 0,\, 8t,\, t + 1]_3^1 \;\middle|\; \frac{t – 3}{2} \not\in \mathbb{N} \right\} \\ &\cup\;\left\{ \begin{aligned} &\left[ \frac{11t + 1}{2},\, \frac{15t + 1}{2},\, 0,\, 8t,\, t + 1 \right]_3^1, \\ &\left[ 6t,\, 7t + 1,\, 0,\, \frac{15t + 1}{2},\, \frac{3t + 1}{2} \right]_3^1 \end{aligned} \;\middle|\; \frac{t – 3}{2} \in \mathbb{N} \right\}. \end{aligned}\]
Case 2(a). Suppose \(v=21\). Consider the set of bowties: \[\left\{[17,\, 16,\, 0,\, 12,\, 7]_3^1, \ \ [6,\, 4,\, 0,\, 8,\, 12]_3^1, \ \ [9,\, 6,\, 0,\, 3,\, 18]_3^1, \ \ [5,\, 19,\, 0,\, 7,\, 20]_3^1, \ \ [2,\, 13,\, 0,\, 1,\, 11]_3^1 \right\}.\]
Case 2(b). Suppose \(v\equiv 5\) (mod 16), say \(v=16t+5\). Consider the set of mixed bowties: \[\begin{aligned} &\left\{ [2t + 4 + 2i,\, 2t + 2 + i,\, 0,\, 6t + 3 + 2i,\, 4t + 2 + i]_3^1 \;\middle|\; i = 0, 1, \ldots, 2t – 4 \right\} \\ &\cup \left\{ [6t + 2 + 4i,\, 8t + 4 + 2i,\, 0,\, 6t + 4 + 4i,\, 8t + 3 + 2i]_3^1 \;\middle|\; i = 0, 1, \ldots, t – 2 \right\} \\ &\cup \left\{ [2t + 5 + 2i,\, 14t + 6 + i,\, 0,\, 4t + 5 + 2i,\, 15t + 6 + i]_3^1 \;\middle|\; i = 0, 1, \ldots, t – 3 \right\} \\ &\cup \left\{ [2,\, 10t + 3,\, 0,\, 10t – 2,\, 10t + 2]_3^1,\, [12t + 5,\, 12t + 4,\, 0,\, 6t + 1,\, 16t + 4]_3^1,\,\right. \\&\qquad\left.[10t + 2,\, 6t + 1,\, 0,\, 1,\, 10t + 1]_3^1 \right\} \\ &\cup \left\{ [2t + 1,\, 14t + 4,\, 0,\, 4t + 3,\, 15t + 5]_3^1,\, [2t + 3,\, 14t + 5,\, 0,\, 4t + 1,\, 15t + 4]_3^1 \right\} \\ &\cup \left\{ [6t – 2,\, 4t – 1,\, 0,\, 10t – 1,\, 6t]_3^1,\, [6t,\, 4t,\, 0,\, 10t – 3,\, 6t – 1]_3^1 \right\} \end{aligned}\]
Case 3(a). Suppose \(v=13\). Consider the set of mixed bowties: \[\{ [2,\ 11,\ 0,\ 4,\ 12]_3^1,\ \ [1,\ 7,\ 0,\ 3,\ 8]_3^1,\ \ [11,\ 10,\ 0,\ 7,\ 4]_3^1 \}.\]
Case 3(b). Suppose \(v\equiv 13\) (mod 16), say \(v=16t+13\). Consider the set of mixed bowties: \[\begin{aligned} &\left\{ [ 2t+5+2i,\ 2t+3+i,\ 0,\ 6t+6+2i,\ 4t+4+i]_3^1\; \middle|\; i = 0, 1, \ldots, 2t-2\right\}\\ &\cup \left\{ [2t+2+2i,\ 14t+11+i,\ 0,\ 4t+4+2i,\ 15t+12+i]_3^1\; \middle|\; i = 0, 1, \ldots, t \right\}\\ &\cup \left\{ [2+2i,\ 10t+5-2i,\ 0,\ 2t+3-2i,\ 8t+8+2i]_3^1\; \middle|\; i=0, 1, \ldots, t-1 \right\}\\ &\cup \left\{ [1,\ 10t+7,\ 0,\ 10t+4,\ 6t+3]_3^1,\ \ [6t+3,\ 4t+2,\ 0,\ 10t+7,\ 6t+4]_3^1,\right.\\&\qquad\left.[12t+11,\ 12t+10,\ 0,\ 3,\ 10t+8]_3^1 \right\}. \end{aligned}\]
In each case, the given set is a set of base blocks for an \(H_3^1\) bowtie system. Therefore an \(H_3^1\) bowtie system exists of order \(v\equiv 1\) (mod 4), \(v\geq 9\). ◻
The complete mixed graph \(M_v\) is self-converse, and the converse of \(H_3^1\) is \(H_3^4\), so an \(H_3^1\) decomposition of \(M_v\) exists if and only if an \(H_3^4\) decomposition of \(M_v\) exists. Lemma 4.5 therefore implies the sufficient conditions for the existence of an \(H_3^4\) decomposition of \(M_v\), as follows.
Lemma 4.6. An \(H_3^4\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\), \(v\geq 9\).
Lemma 4.7. An \(H_3^2\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\), \(v\geq 9\).
Proof. We consider several cases.
Case 1. Suppose \(v\equiv 1\) (mod 8), say \(v=8t+1\). Consider the set of bowties: \[\left\{ \begin{aligned} &[8t – i,\ t + 1 + i,\ 0,\ 7t – 2i,\ t – i]_3^2,\\ &[7t – i,\ 2t + 1 + i,\ 0,\ 3t + 2 + 2i,\ 3t + 1 + i]_3^2 \end{aligned} \ \middle| \ i = 0, 1, 2, \ldots, t-1 \right\}.\]
Case 2(a). Suppose \(v= 21\). Consider the set of bowties: \[\left\{ \begin{aligned} &[12,\ 7,\ 0,\ 1,\ 5]_3^2, \ \ [9,\ 6,\ 0,\ 2,\ 17]_3^2, \ \ [5,\ 19,\ 0,\ 6,\ 3]_3^2, \\ &[2,\ 13,\ 0,\ 8,\ 1]_3^2, \ \ [8,\ 12,\ 0,\ 11,\ 10]_3^2 \end{aligned} \right\}.\]
Case 2(b). Suppose \(v\equiv 5\) (mod 16), say \(v=16t+5\), \(t\geq 2\). Consider the set of bowties:
\[\begin{aligned} &\left\{ [2t+4+2i,\ 2t+2+i,\ 0,\ 2t+1+i,\ 12t+3-i]_3^2 \,\middle|\, i = 0, 1, \ldots, 2t – 2 \right\} \\ &\cup \left\{ [6t+2+4i,\ 8t+4+2i,\ 0,\ 14t+6+2i,\ 8t+2-2i]_3^2 \,\middle|\, i = 0, 1, \ldots, t – 2,\ i \neq \frac{t}{3} \right\} \\ &\cup \left\{ [2t+5+2i,\ 14t+6+i,\ 0,\ 5t+4+i,\ t-1-i]_3^2 \,\middle|\, i = 0, 1, \ldots, t – 3 \right\} \\ &\cup \left\{ [2,\ 10t+3,\ 0,\ 16t+1,\ 6t+3]_3^2 \,\middle|\, \frac{t}{3} \not\in \mathbb{N} \right\} \\ &\cup \left\{ \begin{aligned} &[7t + \frac{t}{3} + 2,\ 8t + \frac{2t}{3} + 4,\ 0,\ 16t+1,\ 6t+3]_3^2, \\ &[2,\ 10t+3,\ 0,\ 14t + \frac{2t}{3} + 6,\ 7t + \frac{t}{3} + 2]_3^2 \end{aligned} \,\middle|\, \frac{t}{3} \in \mathbb{N} \right\} \\ &\cup \left\{ \begin{aligned} &[12t+5,\ 12t+4,\ 0,\ 6t+2,\ 1]_3^2, \ \ [10t+2,\ 6t+1,\ 0,\ 6t+5,\ 6t+4]_3^2 \end{aligned} \right\} \\ &\cup \left\{ \begin{aligned} &[2t+1,\ 14t+4,\ 0,\ 5t+3,\ t]_3^2, \ \ [2t+3,\ 14t+5,\ 0,\ 5t+2,\ t+1]_3^2 \end{aligned} \right\}. \end{aligned}\]
Case 3(a). Suppose \(v= 13\). Consider the set of bowties: \[\left\{ [11,\ 10,\ 0,\ 3,\ 9]_3^2,\ [2,\ 11,\ 0,\ 5,\ 1]_3^2,\ [1,\ 7,\ 0,\ 8,\ 5]_3^2 \right\}.\]
Case 3(b). Suppose \(v\equiv 13\) (mod 16), say \(v=16t+13\). Consider the set of bowties: \[\begin{aligned} &\left\{ [2t+5+2i,\ 2t+3+i,\ 0,\ 2t+2+i,\ 12t+9-i]_3^2 \,\middle|\, i = 0, 1, \ldots, 2t-1 \right\} \\ &\cup \left\{ [4t+8+2i,\ 15t+14+i,\ 0,\ 4t+6+i,\ 2t-i]_3^2 \,\middle|\, i = 0, 1, \ldots, t-2 \right\} \\ &\cup \left\{ [2+2i,\ 10t+5-2i,\ 0,\ 10t+8-4i,\ 8t+5-2i]_3^2 \,\middle|\, i = 0, 1, \ldots, t-1 \right\} \\ &\cup \left\{ [4t+4,\ 15t+12,\ 0,\ 4t+5,\ 2t+1]_3^2,\ [4t+6,\ 15t+13,\ 0,\ 4t+4,\ 2t+2]_3^2 \right\} \\ &\cup \left\{ [12t+11,\ 12t+10,\ 0,\ 4t+3,\ 10t+9]_3^2,\ [1,\ 10t+7,\ 0,\ 6t+8,\ 6t+5]_3^2 \right\}. \end{aligned}\]
In each case, the given set is a set of base blocks for an \(H_3^2\) bowtie system. Therefore an \(H_3^2\) bowtie system exists of order \(v\equiv 1\) (mod 4), \(v\geq 9\). ◻
Lemma 4.8. An \(H_3^3\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\), \(v\geq 9\).
Proof. We consider several cases.
Case 1(a). Suppose \(v=9\). Consider the set of bowties: \[\{ [ 6,\ 8,\ 0,\ 2,\ 5]_3^3,\ \ [4,\ 5,\ 0,\ 1,\ 3]_3^3 \}.\]
Case 1(b). Suppose \(v\equiv 1\) (mod 8), say \(v=8t+1\) where \(t\geq 2\). Consider the set of bowties: \[\begin{aligned} &\left\{ [6t-1-i,\ 7t+2+i,\ 0,\ 2+i,\ t+4+2i]_3^3 \,\middle|\, i = 0, 1, \ldots, t-2 \right\} \\ &\cup \left\{ [6t,\ 7t+1,\ 0,\ 1,\ t+2]_3^3 \,\middle|\, \frac{2t-2}{3} \not\in \mathbb{N} \right\} \\ &\cup \left\{ [1+i,\ 5t-i,\ 0,\ t+1+i,\ 3t+2+2i]_3^3 \,\middle|\, i = 0, 1, \ldots, t-1,\ i \ne \frac{2t-2}{3} \right\} \\ &\cup \left\{ \left[\frac{2t+1}{3},\ \frac{13t+2}{3},\ 0,\ 1,\ t+2\right]_3^3,\ \left[6t,\ 7t+1,\ 0,\ \frac{5t+1}{3},\ \frac{13t+2}{3}\right]_3^3 \,\middle|\, \frac{2t-2}{3} \in \mathbb{N} \right\}. \end{aligned}\]
Case 2(a). Suppose \(v=21\). Consider the set of bowties: \[\left\{ \begin{aligned} &[17,\ 16,\ 0,\ 14,\ 13]_3^3,\quad [12,\ 7,\ 0,\ 15,\ 19]_3^3,\quad [5,\ 19,\ 0,\ 12,\ 18]_3^3,\\ &[1,\ 11,\ 0,\ 13,\ 4]_3^3,\ \ [3,\ 18,\ 0,\ 19,\ 11]_3^3 \end{aligned} \right\}.\]
Case 2(b). Suppose \(v\equiv 5\) (mod 16), say \(v=16t+5\) where \(t\geq 2\). Consider the set of bowties:
\[\begin{aligned} &\left\{ [2t+4+2i,\ 2t+2+i,\ 0,\ 10t+2-2i,\ 14t+4-i]_3^3 \ \middle|\ i = 0, 1, \ldots, 2t-2 \right\} \\ &\cup\ \left\{ [6t+2+4i,\ 8t+4+2i,\ 0,\ 10t+1-4i,\ 2t-1-2i]_3^3 \ \middle|\ i = 0, 1, \ldots, t-2 \right\} \\ &\cup\ \left\{ [2t+5+2i,\ 14t+6+i,\ 0,\ 12t-2i,\ 11t+1-i]_3^3 \ \middle|\ i = 0, 1, \ldots, t-3 \right\} \\ &\cup\ \left\{ [2,\ 10t+3,\ 0,\ 6t+7,\ 4]_3^3,\ [12t+5,\ 12t+4,\ 0,\ 10t+4,\ 10t+3]_3^3,\right.\\ &\qquad\left. [10t+2,\ 6t+1,\ 0,\ 16t+4,\ 10t]_3^3 \right\} \\ &\cup\ \left\{ [2t+1,\ 14t+4,\ 0,\ 12t+2,\ 11t+2]_3^3,\ [2t+3,\ 14t+5,\ 0,\ 12t+4,\ 11t+3]_3^3 \right\} \end{aligned}\]
Case 3(a). Suppose \(v=13\). Consider the set of bowties: \[\{ [7,\ 4,\ 0,\ 2,\ 12]_3^3,\ \ [2,\ 11,\ 0,\ 9,\ 8]_3^3,\ \ [1,\ 7,\ 0,\ 10,\ 5]_3^3\}.\]
Case 3(b). Suppose \(v\equiv 13\) (mod 16), say \(v=16t+13\). Consider the set of bowties: \[\begin{aligned} &\left\{ [2t+5+2i,\ 2t+3+i,\ 0,\ 10t+7-2i,\ 14t+11-i]_3^3 \ \middle|\ i=0, 1, \ldots, 2t-1 \right\} \\[6pt] &\cup\ \left\{ [4t+4+2i,\ 15t+12+i,\ 0,\ 14t+11-2i,\ 12t+9-i]_3^3 \ \middle|\ i = 0, 1, \ldots, t \right\} \\[6pt] &\cup\ \left\{ [2+2i,\ 10t+5-2i,\ 0,\ 14t+10+2i,\ 6t+5+4i]_3^3 \ \middle|\ i = 0, 1, \ldots, t-1,\ i \neq \tfrac{2t}{3} \right\} \\[6pt] &\cup\ \left\{ [12t+11,\ 12t+10,\ 0,\ 16t+10,\ 10t+5]_3^3 \right\} \\[6pt] &\cup\ \left\{ [1,\ 10t+7,\ 0,\ 6t+6,\ 12t+10]_3^3 \ \middle|\ \tfrac{t}{3} \not\in \mathbb{N} \right\} \\[6pt] &\cup\ \left\{ \begin{aligned} \left[1,\ 10t+7,\ 0,\ 15t+\tfrac{t}{3}+10,\ 8t+\tfrac{2t}{3}+5\right]_3^3,\\ \left[t+\tfrac{t}{3}+2,\ 8t+\tfrac{2t}{3}+5,\ 0,\ 6t+6,\ 12t+10\right]_3^3 \end{aligned}\ \middle|\ \tfrac{t}{3} \in \mathbb{N} \right\} \end{aligned}\]
In each case, the given set is a set of base blocks for an \(H_3^3\) bowtie system. Therefore an \(H_3^3\) bowtie system exists of order \(v\equiv 1\) (mod 4) and \(v\geq 9\). ◻
The complete mixed graph \(M_v\) is self-converse, and the converse of \(H_3^3\) is \(H_3^5\), so an \(H_3^3\) decomposition of \(M_v\) exists if and only if an \(H_3^5\) decomposition of \(M_v\) exists. Lemma 4.8 therefore implies sufficient conditions for the existence of an \(H_3^5\) decomposition of \(M_v\), as follows.
Lemma 4.9. An \(H_3^5\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\), \(v\geq 9\).
Lemma 4.10. An \(H_3^6\) homogeneous mixed bowtie system of order \(v\) exists if \(v\equiv 1\) \((\)mod \(4)\), \(v\geq 9\).
Proof. We consider several cases.
Case 1(a). Suppose \(v=9\). Consider the set of bowties: \[\{ [2,\ 5,\ 0,\ 1,\ 3],\ \ [8,\ 4,\ 0,\ 3,\ 2]\}.\]
Case 1(b). Suppose \(v\equiv 1\) (mod 8), say \(v=8t+1\) where \(t\geq 2\). Consider the set of bowties: \[\begin{aligned} &\left\{ [2+i,\ t+4+2i,\ 0,\ 8t-1-i,\ 5t-3-2i]_3^6 \ \middle|\ i = 0, 1, \ldots, t-2 \right\} \\[6pt] &\cup\ \left\{ [t+2+i,\ 3t+4+2i,\ 0,\ 2t+2+i,\ t+3+2i]_3^6 \ \middle|\ i = 0, 1, \ldots, t-2 \right\} \\[6pt] &\cup\ \left\{ [t+1,\ 3t+2,\ 0,\ 8t,\ 5t-1]_3^6,\ [1,\ t+2,\ 0,\ 2t+1,\ t+1]_3^6 \right\} \end{aligned}\]
Case 2(a). If \(v=21\) then consider the set of bowties: \[\left\{\begin{aligned} &[4,\ 20,\ 0,\ 9,\ 16]_3^6,\ [15,\ 19,\ 0,\ 12,\ 18]_3^6,\ [18,\ 15,\ 0,\ 16,\ 14]_3^6,\\ &[14,\ 13,\ 0,\ 19,\ 11]_3^6,\ [20,\ 10,\ 0,\ 13,\ 4]_3^6 \end{aligned}\right\}.\]
Case 2(b). Suppose \(v\equiv 5\) (mod 16), say \(v=16t+5\), \(t\geq 2\). Consider the set of bowties: \[\begin{aligned} &\left\{ [14t+1-2i,\ 16t+3-i,\ 0,\ 10t+2-2i,\ 14t+4-i]_3^6 \;\middle|\; i = 0, 1, \ldots, 2t-2 \right\} \\ &\cup\; \left\{ [10t+3-4i,\ 2t+2-2i,\ 0,\ 10t+1-4i,\ 2t-1-2i]_3^6 \;\middle|\; i = 0, 1, \ldots, t-2 \right\} \\ &\cup\; \left\{ [14t-2i,\ 12t+1-i,\ 0,\ 12t-2i,\ 11t+1-i]_3^6 \;\middle|\; i = 0, 1, \ldots, t-3 \right\} \\ &\cup\; \left\{ [16t+3,\ 10t+1,\ 0,\ 6t+7,\ 4]_3^6,\ [4t,\ 16t+4,\ 0,\ 10t+4,\ 10t+3]_3^6,\right. \\ &\qquad\left. [6t+3,\ 12t+4,\ 0,\ 16t+4,\ 10t]_3^6 \right\} \\ &\cup\; \left\{ [14t+4,\ 12t+3,\ 0,\ 12t+2,\ 11t+2]_3^6,\ [14t+2,\ 12t+2,\ 0,\ 12t+4,\ 11t+3]_3^6 \right\}. \end{aligned}\]
Case 3. Suppose \(v\equiv 13\) (mod 16), say \(v=16t+13\). Consider the set of bowties: \[\begin{aligned} &\left\{ [14t+8-2i,\ 16t+11-i,\ 0,\ 10t+7-2i,\ 14t+11-i]_3^6 \;\middle|\; i = 0, 1, \ldots, 2t-1 \right\} \\ &\cup\; \left\{ [14t+9-2i,\ 12t+8-i,\ 0,\ 12t+7-2i,\ 11t+7-i]_3^6 \;\middle|\; i = 0, 1, \ldots, t-1 \right\} \\ &\cup\; \left\{ [16t+11-2i,\ 10t+3-4i,\ 0,\ 14t+10+2i,\ 6t+5+4i]_3^6 \;\middle|\; i = 0, 1, \ldots, t-1 \right\} \\ &\cup\; \left\{ [14t+11,\ 12t+9,\ 0,\ 6t+6,\ 12t+10]_3^6,\ [4t+2,\ 16t+12,\ 0,\ 12t+9,\ 11t+8]_3^6,\right. \\ &\qquad\left. [16t+12,\ 10t+6,\ 0,\ 16t+10,\ 10t+5]_3^6 \right\}. \end{aligned}\]
In each case, the given set is a set of base blocks for an \(H_3^6\) bowtie system. Therefore an \(H_3^6\) bowtie system exists of order \(v\equiv 1\) (mod 4) and \(v\geq 9\). ◻
We now have the necessary and sufficient conditions for the existence of a homogeneous mixed bowtie system for each possible homogeneous mixed bowtie. Based on the lemmas of Section 3 and this section, we have the following theorem.
Theorem 4.11. The necessary and sufficient conditions for the existence of an \(H_i^j\) homogeneous mixed bowtie system of order \(v\) are as follows:
(1) For \((i,j)\in \{ (1,1), (2,1)\}\), an \(H_i^j\) homogeneous mixed bowtie system of order \(v\) exists if and only if \(v\equiv 1\) \((\)mod \(4)\), and
(2) for \((i,j)\in \{ (1,2), (1, 3), (2,2), (2,3)\} \cup \{ (3,j) \mid j=1, 2, 3, 4, 5, 6\}\), an \(H_i^j\) homogeneous mixed bowtie system of order \(v\) exists if and only if \(v\equiv 1\) \((\)mod \(4)\) and \(v\neq 5\).
Lemma 3.3. An \(H_1^2\) decomposition of \(M_5\) does not exist.
Proof. Assume such a decomposition exists. By Lemma 3.2, each vertex of \(M_5\) must be the center of exactly one block of the decomposition. Also, in \(H_1^2\) each upper vertex is of out-degree two, whereas each lower vertex and the center vertex of \(H_1^2\) are of out-degree zero. Since the out-degree of each vertex of \(M_5\) is 4, then each vertex of \(M_5\) must be an upper vertex of exactly two blocks in a decomposition. We now hack through various collections of \(H_1^2\) blocks to show that no hypothesized decomposition exists.
The vertex labels are arbitrary so we take them as 0, 1, 2, 3, 4. Without loss of generality, one of the blocks is \(B=[3, 1, 0, 4, 2]_1^2\). As just explained, vertex 4 must be an upper vertex of another block. The only possible such blocks that share no edges or arcs with block \(B\) are \(B_a = [0, 2, 1, 4, 3]_1^2\), \(B_b = [0, 2, 3, 4, 1]_1^2\), and \(B_c = [2, 0, 3, 4, 1]_1^2\). Similarly, vertex 3 must be an upper vertex of another block and the only possible such blocks sharing no edges or arcs with block \(B\) are \(B_d = [3, 4, 2, 0, 1]_1^2\), \(B_e = [3, 2, 4, 0, 1]_1^2\), and \(B_f = [3, 2, 4, 1, 0]_1^2\). Now \(B_a\) and \(B_d\) share arc \((0, 1)\), \(B_a\) and \(B_e\) share arc \((0,1)\), and blocks \(B_b\) and \(B_d\) share arc \((0,2)\). So an \(H_1^2\) decomposition of \(M_5\) which contains block \(B\), must contain one of the following collections of three blocks: (i) \(B\), \(B_a\), \(B_f\), (ii) \(B\), \(B_b\), \(B_e\), (iii) \(B\), \(B_b\), \(B_f\), (iv) \(B\), \(B_c\), \(B_d\), (v) \(B\), \(B_c\), \(B_e\), and (vi) \(B\), \(B_c\), \(B_f\). We now show that none of these six necessary cases can be completed to give a decomposition.
(i) In \(B\), \(B_a\), \(B_f\), vertex 0 is an upper vertex once, so there must be another block in a decomposition in which 0 is an upper vertex. The only possible such blocks that share no edges or arcs with blocks \(B\), \(B_a\), \(B_f\) are \(B_g = [0,3,4,2,1]_1^2\) and \(B_h = [0,4,3,1,2]_1^2\). However, block \(B_f\) has 4 as the center vertex and by Lemma 3.2 only one block of a decomposition of \(M_5\) can have 4 as the center vertex. Hence, block \(B_g\) cannot be a block of the decomposition, and the blocks must be \(B\), \(B_a\), \(B_f\), \(B_k\). Then, also be Lemma 3.2, the fifth block of the decomposition must have center vertex 2. But the arcs \((0,2)\), \((1,2)\), \((3,2)\), and \((4,2)\) appear in blocks \(B_a\), \(B_h\), \(B_f\), and \(B\), respectively, so there is no choice for the upper vertices of a block with center vertex 2 which is consistent with blocks \(B\), \(B_a\), \(B_f\). Therefore, no \(H_1^2\) decomposition of \(M_5\) exists containing blocks \(B\), \(B_a\), \(B_f\).
(ii) In \(B\), \(B_b\), \(B_e\), each of vertices 0, 3, and 4 appear twice as upper vertices. In the remaining two blocks of a decomposition of \(M_5\), 1 and 2 must be the upper vertices, so that the center vertex of these two blocks must be either 0, 3, or 4. However, 0 is the center vertex of \(B\), 3 is the center vertex of \(B_b\), and 4 is the center vertex of \(B_e\). So, by Lemma 3.2, neither of the two blocks needed in the decomposition exist. Therefore, no \(H_1^2\) decomposition of \(M_5\) exists containing blocks \(B\), \(B_b\), \(B_e\).
(iii) In \(B\), \(B_b\), \(B_f\), vertex 1 is an upper vertex once, so there must be another block in a decomposition in which 1 is an upper vertex. But there is no such block that shares no edges or arcs with blocks \(B\), \(B_b\), \(B_f\). Therefore, no \(H_1^2\) decomposition of \(M_5\) exists containing blocks \(B\), \(B_b\), \(B_f\).
(iv) In \(B\), \(B_c\), \(B_d\), vertex 0 is an upper vertex once, so there must be another block in a decomposition in which 0 is an upper vertex. The only possible such block that shares no edges or arcs with blocks \(B\), \(B_c\), \(B_d\) is \(B_i = [2, 1, 4, 0, 3]_1^2\) (notice 3 cannot be the center vertex by Lemma 3.2, since 3 is the center vertex of \(B_c\)). In blocks \(B\), \(B_c\), \(B_d\), \(B_i\) the center vertices are 0, 3, 2, and 4, respectively, and 1 has not appeared as an upper vertex. So in the fifth block of a decomposition, 1 must appear twice as an upper vertex and as the center vertex, which is not possible. Therefore, no \(H_1^2\) decomposition of \(M_5\) exists containing blocks \(B\), \(B_c\), \(B_d\).
(v) In \(B\), \(B_c\), \(B_e\), vertex 2 is an upper vertex once, so there must be another block in a decomposition in which 2 is an upper vertex. Since the centers of these blocks are 0, 3, 4, then by Lemma 3.2 the block with 2 as an upper vertex must have center vertex 1. However, there are no such blocks which share no edges or arcs with \(B\), \(B_c\), \(B_e\). Therefore, no \(H_1^2\) decomposition of \(M_5\) exists containing blocks \(B\), \(B_c\), \(B_e\).
(vi) In \(B\), \(B_c\), \(B_f\), vertex 2 is an upper vertex once, so there must be another block in a decomposition in which 2 is an upper vertex. Since the centers of these blocks are 0, 3, and 4 then by Lemma 3.2 the block with 2 as an upper vertex must have center 1. However, there are no such blocks which share no edges or arcs with \(B\), \(B_c\), \(B_f\). Therefore, no \(H_1^2\) decomposition of \(M_5\) exists containing blocks \(B\), \(B_c\), \(B_f\).
Since an \(H_1^2\) decomposition of \(M_5\) must contain one of the six trios of blocks considered, we have a contradiction. That is, no \(H_1^2\) decomposition of \(M_5\) exists. ◻