For a subgraph \(G\) of the complete graph \(K_n\), a \(G\)-design of order \(n\) is a partition of the edges of \(K_n\) into edge-disjoint copies of \(G.\) For a given graph \(G\), the \(G\)-design spectrum problem asks for which \(n\) a \(G\)-design of order \(n\) exists. This problem has recently been completely solved for every graph \(G\) with less than seven edges, with the lone exception of \(G \cong K_3 \cup 2K_2,\) the disconnected graph consisting of a triangle and two isolated edges. In this article, we solve this problem by proving that a \(K_3 \cup 2K_2\)-design of order \(n\) exists if and only if \(n \equiv 0 \; \textrm{or} \; 1 \pmod{5}\) and \(n\geq 10.\)
Let \(K\) be a graph and \(G\) a subgraph of \(K\). If \(E(K)\) can be partitioned into edge-disjoint copies of \(G\), then we say that \(K\) allows a \(G\)-decomposition. If \(K \cong K_n\), then we call the \(G\)-decomposition a \(G\)-design of order \(n\). The \(G\)-design spectrum problem asks for a description of all \(n\) such that a \(G\)-design of order \(n\) exists. For example, a \(K_3\)-design of order \(n\) is known as a Steiner Triple System, \({sts}(n)\). It is well known that an \({sts}(n)\) exists if and only if \(n \equiv 1 \; \textrm{or} \; 3 \pmod6.\)
In terms of number of edges, the smallest graph \(G\) for which the \(G\)-design spectrum problem remains open is \(G\cong K_3 \cup 2K_2,\) the disconnected graph containing a triangle and two isolated edges. Other than this graph, every graph with less than 7 edges has been solved. See the introduction of the recent article [3] for an accounting of these results.
In this article, we use a mix of graph labeling techniques and those borrowed from design theory to solve the \(K_3 \cup 2K_2\)-design spectrum problem by proving the following theorem.
Theorem 1.1. A \(K_3 \cup 2K_2\)-design of order \(n\) exists if and only if \(n \equiv 0 \; \textrm{or} \;1 \pmod 5\) and \(n\geq 10.\)
The necessity of \(n \equiv 0 \; \textrm{or} \;1 \pmod 5\) follows easily from the fact that \(|E(K_3 \cup 2K_2)|=5\) must divide \(\binom{n}{2}=\frac{n(n-1)}{2}\). Further, \(|V(K_3 \cup 2K_2)|=7\), so \(n \geq 10.\) In the sections that follow, we show these conditions are sufficient, completing the proof of Theorem 1.1.
Let \(G\) be a simple graph with \(q\) edges. Nearly 60 years ago, Alex Rosa reduced the problem of finding \(G\)-designs of order \(2q+1\) to assigning integers to the vertices of \(G\) that satisfies certain properties. Over the years, Rosa’s followers have developed other labelings that yield designs of orders congruent to 0 or 1 modulo \(2q.\) We review only the results pertinent to our work next.
Definition 2.1 (Rosa [4]).Let \(G\) be a graph with \(q\) edges. A \(\rho\)-labeling is an injection \(f: V(G) \rightarrow \{0,1,2, \dots, 2q\}\) such that the induced length function \(\ell: E(G) \rightarrow \{1,2, \dots, n\}\) defined as \[\ell(uv) = \text{min}\{|f(u)-f(v)|,2q+1-|f(u)-f(v)|\},\] is a bijection.
A \(G\)-design is cyclic if the vertex transformation \(v \mapsto v+1\) is an automorphism of the design. Rosa showed that a \(\rho\)-labeling of a graph \(G\) with \(q\) edges is equivalent to a cyclic \(G\)-design of order \(2q+1.\)
Theorem 2.2(Rosa [4]).Let \(G\) be a graph with \(q\) edges. There exists a cyclic \(G\)-design of order \(2q+1\) if and only if \(G\) admits a \(\rho\)-labeling.
In 2013, Bunge, Chantasartrassmee, El-Zanati, and Vanden Eynden defined the following labeling to address tripartite graph designs of odd order.
Definition 2.3(Bunge et al. [2]).Let \(G\) be a tripartite graph with \(q\) edges and vertex partition \(A \cup B \cup C\). A \(\rho\)-tripartite labeling of \(G\) is a \(\rho\)-labeling \(f\) of \(G\) such that:
\(f(a) < f(v)\) for any edge \(av \in E(G)\) where \(a \in A\) and \(v \in B \cup C\).
For every edge \(bc \in E(G)\) where \(b \in B\), \(c \in C\), there exists a complementary edge \(b'c' \in E(G)\) where \(b' \in B\), \(c' \in C\) such that \[|f(b) – f(c)| + |f(b') – f(c')| = 2q.\]
For all \(b \in B\), \(c \in C\), \[|f(b) – f(c)| \neq 2q.\]
It is worth noting that the second restriction in this definition permits \(b=b'\) and \(c=c'\). Indeed, if there exists exactly one edge in \(G\) of the form \(bc\) with \(b \in B\) and \(c \in C\), then it is necessary that \(|f(b)-f(c)|=q.\)
Theorem 2.4(Bunge et al . [2]).Let \(G\) be a tripartite graph with \(q\) edges which admits a \(\rho\)-tripartite labeling. Then there exists a cyclic \(G\)-decomposition of \(K_{2qk + 1}\) for all \(k \geq 1\).
Six years later, Bunge defined the following to address tripartite graph designs of even order.
Definition 2.5(Bunge [1]).Let \(G\) be a graph with \(q\) edges. A 1-rotational \(\rho\)-labeling of \(G\) is an injection \(f: V(G) \rightarrow \{0,1,2, \dots, 2q-2\} \cup \{\infty\}\) such that:
For some pendant vertex \(w\), \(f(w) = \infty\).
\(f\) is a \(\rho\)-labeling of \(G – w\).
Definition 2.6(Bunge [1]).Let \(G\) be a tripartite graph with \(q\) edges such that \(uw \in E(G)\) and \(deg(w) = 1\). A 1-rotational \(\rho\)-tripartite labeling of a graph \(G\) is an injection \(h : V(G) \rightarrow \{0,1,2, \dots, 2q-2\} \cup \{\infty\}\) such that:
\(h\) is a 1-rotational \(\rho\)-labeling of \(G\) with \(h(w) = \infty\).
If the edge \(av \in E(G) \backslash \{uw\}\), where \(a \in A\) and \(v \in B \cup C\), then \(h(a) < h(v)\).
If \(bc \in E(G)\) with \(b \in B\), \(c \in C\), then there exists an edge \(b'c' \in E(G)\) with \(b' \in B\), \(c' \in C\) such that \[|h(b) – h(c)| + |h(b') – h(c')| = 2q.\]
Theorem 2.7(Bunge [1]). Let \(G\) be a tripartite graph with \(q\) edges and a vertex of degree one. If \(G\) admits a 1-rotational \(\rho\)-tripartite labeling, then there exists a \(G\)-design of order \(2qk\) for any integer \(k \geq 1\).
Figures 1a and 1b show a \(\rho\)-tripartite labeling and a 1-rotational \(\rho\)-tripartite labeling, respectively of \(K_3 \cup 2K_2\). The top row of vertices belong to \(A\), the middle row of vertices belong to \(B\), and the vertex in the bottom row of each figure is in \(C.\)
Theorem 2.8. There exists a \(K_3 \cup 2K_2\)-design of order \(n\) whenever \(n\equiv 0 \; \textrm{or} \; 1 \pmod{10}\) and \(n\geq 10.\)
Proof. The proof is by Theorems 2.4 and 2.7, and the labelings shown in Figure 1. ◻
For any graphs \(G\) and \(H\), the lexicographic product, \(G(H)\) is the graph obtained by replacing every vertex in \(G\) with a copy of \(H\), and replacing every edge \(uv \in E(G)\) with the complete bipartite graph \(K_{|V(H)|,|V(H)|}.\) We denote the complete equipartite graph with \(p\) partite sets of size \(n\) as \(K_{p:n}\). Notice that \(K_{p:n} \cong K_p(\overline{K_n})\). Also, for any integer \(c\geq 2\), we denote the graph consisting of \(c\) mutually disjoint copies of \(G\) as \(cG\).
In some of the constructions in this section, we use the following result of Spencer regarding the maximal number of edge-disjoint triangles in \(K_n.\)
Theorem 3.1 (Spencer [5]).For any integer \(n \geq 3,\) let \(\mu(n)=\lfloor \frac{n}{3} \lfloor \frac{n-1}{2} \rfloor \rfloor.\) Let \(C(n)\) be the size of the largest set of edge-disjoint triangles in \(K_n.\) Then, \[C(n)= \begin{cases} \mu(n),& n \not\equiv 5\pmod6 ,\\ \mu(n)-1, &n \equiv 5\pmod 6. \end{cases}\]
If \(n \equiv 5 \pmod{10}\) and \(n \geq 10,\) then \(n=10k+5\) for some integer \(k\geq 1.\) We show these conditions are sufficient for a \(K_3 \cup 2K_2\)-design of order \(n\) in this subsection by proving the following two lemmas.
Lemma 3.2. There exists a \(K_3 \cup 2K_2\)-decomposition of the complete \(5\)-partite graph \(K_{5:2k+1}\) for any \(k\geq1.\)
Proof. The proof is by construction. Let \(V(K_{5:2k+1})=\mathbb{Z}_{5} \times \mathbb{Z}_{2k+1}\) and \(E(K_{5:2k+1})=\{(g_1,x_1)(g_2,x_2): g_1 \neq g_2\}\).
Define triangles \[\begin{array}{ccc} \mathcal{T}^{012}_i & = &\{(0,x),(1,x+i),(2,x+2i):x \in \mathbb{Z}_{2k+1}\} , \\ \mathcal{T}^{234}_i & = &\{(2,x),(3,x+i),(4,x+2i):x \in \mathbb{Z}_{2k+1}\} , \end{array}\] and \(2K_2\)’s \[\begin{array}{ccc} \mathcal{M}^{1}_i & = &\{(0,x+1)(3,x+1+i),(1,x+1+i)(3,x):x \in \mathbb{Z}_{2k+1}\} ,\\ \mathcal{M}^{2}_i & = &\{(0,x)(4,x+1+2i), (1,x)(4,x+2+2i):x \in \mathbb{Z}_{2k+1}\} , \end{array}\] for all \(i \in \mathbb{Z}_{2k+1}.\) Then, \(\mathcal{T}^{012}_i \cup \mathcal{M}^1_i\) and \(\mathcal{T}^{234}_i \cup \mathcal{M}^2_i\) each form \((2k+1)^2\) copies of \(K_3 \cup 2K_2.\) Furthermore, we have used all \(10(2k+1)^2\) edges of \(K_{5:2k+1}\) exactly once, so we have proven the theorem. ◻
Lemma 3.3. There exists a \(K_3 \cup 2K_2\)-decomposition of \(5K_{2k+1}\) for any \(k \geq 1.\)
Proof. The proof is by construction. Let \(G\cong5K_{2k+1}\) and \(n=10k+5=|V(G)|.\) The number of edge-disjoint copies of \(K_3 \cup 2K_2\) to construct is \[N=5\binom{2k+1}{2}/5=k(2k+1).\]
We will refer to the \(5\) connected components of \(G\) each isomorphic to \(K_{2k+1}\) as \(H_i\) for \(1\leq i \leq 5\). Notice that \(|E(H_i)|=N\). From each \(H_i\), construct a set \(\mathcal{T}_i\) of \(\lfloor N/5 \rfloor\) edge-disjoint triangles for \(1\leq i \leq 4,\) and \(N-4 \lfloor N/5 \rfloor\) triangles for \(i=5.\) Constructing these sets is possible due to Theorem 3.1. It can be easily checked that \(r:=N-5 \lfloor N/5 \rfloor \in \{0,1,3\}\), so the number of triangles in \(\mathcal{T}_5\) is either \(0,1\) or \(3\) more than the number in \(\mathcal{T}_i\) where \(i \neq 5.\) Denote the graph \(H_i \setminus \mathcal{T}_i\) by \(H'_i.\) The number of edges in \(H'_i\) is \(N- 3\lfloor N/5 \rfloor\) for \(1 \leq i \leq 4\) and \(12 \lfloor N/5 \rfloor -2N\) for \(i=5.\)
For \(1\leq i \leq 5\), arbitrarily pair any \(\lfloor N/5 \rfloor-r\) of the triangles from \(\mathcal{T}_i\) each with one edge from \(H'_{i+1}\) and one edge from \(H'_{i+2}\), with arithmetic in the subscript performed modulo 5. The number of triangles remaining in \(\mathcal{T}_i\) is \(r\) for \(1\leq i \leq 4,\) and \(2r\) for \(i=5.\) The number of edges remaining in \(H'_i\) is \(3r\) for \(1\leq i \leq 4,\) and \(0\) for \(i=5.\)
Form the remaining \(6r\) copies of \(K_3 \cup 2K_2\) by forming \(r\) copies of each of the following types.
A triangle from \(\mathcal{T}_1,\) an edge from \(H_2'\), and an edge from \(H_3'\).
A triangle from \(\mathcal{T}_2,\) an edge from \(H_1'\), and an edge from \(H_4'\).
A triangle from \(\mathcal{T}_3,\) an edge from \(H_1'\), and an edge from \(H_2'\).
A triangle from \(\mathcal{T}_4,\) an edge from \(H_2'\), and an edge from \(H_3'\).
A triangle from \(\mathcal{T}_5,\) an edge from \(H_1'\), and an edge from \(H_4'\).
A triangle from \(\mathcal{T}_5,\) an edge from \(H_3'\), and an edge from \(H_4'\).
The total number of edge-disjoint copies of \(K_3 \cup 2K_2\) constructed is \[5(\lfloor N/5 \rfloor-r)+6r=N,\] so the construction is complete and we have proved the theorem. ◻
Theorem 3.4. There exists a \(K_3 \cup 2K_2\)-design of order \(n\) whenever \(n\equiv 5 \pmod{10}\) and \(n\geq 15.\)
Proof. Let \(n=10k+5\) where \(k\geq 1.\) The proof follows from the congruence \(K_n \cong K_5(K_{2k+1})\) and Lemmas 3.2 and 3.3. ◻
For the smallest case, \(k=1\), we exhibit a \(K_3 \cup 2K_2\)-design of order 16 in Figure 2. In this design, we take \(V(K_{16})=\{0,1,\dots,14\} \cup \{\infty\}\) and compute edge lengths (shown in blue) as in the \(1\)-rotational \(\rho\)-labelings from Section 2. The arrow symbols indicate the amount each block is cyclicly increased by (as the \(\infty\) vertex stays fixed) to construct the design.
If \(k\geq 2,\) our construction in this subsection makes use of the following fact.
Lemma 3.5. Consider the complete graph \(K_{2k+1}\) and a matching \(M_{2k}\) on any \(2k\) of its vertices. Let \(G\) be the graph obtained by removing \(M_{2k}\) from \(K_{2k+1}\) and \(C^*(2k+1)\) be the size of the largest set of edge-disjoint triangles in \(G.\) If \(k\geq 2,\) then \(C^*(2k+1) \geq \binom{k}{2}.\)
Proof. If \(k=2\), we note that the graph \(K_5 \setminus M_4\) from Figure 3 shows \(C^*(5)=2\geq \binom{2}{2}\), so from now on we may assume \(k\geq 3.\) By Theorem 3.1 and the fact that \(M_{2k}\) can remove at most \(k\) triangles from a set that obtains the value \(C(2k+1),\) we have \[C^*(2k+1) \geq C(2k+1)-k.\]
If \(k \equiv 0 \; \textrm{or} \;1 \pmod 3\), then \[C(2k+1)-k= \left\lfloor \frac{k(2k+1)}{3} \right\rfloor -k = \frac{2k(k-1)}{3} \geq \frac{k(k-1)}{2} = \binom{k}{2}.\]
Similarly, if \(k \equiv 2\pmod3\), then \[C(2k+1)-k\geq \left\lfloor \frac{k(2k+1)}{3} \right\rfloor-1 -k = \frac{2(k^2-k-2)}{3} \geq \frac{k(k-1)}{2} = \binom{k}{2},\] so we have proved the lemma. ◻
For any graphs \(G\) and \(H\), the join of \(G\) with \(H\), denoted \(G \vee H\), is the graph with vertex set \(V(G \vee H)=V(G) \cup V(H)\) and edge set \(E(G \vee H)=E(G) \cup E(H) \cup \{gh: g\in V(G),h \in V(H)\}.\)
Lemma 3.6. There exists a \(K_3 \cup 2K_2\)-decomposition of \(5K_{2k+1} \vee K_1\) whenever \(k\geq 2.\)
Proof. The proof is by construction. Let \(G=5K_{2k+1} \vee K_1\) and \(n=10k+6=|V(G)|.\) The number of edge-disjoint copies of \(K_3 \cup 2K_2\) to construct is \[N=|E(G)|/5=5\left(\binom{2k+1}{2}+2k+1\right)/5=(2k+1)(k+1).\]
We will refer to the \(5\) connected components of \(G\) each isomorphic to \(K_{2k+1}\) as \(H_i\) for \(1\leq i \leq 5\), and the lone vertex of \(K_1\) as \(\infty\). Let \(M_i\) be a perfect matching on any set of \(2k\) vertices of \(H_i\) and let \(H'_i \cong H_i\setminus M_i\). Denote the single vertex of \(H_i\) left out of \(M_i\) as \(\lambda_i.\) For each \(1\leq i \leq 5,\) let \(\mathcal{T}^\infty_i\) be the set of \(k\) edge-disjoint triangles from the join \(M_i \vee K_1.\) The number of triangles that remain to be constructed is \[a:=N-5k=2k(k-1)+1.\]
Notice that \(4|(a-1).\) From each \(H'_i\), construct a set \(\mathcal{T}_i\) of \(\frac{a-1}{4}\) edge-disjoint triangles for \(1 \leq i \leq 4\), and let \(\mathcal{T}_5\) be a single triangle from \(H'_5.\) This is possible by Lemma 3.5 since \(\frac{a-1}{4}=\binom{k}{2}\).
Now we match the \(N\) triangles we have constructed with a pair of vertex-disjoint edges as follows. Assign
each triangle in \(\mathcal{T}^\infty_i\) with an edge from \(H'_{i+1}\setminus \mathcal{T}_{i+1}\) and an edge from \(H'_{i+2}\setminus \mathcal{T}_{i+2}\) for \(1\leq i \leq 5\) (with subscript arithmetic performed modulo 5),
one triangle from \(\mathcal{T}_i\) with an edge from \(H'_{i+1}\setminus \mathcal{T}_{i+1}\) and the edge \(\lambda_{i+2}\infty\) for \(1\leq i \leq 5\) (with subscript arithmetic performed modulo 5),
and the remaining triangles in \(\mathcal{T}_i\) with an edge from \(H'_{i+1}\setminus \mathcal{T}_{i+1}\) and an edge from \(H'_5 \setminus \mathcal{T}_5\) for \(1\leq i \leq 4\) (with subscript arithmetic performed modulo 4).
We refer to the copies of \(K_3 \cup 2K_2\) produced above as type \(1,2,\) or \(3\) in the natural way. Notice that the type 1 graphs assign \(5k\) triangles to \(10k\) edges producing \(5k\) copies of \(K_3 \cup 2K_2.\) The type 2 graphs assign 5 triangles to \(10\) edges producing \(5\) copies of \(K_3 \cup 2K_2.\) Finally, the type 3 graphs assign \(4\frac{k(k-1)-2}{2}=2(k+1)(k-2)\) triangles to \(4(k+1)(k-2)\) edges yielding \(2(k+1)(k-2)\) copies of \(K_3 \cup 2K_2.\) In total, we decomposed the edges of \(G\) into \[5k+5+2(k+1)(k-2)=(2k+1)(k+1)=N\] edge-disjoint copies of \(K_3 \cup 2K_2\), so the proof is complete. ◻
This leads to the main result of this subsection.
Theorem 3.7. There exists a \(K_3 \cup 2K_2\)-design of order \(n\) whenever \(n \equiv 6 \pmod{10}\) and \(n\geq 16.\)
Proof. Let \(n=10k+6\) and \(k\geq 1.\) If \(k=1\), the proof is by the design in Figure 2. On the other hand, if \(k\geq 2\), the proof follows from the congruence \(K_{n}\cong K_5(K_{2k+1}) \vee K_1\) and Lemmas 3.2 and 3.6. ◻
The proof of Theorem 1.1 now follows from Theorems 2.8, 3.4, and 3.7. Therefore, we have completely solved the \(K_3 \cup 2K_2\)-design spectrum problem. Furthermore, the \(G\)-design spectrum problem is now completely solved for every graph \(G\) with less than 7 edges.