A decomposition \(\mathcal{C}\) of a graph \(G\) is primitive if no proper, nontrivial subset of \(\mathcal{C}\) is a decomposition of an induced subgraph of \(G\). The existence of primitive decompositions has been studied for several decompositions, including path and cycle decompositions for complete and cocktail party graphs. In this work, we classify the existence of primitive star decompositions for complete graphs.
In this work we investigate the existence of primitive graph decompositions, which was formalized by Asplund et al. [1]. We begin with the following question:
Question 1.1. Let \(G\) be a graph with vertex set \(V\), and let \(\mathcal{G}\) be a decomposition of \(G\). Do there exist nonempty subsets \(\mathcal{G}’\subseteq \mathcal{G}\) and \(V’\subseteq V\) such that \(\mathcal{G}’\) is a decomposition of the induced subgraph of \(G\) with vertex set \(V’\)?
Such subsets \(\mathcal{G}’\) are subdecompositions of \(\mathcal{G}\). Trivially, the answer to the previous question is yes, as \(\mathcal{G}\) is a subdecomposition of itself. So we ask a more interesting question:
Question 1.2. Let \(G\) be a graph with a decomposition \(\mathcal{G}\). Does \(\mathcal{G}\) contain any proper subdecompositions?
If the answer to the previous question is no, we say \(\mathcal{G}\) is a primitive decomposition of \(G\), and this property has been investigated in several cases. In 2000, Rodger and Spicer [6] classified the existence of primitive \((K_4-e)\)-decompositions of complete graphs. In 2012, Dinavahi and Rodger [4] classified the existence of primitive \(P_n\)-decompositions of complete graphs. In 2022, Asplund et al. [1] investigated primitive \(C_n\)-decompositions of both complete graphs and cocktail party graphs and, in 2023, Schroeder [7] settled an unresolved question from the previous work involving \(C_4\)-decompositions of cocktail party graphs. By another name, \(2\)-primitivity of triple systems (\(C_3\)-decompositions of \(K_n\)) was introduced in 1969 by Doyen [5], in a paper discussing non-degenerate triple systems, and in 2024, Schroeder et al. [8] classified a similar result for \(C_3\)-decompositions of \(K_n-I\). In this paper, we continue the exploration of this topic with star decompositions.
Given positive integers \(m\) and \(n\), we say that \((m,n)\) is valid if either \(n=1\) or both \(n\geq 2m\) and \(n(n-1)\) is divisible by \(2m\). This is a necessary condition for \(K_n\) to have an \(m\)-star decomposition; the latter condition ensures an integral number of stars in such a decomposition, and the former arises from an \(m\)-star decomposition having at least \(n-1\) stars (at most one vertex is not a root for a star in the decomposition). Tarsi [3] demonstrated these conditions are sufficient.
Theorem 1.3. Let \(n\) and \(m\) be positive integers. Then \(K_{n}\) has an \(m\)-star decomposition if and only if \((m,n)\) is valid.
In this work, we show the necessary conditions are also sufficient for the existence of primitive \(m\)-star decompositions of \(K_n\).
Theorem 1.4. Let \(n\) and \(m\) be positive integers. Then \(K_{n}\) has a primitive \(m\)-star decomposition if and only if \(m=1\) and \(n\in\{1,2\}\), or \(m\neq 1\) and \((m,n)\) is valid.
For a positive integer \(m\), an \(m\)-star is a graph which is isomorphic to \(K_{1,m}\). The vertex in the part of size 1 is the root of \(S\), denoted \(r(S)\), and the vertex set of size \(m\) is the pendant vertex set of \(S\), denoted as \(P(S)\). In addition, we use the notation \((x;D)\) to denote the star with root \(x\) and pendant vertex set \(D\).
Let \(G\) and \(H\) be graphs. The join of \(G\) and \(H\), denoted \(G+H\), is a graph with vertex set \(V(G+H)=V(G)\cup V(H)\) and edge set \[E(G+H) = E(G) \cup E(H) \cup \{xy: x\in V(G),\ y\in V(H) \}.\]
For a graph \(G\) and a vertex set \(V\) with cardinality \(n\) and disjoint from \(V(G)\), the join of \(G\) with the \(n\) independent vertices in \(V\) is \(G+ \overline{K_n}\), where \(V = V(\overline{K_n})\), and we abbreviate this graph as \(G+V\).
Let \(G\) be a graph, \(\phi\) be a permutation of \(V(G)\), \(e\in E(G)\), and \(H\) a subgraph of \(G\). We define \(\phi(e) = \{\phi(i),\phi(j)\}\), where \(e=\{i,j\}\) for some \(i,j\in V(G)\), and \(\phi(H)\) is the graph such that \(V(\phi(H))=\{\phi(v):v\in V(H)\}\) and \(E(\phi(H))=\{\phi(e):e\in E(H)\}\). If \(\mathcal{G}\) is a set of subgraphs of \(G\), we use \(V(\mathcal{G})\) to denote the union of the vertex sets of all graphs in \(\mathcal{G}\).
Let \(\alpha=(a_1,a_2,\dots,a_k)\) be a sequence of integers. We let \(\Sigma_i(\alpha)\) denote the partial sum \(a_1+a_2+\cdots+a_i\), with the convention \(\Sigma_0(\alpha)=0\). Furthermore, for positive integers \(n_1,\dots,n_k\), we denote the sequence with \(n_1\) copies of \(a_1\), \(n_2\) copies of \(a_2\), \(\dots\), and \(n_k\) copies of \(a_k\) with \((a_1:n_1)(a_2:n_2)\cdots(a_k:n_k)\).
Let \(G\) be a digraph. Then \(G\) is a bi-tournament if \(V(G)\) may be partitioned as \(V_0\cup V_1\) such that for each edge \((x,y)\in E(G)\), if \(x\in V_i\), then \(y\in V_{1-i}\), and for all \(x\in V_0\), \(y\in V_1\), either \((x,y)\in E(G)\) or \((y,x)\in E(G)\), but not both. We say that such a bi-tournament has \((|V_0|,|V_1|)\) vertices. Suppose that \(V_0=\{x_1,\dots,x_n\}\) and \(V_1=\{y_1,\dots,y_m\}\), and for each \(i\in\{1,\dots,n\}\) and \(j\in\{1,\dots,m\}\), let \(k_i\) and \(\ell_j\) be the out-degrees of \(x_i\) and \(y_j\) in \(G\), respectively. The score sequences of \(G\) are the sequences \((k_1,\dots,k_n)\) and \((\ell_1,\dots,\ell_m)\), and we assume these sequences are non-decreasing. Beineke and Moon [2] classified when a pair of sequences is a set of score sequences for a bi-tournament.
Theorem 2.1.Let \(n,m\geq 1\) and \(\alpha=(a_1,\dots,a_n)\) and \(\beta=(b_1,\dots,b_m)\) be non-decreasing, non-negative integer sequences of lengths \(n\) and \(m\), respectively. Then \(\alpha\) and \(\beta\) are score sequences for a bi-tournament with \((n,m)\) vertices if and only if \(\Sigma_k(\alpha)+\Sigma_\ell(\beta) \geq k\ell\) for each \(k\in\{0,\dots,n\}\) and \(\ell\in\{0,\dots,m\}\), with equality when \(k=n\) and \(\ell=m\).
We now demonstrate a special case of Theorem 2.1.
Lemma 2.2. Let \(n,m\geq 1\) and \(\alpha=(a_1,\dots,a_n)\) and \(\beta=(b_1,\dots,b_m)\) be non-decreasing, non-negative integer sequences of lengths \(n\) and \(m\), respectively. Then \(\alpha\) and \(\beta\) are score sequences for a bi-tournament with \((n,m)\) vertices if \(\Sigma_n(\alpha)+\Sigma_m(\beta)=nm\) and there exist integers \(p\) and \(t\) such that \(1\leq p\leq n\), \(0\leq t\leq m\), \(a_{p+1}=a_{p+2}=\cdots=a_n=t\), and \(p\leq b_1\).
Proof.For \(u\in\{0,\dots,n\}\) and \(v\in\{0,\dots,m\}\), define \(g(u,v)=\Sigma_u(\alpha)+\Sigma_v(\beta)\). Since \(g(n,m)=nm\), it is sufficient to show that \(g(u,v)\geq uv\) over the domain of \(g\), as the result then follows from Theorem 2.1.
Clearly \(g(u,0)\geq 0\) for each \(u\in\{1,\dots,n\}\). Now suppose that \(g(u,v)\geq uv\) for some \(u\in\{0,\dots,p\}\) and \(v\in\{0,\dots,m-1\}\). Then \[\begin{equation*} g(u,v+1) = g(u,v) + b_{v+1} \geq uv + b_{v+1} \geq uv + b_1 \geq uv + p \geq uv + u = u(v+1), \end{equation*}\] so \(g(u,v+1)\geq u(v+1)\). Now let \(v\in\{0,\dots,m\}\). Then \[\begin{equation*} g(n,v) = \Sigma_n(\alpha)+\Sigma_v(\beta) = \left(\sum_{i=1}^n a_i\right) + \left(\sum_{j=1}^v b_j\right) = nm – \left(\sum_{j=v+1}^m b_j\right) \geq nm – (m-v)n = nv. \end{equation*}\]
Finally, suppose \(u\in\{p+1,\dots,n-1\}\) and \(v\in\{1,\dots,m\}\). Then \[\begin{equation} g(u,v) = g(p,v) + \left(\sum_{i=p+1}^u a_i\right) = g(p,v) + t(u-p) \geq pv + t(u-p) = bv + ut – bt = uv + bv + ut – bt – uv = uv + (b-u)v + ut – bt = uv + (b-u)v -t(b-u) = uv + (t-v)(u-p). \label{eq:guv1} \end{equation} \tag{1}\]
Similarly we have that \[\begin{equation} g(u,v) g(n,v) – \left(\sum_{i=u+1}^n a_i\right) = g(n,v) – t(n-u) \geq nv – t(n-u) = nv – nt + ut = uv + nv – uv – nt + ut = uv + v(n-u) – t(n-u) = uv + (v-t)(n-u). \label{eq:guv2} \end{equation} \tag{2}\]
Since both \(u-p\geq 0\) and \(n-u\geq 0\), we have that \(g(u,v)\geq uv\) by (1) if \(t\geq v\) or by (2) if \(t\leq v\). ◻
Again, let \(G\) be a graph. A set \(\mathcal{D}\) of subgraphs of \(G\) is a decomposition of \(G\) if \(\{E(H):H\in\mathcal{D}\}\) is a partition of \(E(G)\). A subset \(\mathcal{S}\) of \(\mathcal{D}\) is a subdecomposition of \(\mathcal{D}\) if there exists an induced subgraph \(H\) of \(G\) such that \(\mathcal{S}\) is a decomposition of \(H\). We say \(H\) is the induced subgraph of \(G\) associated to \(\mathcal{S}\). Recall that if \(\mathcal{D}\) has no proper subdecompositions, then \(\mathcal{D}\) is primitive.
Example 2.3. Let \(G=K_5\) with \(V(G)=\mathbb{Z}_5\), and let \[\begin{align*} \mathcal{D}&=\{(1;\{0,2\}),(2;\{0,3\}),(3;\{0,1\}),(4;\{0,1\}),(4;\{2,3\}), \text{ and}\\ \mathcal{E}&=\{(0;\{1,2\}),(1;\{2,3\}),(2;\{3,4\}),(3;\{4,0\}),(4;\{0,1\})\}. \end{align*}\]
Then \(\mathcal{D}’=\{(1;\{0,2\}),(2;\{0,3\}),(3;\{0,1\})\}\) is a proper subdecomposition of \(\mathcal{D}\), and hence \(\mathcal{D}\) is not primitive. However, \(\mathcal{E}\) has no proper subdecompositions, so \(\mathcal{E}\) is primitive. Furthermore, observe that if we define \(S=(0;\{1,2\})\) and \(\phi(x)=x+1\) for each \(x\in\mathbb{Z}_5\), then \(\mathcal{E} = \{\phi^i(S):i\in\{0,1,2,3,4\}\}\). See Figure 1.
| \(\mathcal{D}\) | \(\mathcal{D}’\) | \(\mathcal{E}\) |
The following lemma outlines a fairly obvious construction for an \(m\)-star decomposition, which is used in several subsequent arguments.
Lemma 2.4. Let \(a\) and \(m\) be positive integers with \(m\geq 3\). Then \(K_{a,m}\) has an \(m\)-star decomposition.
Proof. Let \(V\) and \(W\) be the parts of the vertex set of \(K_{a,m}\) with cardinalities \(a\) and \(m\), respectively. Then \(\mathcal{D}=\{(x;W):x\in V\}\) is an \(m\)-star decomposition of \(K_{a,m}\). Observe that any subset of \(\mathcal{D}\) is a subdecomposition, so \(\mathcal{D}\) is not primitive for any \(a\geq 2\). ◻
We now present two lemmas, originally introduced and proved by Asplund et al. [1], which lends itself better to proving primitivity, as well as providing a useful property involving the intersection of subdecompositions.
Lemma 2.5 (Lemma 2.1 in [1]). Let \(G\) be a graph with a decomposition \(\mathcal{G}\) and \(\mathcal{S}\subseteq\mathcal{G}\) with \(\mathcal{S}\neq\varnothing\).
(a) Then \(\mathcal{S}\) is a subdecomposition of \(\mathcal{G}\) if and only if for each \(v,w\in V(\mathcal{S})\), if \(vw\in E(G)\) and \(C\in\mathcal{G}\) such that \(vw\in E(C)\), then \(C\in\mathcal{S}\).
(b) If \(V(\mathcal{S})=V(G)\), then \(\mathcal{S}=\mathcal{G}\).
(c) If \(\mathcal{G}\) is primitive and \(\mathcal{S}\) is a subdecomposition of \(\mathcal{G}\), then \(\mathcal{S}=\mathcal{G}\).
(d) If \(\mathcal{S}\) being a subdecomposition of \(\mathcal{G}\) implies \(\mathcal{S}=\mathcal{G}\), then \(\mathcal{G}\) is primitive.
Lemma 2.6(Lemma 2.3 in [1]). Let \(G\) be a graph with a decomposition \(\mathcal{G}\) and let \(\mathcal{H}\) be a nonempty subset of \(\mathcal{G}\) associated to a subgraph \(H\) of \(G\). If \(\mathcal{S}\) is a subdecomposition of \(\mathcal{G}\), then \(\mathcal{S}\cap\mathcal{H}\) is either empty or a subdecomposition of \(\mathcal{H}\). Furthermore, if \(\mathcal{H}\) is a primitive decomposition of \(H\), then \(\mathcal{S}\cap\mathcal{H}\) is empty or \(\mathcal{H}\subseteq\mathcal{S}\).
We close this section with a pair of similar lemmas that provides a method for building a primitive decomposition for a graph from primitive decompositions of its subgraphs, which is leveraged in later arguments.
Lemma 2.7. Let \(G\) be a graph with subgraphs \(H\), and \(K\) with \(V(G)=V(H)\cup V(K)\). Let \(\mathcal{G}\) and \(\mathcal{H}\) be decompositions of \(G\) and \(H\), respectively, and both \(\mathcal{K}\) and \(\mathcal{K}’\) be decompositions of \(K\) such that
(a) \(\mathcal{H}\) and \(\mathcal{K}\) are subsets of \(\mathcal{G}\),
(b) \(\mathcal{H}\) is primitive,
(c) \(\mathcal{H}\cap\mathcal{K}\) is nonempty,
(d) any subdecomposition of \(\mathcal{G}\) intersects \(\mathcal{H}\) nontrivially, and
(e) \(\mathcal{K}’\) is contained in all subdecompositions of \((\mathcal{G}\backslash \mathcal{K})\cup\mathcal{K}’\).
Then \((\mathcal{G}\backslash \mathcal{K})\cup\mathcal{K}’\) is a primitive decomposition of \(G\).
Proof. Let \(\mathcal{G}’=(\mathcal{G}\backslash \mathcal{K})\cup\mathcal{K}’\) and \(\mathcal{S}’\) be a subdecomposition of \(\mathcal{G}’\) which associates to an induced subgraph \(I\) in \(G\). Let \(\mathcal{S} = (\mathcal{S}’\backslash\mathcal{K}’)\cup\mathcal{K}\). Then \(\mathcal{S}\subseteq \mathcal{G}\), and since \(\mathcal{K}’\subseteq \mathcal{S}’\) and \(\mathcal{K}\) and \(\mathcal{K}’\) are both decompositions of \(K\), we have that \(\mathcal{S}\) also associates to \(I\), so \(\mathcal{S}\) is a subdecomposition of \(\mathcal{G}\). Since \(\mathcal{H}\cap\mathcal{S}\) is nonempty and \(\mathcal{H}\) is primitive, it follows that \(\mathcal{H}\subseteq\mathcal{S}\), by Lemma 2.6. Hence \(V(\mathcal{S})=V(G)\), so \(\mathcal{S}=\mathcal{G}\). Therefore \(\mathcal{S}’=(\mathcal{G}\backslash\mathcal{K})\cup\mathcal{K}’=\mathcal{G}’\). Hence \(\mathcal{G}’\) is primitive by Lemma 2.5(d). ◻
Lemma 2.8. Let \(G\) be a graph with subgraphs \(H\), \(J\), \(K\) with \(V(G)=V(H)\cup V(J)\). Let \(\mathcal{G}\), \(\mathcal{H}\), and \(\mathcal{J}\) be decompositions of \(G\), \(H\), and \(J\), respectively, and both \(\mathcal{K}\) and \(\mathcal{K}’\) be decompositions of \(K\) such that
(a) \(\mathcal{H}\), \(\mathcal{J}\), and \(\mathcal{K}\) are subsets of \(\mathcal{G}\),
(b) \(\mathcal{H}\) and \(\mathcal{J}\) are primitive,
(c) both \(\mathcal{H}\cap\mathcal{K}\) and \(\mathcal{J}\cap\mathcal{K}\) are nonempty,
(d) any subdecomposition of \(\mathcal{G}\) intersects \(\mathcal{H}\cup\mathcal{J}\) nontrivially, and
(e) \(\mathcal{K}’\) is contained in all subdecompositions of \((\mathcal{G}\backslash \mathcal{K})\cup\mathcal{K}’\).
Then \((\mathcal{G}\backslash \mathcal{K})\cup\mathcal{K}’\) is a primitive decomposition of \(G\).
Proof. Let \(\mathcal{G}’=(\mathcal{G}\backslash \mathcal{K})\cup\mathcal{K}’\) and \(\mathcal{S}’\) be a subdecomposition of \(\mathcal{G}’\) which associates to an induced subgraph \(I\) in \(G\). Let \(\mathcal{S} = (\mathcal{S}’\backslash\mathcal{K}’)\cup\mathcal{K}\). Then \(\mathcal{S}\subseteq \mathcal{G}\), and since \(\mathcal{K}’\subseteq \mathcal{S}’\) and \(\mathcal{K}\) and \(\mathcal{K}’\) are both decompositions of \(K\), we have that \(\mathcal{S}\) also associates to \(I\), meaning \(\mathcal{S}\) is a subdecomposition of \(\mathcal{G}\). Since \(\mathcal{K}\subseteq \mathcal{S}\) and both \(\mathcal{H}\cap\mathcal{K}\) and \(\mathcal{J}\cap\mathcal{K}\) are nonempty, it follows that \(\mathcal{H}\cap\mathcal{S}\) and \(\mathcal{J}\cap\mathcal{S}\) are nonempty. Furthermore, since \(\mathcal{H}\) and \(\mathcal{J}\) are primitive, it follows that \(\mathcal{H}\subseteq\mathcal{S}\) and \(\mathcal{J}\subseteq\mathcal{S}\), by Lemma 2.6. Hence \(V(G)=V(H)\cup V(J)\subseteq V(\mathcal{S})\), so \(\mathcal{S}=\mathcal{G}\). Therefore \(\mathcal{S}’=(\mathcal{G}\backslash\mathcal{K})\cup\mathcal{K}’=\mathcal{G}’\). Hence \(\mathcal{G}’\) is primitive by Lemma 2.5(d). ◻
In this section, we prove Theorem 1.4 for odd \(m\geq 3\). First, we directly show the existence of primitive \(m\)-star decompositions of \(K_n\) when \((m,n)\) is valid and \(n<3m\), and then we provide an inductive construction to handle cases with larger \(n\).
Lemma 3.1. Let \(m\geq 2\) be a positive integer. Then \(K_{2m+1}\) has a primitive \(m\)-star decomposition.
Proof. Let \(G\) be isomorphic to \(K_{2m+1}\) with vertex set \(V(G) = \mathbb{Z}_{2m+1}\). Define \(S\) as the subgraph of \(G\) given by \(S=(0;\{1,\dots,m\})\), and let \(\phi\) be the permutation of \(V(G)\) given by \(\phi(x)=x+1\). Let \(\mathcal{D} = \{\phi^i(S):i\in\mathbb{Z}_{2m+1}\}\). Then \(\mathcal{D}\) is an \(m\)-star decomposition of \(G\), which we now show is primitive.
Let \(\mathcal{S}\) be a subdecomposition of \(\mathcal{D}\). Then \(\phi^i(S)\in \mathcal{S}\) for some \(i\in\mathbb{Z}_{2m+1}\). Since \(m\geq 2\), we have \(i+1,i+2\in V(S)\), and hence \(i+1,i+2\in V(\mathcal{S})\). Since \((i+1)(i+2)\in E(\phi^{i+1}(S))\), it follows that \(\phi^{i+1}(S)\in\mathcal{S}\). An iterative application of this gives that \(\mathcal{S}=\mathcal{D}\), and hence \(\mathcal{S}\) is not proper. So \(\mathcal{D}\) is primitive by Lemma 2.5(d). See Example 2.3 for an illustration of this decomposition when \(m=2\). ◻
Lemma 3.2. Let \(m\) and \(n\) be positive integers such that \(m\geq 2\), \((m,n)\) is valid, and \(n < 3m\). Then \(K_n\) has a primitive \(m\)-star decomposition.
Proof. By Theorem 1.3, \(K_n\) has an \(m\)-star decomposition \(\mathcal{D}\), and assume that \(\mathcal{D}\) is not primitive. Then \(n\neq 2m+1\) by Lemma 3.1. Let \(\mathcal{S}\) be a proper subdecomposition of \(\mathcal{D}\) with associated induced subgraph \(H\) of \(K_n\). Then \(H\) is isomorphic to \(K_\ell\), where \(2m\leq \ell < n\); hence \(n\neq 2m\). So \(n\geq 2m+2\), which implies that \(m\geq 3\).
Let \(J=\overline{H}\) in \(K_n\) and \(W=V(G)\backslash V(H)\); then \(\mathcal{D}\backslash\mathcal{S}\) is a decomposition of \(J\) and \(|W|=n-\ell\). Let \(x\in V(H)\). Then \(\deg_J(x) = n-\ell\), and hence \(1\leq \deg_J(x) \leq m-1\). So \(r(S)\notin V(H)\) for each \(S\in\mathcal{D}\backslash\mathcal{S}\). For each \(x\in W\), define \(f(x) = |\{ S\in\mathcal{J}: r(S)=x\}|\). Then the average value of \(f\) over \(W\) is \[\dfrac1{n-\ell}\sum_{x\in W}f(x) = \dfrac{|E(J)|}{m(n-\ell)} = \dfrac{n+\ell-1}{2m}\geq \dfrac{4m+1}{2m}>2.\]
Hence \(f(x)\geq 3\) for some \(x\in W\), and therefore \(\deg_J(x)\geq 3m\), which is not possible. Hence \(\mathcal{D}\) is a primitive \(m\)-star decomposition of \(K_n\). ◻
Notably, it follows from this argument that all \(m\)-star decompositions of \(K_n\) for which \(n=2m\) or \(2m+2\leq n < 3m\) are primitive. Interestingly, \(K_{2m+1}\) does have an \(m\)-star decomposition that is not primitive, which arises by first decomposing \(K_{2m+1}\) as the union of \(K_{2m}\) and \(K_{1,2m}\).
The next two lemmas, along with Lemma 3.2, are sufficient to show that Theorem 1.4 holds for odd \(m\geq 3\) and \(n\geq 3m\).
Lemma 3.3. Let \(m\) be a positive odd integer, \(m\geq 3\), \(K_m\) be a complete graph on a vertex set \(W\), and \(V\) be a vertex set of cardinality \((m+1)/2\) disjoint from \(W\). Then \(K_m+V\) has an \(m\)-star decomposition which contains two stars \(Q\) and \(R\) such that \(r(Q)\in W\), \(r(R)\in (P(Q)\cap W)\), and \(|V\cap P(Q)\cap P(R)|\geq 2\).
Proof. Identify \(W\) with the ring of integers modulo \(m\), \(\mathbb{Z}_m\). For each \(i\in W\), define the \(m\)-star \(S_i\) as \(S_i=(i;\{i+1,\dots,i+(m-1)/2\}\cup V)\). Define \(\mathcal{G}=\{ S_i:i\in W\}\), and as such, \(\mathcal{G}\) is an \(m\)-star decomposition of \(G\).
Observe that by defining \(Q=S_0\) and \(R=S_1\), the conditions on \(Q\) and \(R\) outlined in the lemma statement are satisfied. ◻
Lemma 3.4. Let \(a\) and \(m\) be positive integers such that \(m\geq 3\) and \(K_a\) has a primitive \(m\)-star decomposition. Then \(K_{a+m}\) has a primitive \(m\)-star decomposition if and only if \(m\) is odd.
Proof. First suppose that \(K_{a+m}\) has a primitive \(m\)-star decomposition. Then \(2m\) divides both \(a(a-1)\) and \((a+m)(a+m-1)\). Hence \(2m\) divides their difference, which is \(m(m-2a-1)\), and therefore \(m-2a-1\) must be even. So \(m\) is odd.
Now, suppose \(m\) is odd. Let \(U\), \(V\), and \(W\) be disjoint sets with cardinalities \(a-(m+1)/2\), \((m+1)/2\), and \(m\), respectively; note that \(a\geq 2m\) by Theorem 1.3, since \(K_a\) has an \(m\)-star decomposition, so \(U\) is well-defined. Then \(\{H,F,J\}\) is a decomposition of \(K_{a+m}\), where \(H=K_{a}\) with vertex set \(U\cup V\), \(J=K_m+V\) with vertex set \(W\cup V\), and \(F=K_{a-v,m}\) with \(U\) and \(W\) as the parts of its vertex set.
Let \(\mathcal{H}\), \(\mathcal{J}\), and \(\mathcal{F}\) be the \(m\)-star decompositions of \(H\), \(J\), and \(F\) given by the hypothesis and Lemmas 3.3 and 2.4. Then \(\mathcal{H}\) is primitive and \(\mathcal{H}\cup\mathcal{J}\cup\mathcal{F}\), which we denote as \(\mathcal{G}\), is an \(m\)-star decomposition of \(K_{a+m}\).
Let \(Q\in\mathcal{J}\) and \(R\in\mathcal{J}\) such that \(r(R)\in (P(Q)\cap W)\) and \(|V\cap P(Q)\cap P(R)|\ \geq 2\); let \(a=r(Q)\), \(b=r(R)\), and \(\{c,d\}\subseteq V\cap P(Q)\cap P(R)\) where \(c\neq d\). Without loss of generality, we may assume there exists a star \(S\in \mathcal{H}\) such that \(r(S)=c\), \(d\in P(S)\), and \(P(S)\cap U\) is nonempty; let \(e\in P(S)\cap U\). Observe that \((e;W)\in\mathcal{F}\), and let \(T=(e;W)\). See Figure 2(a).
Let \(\mathcal{K}=\{Q,S,T\}\), and define \(\mathcal{K}’\) as the set of subgraphs \(\{Q’,S’,T’\}\), where \[\begin{align} E(Q’) &= (E(Q)\backslash\{ac\})\cup\{ae\},\nonumber\\ E(S’) &= (E(S)\backslash\{ce\})\cup\{ca\},\text{ and}\nonumber\\ E(T’) &= (E(T)\backslash\{ea\})\cup\{ec\}.\label{eq:q’s’t’} \end{align} \tag{3}\]
See Figure 2(b). We seek to show that \((\mathcal{G}\backslash\mathcal{K})\cup\mathcal{K}’\), which we henceforth denote as \(\mathcal{G}’\), is a primitive \(m\)-star decomposition of \(K_{a+m}\). Observe that \(V(G) = V(H)\cup V(K)\), so it is sufficient to show that conditions (a) through (e) of Lemma 2.7 are satisfied, as the result then follows. The first three follow immediately by construction, so we now demonstrate that (d) and (e) are met.
Let \(\mathcal{S}\) be a subdecomposition of \(\mathcal{G}\), and assume that \(\mathcal{S}\cap\mathcal{H}\) is empty. Then either \(\mathcal{S}\cap\mathcal{J}\) or \(\mathcal{S}\cap\mathcal{F}\) is nonempty. If \(\mathcal{S}\cap\mathcal{J}\) is nonempty, then \(V\subseteq V(\mathcal{S})\), and since \(|V|\geq 2\), it follows that \(\mathcal{S}\cap\mathcal{H}\) is nonempty, which is a contradiction. So \(\mathcal{S}\cap\mathcal{J}\) is empty and \(\mathcal{S}\cap\mathcal{F}\) is nonempty. Then \((x;W)\in \mathcal{S}\) for some \(x\in U\). So \(W\in V(\mathcal{S})\), which implies \(\mathcal{S}\cap\mathcal{J}\) is nonempty, which contradicts. So \(\mathcal{S}\cap\mathcal{H}\) is nonempty, and hence (d) is satisfied.
Now, let \(\mathcal{S}’\) be a subdecomposition of \(\mathcal{G}’\). First, we show that \(\mathcal{S}’\cap\mathcal{K}’\) is nonempty. Suppose to the contrary. Then \(\mathcal{S}’\) is also a subdecomposition of \(\mathcal{G}\) and \(\{Q,S,T\}\cap\mathcal{S}\) is empty. However, since \(\mathcal{S}’\) is nontrivial, \(\mathcal{S}’\) must intersect nontrivially with either \(\mathcal{H}\), \(\mathcal{J}\), or \(\mathcal{F}\). If \(\mathcal{S}’\cap\mathcal{H}\) is nonempty, then \(\mathcal{H}\subseteq\mathcal{S}’\) by Lemma 2.6, meaning \(S\in\mathcal{S}’\), which is a contradiction. If \(\mathcal{S}\cap\mathcal{J}\) is nonempty, then \(V\subseteq V(\mathcal{S})\), which implies that either \(S\in\mathcal{S}\) or \(\mathcal{S}’\cap\mathcal{H}\) is nonempty, which is another contradiction. If \(\mathcal{S}’\cap\mathcal{F}\) is nonempty, then \(W\subseteq V(\mathcal{S}’)\) and hence \(\mathcal{S}’\cap\mathcal{J}\) is nonempty, which is, again, a contradiction. Therefore \(\mathcal{S}’\cap\mathcal{K}’\) is nonempty.
We conclude by showing that \(\mathcal{K}’\subseteq\mathcal{S}\). We consider three cases.
Suppose \(Q’\in \mathcal{S}’\). Then \(e,b\in V(\mathcal{S}’)\), and hence \(T’\in \mathcal{S}’\).
Suppose \(T’\in\mathcal{S}’\). Then \(c,b\in V(\mathcal{S}’)\), and hence \(R\in\mathcal{S}\). So \(d\in V(\mathcal{S}’)\), implying that \(S’\in\mathcal{S}\).
Suppose \(S’\in\mathcal{S}’\). Then \(a,d\in V(\mathcal{S}’)\), and hence \(Q’\in \mathcal{S}’\).
The above implications show that since \(\mathcal{K}’\cap\mathcal{S}’\) is nonempty, then \(\mathcal{K}’\subseteq\mathcal{S}’\), which satisfies condition (e) in Lemma 2.7. Hence \(\mathcal{G}’\) is primitive, and therefore \(K_{a+m}\) has a primitive \(m\)-star decomposition. ◻
Combining the results of Theorem 1.3 with Lemmas 3.2 and 3.4 admits the following classification.
Theorem 3.5. Let \(m\geq 3\) be an odd integer. Then \(K_n\) has a primitive \(m\)-star decomposition if and only if \((m,n)\) is valid.
Lemma 3.2 proved Theorem 1.4 when \(m \geq 2\) and \(2m\leq n < 3m\), regardless of the parity of \(m\). However, Lemma 3.4 relies on \(m\) being odd, meaning another method is needed when \(m\) is even. First, we directly prove the existence of primitive \(m\)-star decompositions of \(K_n\) when \(n < 4m\) with two constructions, dependent on the parity of \(n\). Then, we prove an inductive result weaker than Lemma 3.4 to resolve the remaining cases of Theorem 1.4.
Lemma 4.1. Let \(m\geq 3\) and \(n\) be a positive, even integer. Suppose there exist integers \(p\) and \(q\) such that \(p\geq 2\), \(1\leq q\leq m-2\), \(m = p + 2q + 1\), and \(n = 4p + 6q + 4\). Then there exists a primitive \(m\)-star decomposition of \(K_n\).
Proof. Since \(p\) and \(q\) are nonnegative, it follows that \[\begin{equation*} m+q \leq 2p+2q+2+\frac1m\binom{2q+1}2 \leq 2m+2q+1. \end{equation*}\]
Then we may find integers \(s\) and \(t\) such that \(0\leq s \leq 2q+1\), \(m+q\leq t\leq 2m\), and \(s+t=2p+2q+2+\frac1m\binom{2q+1}2\). Observe that \(n-2m = 2p+2q+2\). Let the sequences \(\alpha\) and \(\beta\), each with length \(2m\) and \(n-2m\), respectively, be defined as \[\alpha = (0:2m-t)(m:t) \text{ and }\beta = (m-q:2q+1-s)(m:2p+1)(2m-q:s).\]
Since \(\Sigma_{2m}(\alpha) + \Sigma_{n-2m}(\beta) = 2m(n-2m)\) and \(2m-t \leq m-q\) (which is equivalent to \(t\geq m+q\)), then by Lemma 2.2, there exists a bi-tournament \(T\) on \((2m,n-2m)\) vertices for which \(\alpha\) and \(\beta\) are score sequences. Let \(V_a\), \(V_b\), and \(V_c\) be the vertex sets \(V_a = \{ a_i: i\in\mathbb{Z}_{2m}\}\), \(V_b = \{ b_j: j\in\mathbb{Z}_{2p+1}\}\), and \(V_c = \{ c_k: k\in\mathbb{Z}_{2q+1}\}\). We may take \(V_a\) and \(V_b\cup V_c\) to be the vertex sets of \(T\), and hence there exist a \(t\)-subset \(X\subseteq\mathbb{Z}_{2m}\) and an \(s\)-subset \(Y\subseteq\mathbb{Z}_{2q+1}\) such that \[\begin{align*} |N_T(a_i)| &= m\text{ if $i\in X$ and $0$ if $i\notin X$},\\ |N_T(b_j)| &= m,\text{ and}\\ |N_T(c_k)| &= 2m-q\text{ if $k\in Y$ and $m-q$ if $k\notin Y$}. \end{align*}\]
Without loss of generality, we may assume that \(N_T(b_0)=\{a_0,\dots,a_{m-1}\}\).
Let \(G\) be a graph isomorphic to \(K_n\) with vertex set \(V_a\cup V_b\cup V_c\). For each \(k\in \mathbb{Z}_{2q+1}\), let \(N_T'(c_k)\) be a \((m-q)\)-subset of \(N_T(c_k)\); note that \(|N_T(c_k)\backslash N_T'(c_k)|=m\) when \(k\in Y\) and \(N_T'(c_k)=N_T(c_k)\) when \(k\notin Y\). For each \(i\in\mathbb{Z}_{2m}\), define \(x_i = b_0\) if \(i\in\{0,\dots,m-1\}\) and \(x_0=a_{i+m}\) if \(i\in\{m,\dots,2m-1\}\). For \(i\in \mathbb{Z}_{2m}\), \(j\in\mathbb{Z}_{2p+1}\), and \(k\in\mathbb{Z}_{2q+1}\), define the subgraphs \(A_i\), \(B_j\), and \(C_k\) of \(G\) as the stars \[\begin{align*} A_i &= (a_i;\{a_{i+1},\dots,a_{i+m-1},x_i\}),\\ B_j &= (b_j;\{b_{j+1},\dots,b_{j+p}\}\cup V_c),\text{ and}\\ C_k &= (c_k;\{c_{k+1},\dots,c_{k+q}\}\cup N_T'(c_k)). \end{align*}\]
For each \(i\in X\), \(j\in\mathbb{Z}_{2p+1}\backslash\{0\}\), and \(k\in Y\), define \[\begin{align*} A_i’ &= (a_i;N_T(a_i)),\\ B_j’ &= (b_j;N_T(b_j)),\text{ and}\\ C_k’ &= (c_k;N_T(c_k)\backslash N_T'(c_k)). \end{align*}\]
Next, define \(\mathcal{A}\), \(\mathcal{B}\), \(\mathcal{C}\), \(\mathcal{A}’\), \(\mathcal{B}’\), and \(\mathcal{C}’\) as the sets \[\begin{align*} \mathcal{A} &= \{ A_i: i\in\mathbb{Z}_{2m}\}, & \mathcal{A}’ &= \{ A_i’: i\in X\},\\ \mathcal{B} &= \{ B_j: j\in\mathbb{Z}_{2p+1}\},& \mathcal{B}’ &= \{ B_j’: j\in\mathbb{Z}_{2p+1}\backslash\{0\}\},\\ \mathcal{C} &= \{ C_k: k\in\mathbb{Z}_{2q+1}\},\text{ and} & \mathcal{C}’ &= \{ C_k’: k\in Y\}. \end{align*}\]
Finally, define \(\mathcal{D} = \mathcal{A}\cup\mathcal{B}\cup\mathcal{C}\cup\mathcal{A}’\cup\mathcal{B}’\cup\mathcal{C}’\). We claim that \(\mathcal{D}\) is a primitive \(m\)-star decomposition of \(K_n\). By its construction, we have that \(\mathcal{D}\) is an \(m\)-star decomposition, so we only need to show \(\mathcal{D}\) is primitive. To that end, let \(\mathcal{S}\) be a nontrivial subdecomposition of \(\mathcal{D}\). First, we begin with two useful facts about \(\mathcal{S}\).
(a) Suppose \(\mathcal{A}\cap\mathcal{S}\neq\varnothing\). Then there exists \(A_i\in \mathcal{S}\) for some \(i\in\mathbb{Z}_{2m}\). Since \(m\geq 3\), we have that \(a_{i+1},a_{i+2}\in V(\mathcal{S})\). So \(A_{i+1}\in\mathcal{S}\) as well, since \(a_{i+1}a_{i+2}\in E(A_{i+1})\). An iterative application of this argument gives that \(\mathcal{A}\subseteq \mathcal{S}\), and as such, \(V_a\subseteq V(\mathcal{S})\).
(b) Suppose \(\mathcal{B}\cap\mathcal{S}\neq\varnothing\). Then there exists \(B_j\in\mathcal{S}\) for some \(j\in\mathbb{Z}_{2p+1}\). Then \(V_c\subseteq V(\mathcal{S})\) and, since \(p\geq 2\), \(b_{j+1}\in V(\mathcal{S})\) as well. Hence \(B_{j+1}\in\mathcal{S}\), since \(b_{j+1}x\in E(B_{j+1})\) for each \(x\in V_c\). An iterative application of this argument gives that \(\mathcal{B}\subseteq \mathcal{S}\), and as such, \(V_b\cup V_c\subseteq V(\mathcal{S})\).
Therefore, it is sufficient to show that \(\mathcal{A}\cap\mathcal{S}\) and \(\mathcal{B}\cap\mathcal{S}\) are nonempty, as (a) and (b) imply \(V(\mathcal{S})=V(G)\), and hence \(\mathcal{D}\) is primitive by Lemma 2.5(b). Consider the following five cases.
(1) Suppose that \(\mathcal{A}\cap\mathcal{S}\neq \varnothing\). Then from property (a), we have that \(\mathcal{A}\subseteq \mathcal{S}\), and hence \(V_a\subseteq V(\mathcal{S})\) and \(b_0\in V(\mathcal{S})\) as well. Since \(b_0a_m\in E(A_m’)\), we have that \(A_m’\in\mathcal{S}\), and since \(p\geq 2\), there exists some \(b_j\in V(A_m’)\), where \(j\in\mathbb{Z}_{2p+1}\) and \(j\neq 0\). Since either \(b_0b_j \in E(B_0)\) or \(E(B_j)\), we have that \(\mathcal{B}\cap\mathcal{S}\) is nonempty.
(2) Suppose that \(\mathcal{B}\cap\mathcal{S}\neq\varnothing\). Then \(V_c\subseteq V(\mathcal{S})\), and since \(q\geq 1\), \(C_k\in \mathcal{S}\) for each \(k\in\mathbb{Z}_{2q+1}\). Hence \(\mathcal{C}\cap\mathcal{S}\) is nonempty.
(3) Suppose that \(\mathcal{C}\cap\mathcal{S}\neq\varnothing\). Then \(C_k\in\mathcal{S}\) for some \(k\in\mathbb{Z}_{2q+1}\). Since \(m-q\geq 2\), there exist distinct \(a_h,a_{i}\in V(\mathcal{S})\); without loss of generality, suppose \(h=i+\ell\) for some \(\ell\in\{1,\dots,m\}\). Hence \(A_{i}\in\mathcal{S}\), and therefore \(\mathcal{A}\cap\mathcal{S}\) is nonempty.
(4) Suppose \(\mathcal{A}’\cap\mathcal{S}\neq\varnothing\). Then \(|V_b\cap V(\mathcal{S})|\geq p\geq 2\), and so \(\mathcal{B}\cap\mathcal{S}\) is nonempty.
(5) Suppose \((\mathcal{B}’\cup\mathcal{C}’)\cap\mathcal{S}\) is nonempty. Then \(|V_a\cap V(\mathcal{S})|\geq m \geq 3\), and hence \(\mathcal{A}\cap\mathcal{S}\) is nonempty.
The previous five facts imply that, since \(\mathcal{S}\) is nonempty, \(\mathcal{A}\cap\mathcal{S}\) and \(\mathcal{B}\cap\mathcal{S}\) are both nonempty. Hence \(\mathcal{D}\) is primitive. ◻
The next lemma and proof is very similar to that of Lemma 4.1, however, modifications to the construction are needed due to the parity of \(n\).
Lemma 4.2. Let \(m\geq 3\) and \(n\) be a positive, odd integer. Suppose there exist integers \(p\) and \(q\) such that \(p\geq 2\), \(1\leq q\leq m-2\), \(m = p + 2q\), and \(n = 4p + 6q + 1\). Then there exists a primitive \(m\)-star decomposition of \(K_n\).
Proof. Since \(p\) and \(q\) are nonnegative, it follows that \[m+q \leq 2p+2q+\frac1m\binom{2q}2 \leq 2m+2q.\]
Then we may find integers \(s\) and \(t\) such that \(0\leq s \leq 2q\), \(m+q\leq t\leq 2m\), and \(s+t=2p+2q+\frac1m\binom{2q}2\). Observe that \(n-2m = 2p+2q+1\). Let the sequences \(\alpha\) and \(\beta\), each with length \(2m\) and \(n-2m\), respectively, be defined as \[\alpha = (0:2m-t)(m:t) \text{ and }\beta = (m-q:2q-1-s)(m:2p+1)(2m-q:s)(2m:1).\]
Since \(\Sigma_{2m}(\alpha) + \Sigma_{n-2m}(\beta) = 2m(n-2m)\) and \(2m-t \leq m-q\) (which is equivalent to \(t\geq m+q\)), then by Lemma 2.2, there exists a bi-tournament \(T\) on \((2m,n-2m)\) vertices for which \(\alpha\) and \(\beta\) are score sequences. Let \(V_a\), \(V_b\), and \(V_c\) be the vertex sets \(V_a = \{ a_i: i\in\mathbb{Z}_{2m}\}\), \(V_b = \{ b_j: j\in\mathbb{Z}_{2p+1}\}\), and \(V_c = \{ c_k: k\in\mathbb{Z}_{2q-1}\}\cup\{\infty\}\). We may take \(V_a\) and \(V_b\cup V_c\) to be the vertex sets of \(T\), and hence there exist a \(t\)-subset \(X\subseteq\mathbb{Z}_{2m}\) and an \(s\)-subset \(Y\subseteq\mathbb{Z}_{2q-1}\) such that \[\begin{align*} |N_T(a_i)| &= m\text{ if $i\in X$ and $0$ if $i\notin X$},\\ |N_T(b_j)| &= m,\\ |N_T(\infty)| &= 2m,\text{ and}\\ |N_T(c_k)| &= 2m-q\text{ if $k\in Y$ and $m-q$ if $k\notin Y$}. \end{align*}\]
Without loss of generality, we may assume that \(N_T(b_0)=\{a_0,\dots,a_{m-1}\}\).
Let \(G\) be a graph isomorphic to \(K_n\) with vertex set \(V_a\cup V_b\cup V_c\). For each \(k\in \mathbb{Z}_{2q+1}\), let \(N_T'(c_k)\) be a \((m-q)\)-subset of \(N_T(c_k)\); note that \(|N_T(c_k)\backslash N_T'(c_k)|=m\) when \(k\in Y\) and \(N_T'(c_k)=N_T(c_k)\) when \(k\notin Y\). Let \(\{N_1,N_2\}\) partition \(N_T(\infty)\) such that \(|N_1|=|N_2|=m\). For each \(i\in\mathbb{Z}_{2m}\), define \(x_i = b_0\) if \(i\in\{0,\dots,m-1\}\) and \(x_0=a_{i+m}\) if \(i\in\{m,\dots,2m-1\}\). For \(i\in \mathbb{Z}_{2m}\), \(j\in\mathbb{Z}_{2p+1}\), and \(k\in\mathbb{Z}_{2q-1}\), define the subgraphs \(A_i\), \(B_j\), and \(C_k\) of \(G\) as the stars \[\begin{align*} A_i &= (a_i;\{a_{i+1},\dots,a_{i+m-1},x_i\}),\\ B_j &= (b_j;\{b_{j+1},\dots,b_{j+p}\}\cup V_c),\text{ and}\\ C_k &= (c_k;\{c_{k+1},\dots,c_{k+q-1}\}\cup\{\infty\}\cup N_T'(c_k)). \end{align*}\]
For each \(i\in X\), \(j\in\mathbb{Z}_{2p+1}\backslash\{0\}\), and \(k\in Y\), define \[\begin{align*} A_i’ &= (a_i;N_T(a_i)),\\ B_j’ &= (b_j;N_T(b_j)),\text{ and}\\ C_k’ &= (c_k;N_T(c_k)\backslash N_T'(c_k)), \end{align*}\] and define \(C_\infty’\) and \(C_\infty”\) as \((\infty;N_1)\) and \((\infty;N_2)\), respectively. Next, define \(\mathcal{A}\), \(\mathcal{B}\), \(\mathcal{C}\), \(\mathcal{A}’\), \(\mathcal{B}’\), and \(\mathcal{C}’\) as the sets \[\begin{align*} \mathcal{A} &= \{ A_i: i\in\mathbb{Z}_{2m}\}, & \mathcal{A}’ &= \{ A_i’: i\in X\},\\ \mathcal{B} &= \{ B_j: j\in\mathbb{Z}_{2p+1}\},& \mathcal{B}’ &= \{ B_j’: j\in\mathbb{Z}_{2p+1}\backslash\{0\}\},\\ \mathcal{C} &= \{ C_k: k\in\mathbb{Z}_{2q+1}\},\text{ and} & \mathcal{C}’ &= \{ C_k’: k\in Y\}\cup\{C_\infty’,C_\infty”\}. \end{align*}\]
Finally, define \(\mathcal{D} = \mathcal{A}\cup\mathcal{B}\cup\mathcal{C}\cup\mathcal{A}’\cup\mathcal{B}’\cup\mathcal{C}’\). Using an argument identical to that which is used in the proof of Lemma 4.1 (by replacing \(\mathbb{Z}_{2q+1}\) with \(\mathbb{Z}_{2q-1}\) where appropriate), we have that \(\mathcal{D}\) is primitive. ◻
Lemma 4.3. class=”math inline”>\(m\geq 4\), \(m\) even, and \(n\) be an integer such that \(3m\leq n <4m\) and \((m,n)\) is valid. Then \(K_n\) has a primitive \(m\)-star decomposition.
Proof. First, observe that if \(m\) is even, then \((m,3m)\) and \((m,3m+1)\) are not valid. Furthermore, since \(m\geq 3\), we have that \((m,3m+2)\) and \((m,4m-1)\) are not valid. Hence, we may assume that \(3m+3\leq n\leq 4m-2\).
Suppose that \(n\) is even. Let \(p = n-1-3m\) and \(q = 2m – \frac n2\). Then \(p\geq 2\), \(1\leq q\leq m-2\), \(m = p + 2q + 1\) and \(n = 4p + 6q + 4\). Therefore, by Lemma 4.1, \(K_n\) has a primitive \(m\)-star decomposition.
Suppose that \(n\) is odd. Let \(p=n-1-3m\) and \(q=2m-(n-1)/2\). Then \(p\geq 2\) and \(1\leq q\leq m-2\), \(m=p+2q\), and \(n= 4p+6q+1\). Therefore, by Lemma 4.2, \(K_n\) has a primitive \(m\)-star decomposition. ◻
Observe that the proof of Lemma 4.3 only uses the hypothesis that \(m\) is even to discount \((m,3m)\) and \((m,3m+1)\) from being valid. One could simply produce a primitive \(m\)-star decomposition of \(K_{3m}\) and \(K_{3m+1}\) when \(m\) is odd using the earlier constructions, and then Lemma 4.3 would hold for all \(m\geq 3\). However, the next two lemmas have constructions which depend heavily on \(m\) being even, and thus it is necessary to have distinct constructions, based on the parity of \(m\).
Lemma 4.4. Let \(m\) be a positive even integer, \(m\geq 4\), \(K_{2m-1}\) be a complete graph on a vertex set \(W\), and \(V\) be a vertex set of cardinality \(m+1\) disjoint from \(W\). Then \(K_{2m-1}+V\) has a primitive \(m\)-star decomposition which contains two stars \(Q\) and \(R\) such that \(r(Q)\in W\), \(r(R)\in (P(Q)\cap W)\), and \(|V\cap P(Q)\cap P(R)|\geq 2\).
Proof. Let \(\{V_1,V_2\}\) be a partition of \(V\) where \(|V_1|=(m+2)/2\) and \(|V_2|=m/2\), and identify \(W\) with the ring of integers modulo \(2m-1\), \(\mathbb{Z}_{2m-1}\). Let \(x\in V_1\). For each \(i\in W\), define the \(m\)-stars \(S_i\) and \(T_i\) as \[\begin{align*} S_i &= (i;V_1\cup \{i+1,\dots,i+(m/2)-1\})\text{ and}\\ T_i &= (i;V_2\cup \{i+(m/2),\dots,i+m-1\}). \end{align*}\]
Define \(\mathcal{G}=\{ S_i,T_i:i\in W\}\), and as such, \(\mathcal{G}\) is a decomposition of \(G\).
Suppose \(\mathcal{S}\) is a subdecomposition of \(\mathcal{G}\). Then \(\mathcal{S}\) is nonempty; first suppose that \(S_k\in \mathcal{S}\) for some \(k\in W\). It follows that \(x,k+1\in V(\mathcal{S})\) and, since \(\{x,k+1\}\in E(S_{k+1})\), we have that \(S_{k+1}\in\mathcal{S}\). Applying this iteratively gives that \(\{S_i:i\in W\}\subseteq \mathcal{S}\), and hence \(W\cup V_1\subseteq V(\mathcal{S})\). Since \(k,k+(m/2)\in V(\mathcal{S})\), it follows that \(T_k\in\mathcal{S}\) and hence \(V_2\subseteq V(\mathcal{S})\). Therefore \(\mathcal{S}=\mathcal{G}\) by Lemma 2.5(b).
If \(T_k\in \mathcal{S}\) for some \(k\in W\), then \(k+(m/2),k+(m/2)+1\in V(\mathcal{S})\), and since edge \(\{k+(m/2),k+(m/2)+1\}\in E(S_{k+(m/2)})\), it follows that \(S_{k+(m/2)}\in \mathcal{S}\). So \(\mathcal{S}=\mathcal{G}\) from the above argument. Therefore \(\mathcal{G}\) is primitive by Lemma 2.5(d).
Observe that by defining \(Q=T_0\) and \(R=T_{m/2}\), we have that \(Q\) and \(R\) satisfy their conditions outlined in the lemma statement. ◻
Lemma 4.5. Let \(a\) and \(m\) be positive integers such that \(a>m\geq 4\) and \(m\) is even. If \(K_a\) has a primitive \(m\)-star decomposition, then \(K_{a+2m}\) has a primitive \(m\)-star decomposition as well.
Proof. Let \(U\), \(V\), and \(W\) be sets with cardinalities \(a-m\), \(m\), and \(2m-1\), respectively, and let \(\infty\) be an element such that \(\infty\notin (U\cup V\cup W)\). Let \(W_1\) be a subset of \(W\) with cardinality \(m\) and \(W_2 = (W\backslash W_1)\cup\{\infty\}\). Then \(\{H,J,F_1,F_2,E\}\) is a decomoposition of \(K_{a+2m}\), where \(H=K_{a}\) with vertex set \(U\cup V\), \(J=K_{2m-1}+(V\cup\{\infty\})\) with vertex set \(W\cup V\cup\{\infty\}\), \(F_1=K_{a-m,m}\) with \(U\) and \(W_1\) as the parts of its vertex set, \(F_2=K_{a-m,m}\) with \(U\) and \(W_2\) as the parts of its vertex set, and \(E = (\infty;V)\).
Let \(\mathcal{H}\), \(\mathcal{J}\), \(\mathcal{F}_1\), and \(\mathcal{F}_2\) be the \(m\)-star decompositions of \(H\), \(J\), \(F_1\), and \(F_2\) given by the hypothesis and Lemmas 4.4 and 2.4. Then \(\mathcal{H}\) and \(\mathcal{J}\) are primitive and \(\mathcal{H}\cup\mathcal{J}\cup\mathcal{F}_1\cup\mathcal{F}_2\cup\{E\}\), which we now denote as \(\mathcal{G}\), is an \(m\)-star decomposition of \(K_{a+2m}\).
Let \(Q\in\mathcal{J}\) and \(R\in\mathcal{J}\) such that \(r(R)\in (P(Q)\cap W)\) and \(|V\cap P(Q)\cap P(R)|\ \geq 2\); let \(a=r(Q)\), \(b=r(R)\), and \(\{c,d\}\subseteq V\cap P(Q)\cap P(R)\) where \(c\neq d\). Without loss of generality, we may assume there exists a star \(S\in \mathcal{H}\) such that \(r(S)=c\), \(d\in P(S)\), and \(P(S)\cap U\) is nonempty; let \(e\in P(S)\cap U\). Also, without loss of generality, we may assume \(\{a,b\}\subseteq W_1\). Then \((e;W_1)\in\mathcal{F}_1\), and let \(T=(e,W_1)\). See Figure 3(a).
Similar to the proof of Lemma 3.4, let \(\mathcal{K}=\{Q,S,T\}\), and define \(\mathcal{K}’\) as the set of subgraphs \(\{Q’,S’,T’\}\), where \(Q’\), \(S’\), and \(T’\) are defined as given in (3). See Figure 3(b). Again, we define \(\mathcal{G}’=(\mathcal{G}\backslash\mathcal{K})\cup\mathcal{K}’\), and we now show that \(\mathcal{G}’\) is a primitive \(m\)-star decomposition of \(K_{a+2m}\). Similar to the proof of Lemma 3.4, we need only to demonstrate that (d) and (e) of Lemma 2.8 are satisfied.
Let \(\mathcal{S}\) be a subdecomposition of \(\mathcal{G}\), and assume that \(\mathcal{S}\cap(\mathcal{H}\cup\mathcal{J})\) is empty. Then \(\mathcal{S}\subseteq \mathcal{F}_1\cup \mathcal{F}_2\cup \{E\}\) and \(\mathcal{S}\) is nonempty. Then either \((x;W_1)\in \mathcal{S}\) or \((x;W_2)\in\mathcal{S}\) for some \(x\in U\), or \(E\in\mathcal{S}\). So either \(W_1\subseteq \mathcal{S}\), \(W_2\subseteq\mathcal{S}\), or \(V\subseteq\mathcal{S}\). In the first two cases, it follows that \(\mathcal{J}\cap\mathcal{S}\) is nonempty, and \(\mathcal{H}\cap\mathcal{S}\) is nonempty in the latter case, and both result in a contradiction. So (d) is satisfied in Lemma 2.8.
Now, let \(\mathcal{S}’\) be a subdecomposition of \(\mathcal{G}’\). First, we show that \(\mathcal{S}’\cap\mathcal{K}’\) is nonempty. Suppose to the contrary. Then \(\mathcal{S}’\) is also a subdecomposition of \(\mathcal{G}\) and \(\{Q,S,T\}\cap\mathcal{S}\) is empty. However, since \(\mathcal{S}’\) is nontrivial, \(\mathcal{S}’\) must intersect nontrivially with either \(\mathcal{H}\), \(\mathcal{J}\), \(\mathcal{F}_1\), or \(\mathcal{F}_2\). If \(\mathcal{S}’\cap\mathcal{H}\) is nonempty, then \(\mathcal{H}\subseteq\mathcal{S}’\) by Lemma 2.6, meaning \(S\in\mathcal{S}\), which is a contradiction. Similarly, if \(\mathcal{S}\cap\mathcal{J}\) is nonempty, it follows that \(T\in\mathcal{S}’\), which also contradicts. So \(\mathcal{S}’\subseteq(\mathcal{F}_1\cup\mathcal{F}_2\cup\{E\})\), when then by an identical argument used earlier, \(W_1\subseteq V(\mathcal{S}’)\), \(W_2\subseteq V(\mathcal{S}’)\), or \(V\subseteq V(\mathcal{S}’)\), and hence either \(\mathcal{S}’\cap\mathcal{J}\) or \(\mathcal{S}’\cap\mathcal{H}\) is nonempty, which is a contradiction. Therefore \(\mathcal{S}’\cap\mathcal{K}’\) is nonempty.
Using the identical argument given in the proof of Lemma 3.4, it follows that \(\mathcal{K}’\subseteq\mathcal{S}’\), which satisfies condition (e) in Lemma 2.8. Hence \(\mathcal{G}’\) is primitive, and therefore \(K_{a+2m}\) has a primitive \(m\)-star decomposition. ◻
To complete the proof of Theorem 1.4, we must first state a special case of the result proved by Dinavahi and Rodger. [4]
Theorem 4.6. Let \(n\) be a positive integer. Let \(P_2\) denote a path with two edges. Then \(K_n\) has a primitive \(P_2\)-decomposition if and only if \(n=1\) or \((2,n)\) is valid.
Since a \(2\)-star is isomorphic to \(P_2\), by combining the results of Theorems 1.3 and 4.6 with Lemmas 3.2, 4.3, and 4.5, we admit the following classification.
Theorem 4.7. Let \(m\geq 2\) be an even integer. Then \(K_n\) has a primitive \(m\)-star decomposition if and only if \((m,n)\) is valid.
Finally, observe that a \(1\)-star is isomorphic to \(K_2\), which implies that each subgraph in a \(1\)-star decomposition gives rise to a subdecomposition. This fact, along with Theorems 3.5 and 4.7, imply Theorem 1.4.