We use Rosa-type labelings to decompose complete graphs into unicyclic, disconnected, non-bipartite graphs on nine edges. For any such graph \(H\), we prove there exists an \(H\)-design of \(K_{18k+1}\) and \(K_{18k}\) for all positive integers \(k.\)
All graphs considered herein are without loops, parallel edges, and isolated vertices. A decomposition \(\mathcal{D}\) of a graph \(G\) is an edge-spanning set of pairwise edge-disjoint subgraphs \(H_i\). More precisely, we say \(\mathcal{D}=\{H_i\}\) where \[E\left(G\right)=\bigcup\limits_{\mathcal{D}}\,E\left(H_i\right)\hspace{0.2cm}\textrm{and}\hspace{0.2cm}E(H_i)\cap E(H_j)=\emptyset\hspace{0.2cm}\textrm{for all }i\neq j.\]
This paper focuses on decompositions above where \(G\cong K_p\) and \(H_i\cong H\) for all \(H_i\in\mathcal{D}\). Such a decomposition is called an \(H\)-design of \(K_p\) or rather a \((K_p,H)\)-design.
For such a graph \(H\) with vertex labeling \(f:V(H)\rightarrow\mathbb{Z}_p\), the term clicking is used when the isomorphism \(i\to i+1\) is applied to the image of \(f\). When a design \(\mathcal{D}\) is formed by clicking, we say \(\mathcal{D}\) is cyclic; a formal definition will follow.
When a graph contains exactly one cycle, it is said to be unicyclic. Let \(H\) be a unicyclic, disconnected, non-bipartite graph on nine edges. \(H\) must then be a supergraph of an odd cycle – namely \(C_3\), \(C_5\), or \(C_7\). Moreover, it is shown in [2] that only four classes of complete graphs \(K_p\) admit \(H\)-designs. These are those with \(p=18k\), \(p=18k+1\), \(p=18k+9\), and \(p=18k+10\) for some non-negative integer \(k\). This paper is concerned only with the first two values of \(p\) for \(k\geq1\). We aim to find \(H\) designs of \(K_{18k+1}\) and \(K_{18k}\) for all non-isomorphic \(H\) and all positive integers \(k\). To do so, we will build upon several tools developed by A. Rosa and numerous other researchers.
There has been a wave of recent progress in classifying graphs on \(n\) edges for which \(K_{2nk+1}\) and \(K_{2nk}\) admit designs. For an extensive overview of those with \(n\leq8\), see the work of Froncek and Kubesa in [5].
Our effort is designed to complement a series of papers aiming to explore the nine-edge case. For unicyclic graphs, the territory is almost completely documented. The full catalog of unicyclic, connected graphs on nine edges is presented in [1]. Such graphs that are instead disconnected and bipartite are explored in [2]. We aim to add non-bipartite graphs to these findings, thus settling the unicyclic, nine-edge case for \(K_{18k+1}\) and \(K_{18k}\).
We begin by introducing some tools that will be important in our inquiry. The first of which will be Rosa’s \(\rho\)-labeling defined in [8].
Definition 3.1. Let \(H\) be a graph on \(n\) edges. A \(\rho\)-labeling \(f\) is an injection \(f:V(H)\rightarrow\{0,1,2,\dots,2n\}\) inducing the mapping \(\ell:E(H)\rightarrow\{1,2,\dots,n\}\) defined as \[\ell(uv)=\min\{\lvert f(u)-f(v)\rvert,\,\,2n+1-\lvert f(u)-f(v)\rvert\},\] where the image satisfies \[\{\ell(uv):uv\in E(H)\}=\{1,2,\dots,n\}.\]
In other words, we assign the elements of the integer group \(\mathbb{Z}_{2n+1}\) to the vertices of \(H\) such that we yield \(\{1,2,\dots, n\}\) as the image of \(\ell\), often called the length function. This idea will not be used explicitly; instead, it serves as a stepping stone to a more specialized set of tools. The following definition was introduced by Bunge et al. in [4].
Definition 3.2. Let \(H\) be a graph with tripartition \((A,B,C)\) and \(n\) edges. A \(\rho\)-tripartite labeling \(f\) of \(H\) is a \(\rho\)-labeling with the additional properties:
(\(\alpha1\)) \(f(a)<f(x)\) for all \(ax\in E(H)\) where \(a\in A\).
(\(\alpha2\)) For every edge \(bc\) where \(b\in B\) and \(c\in C\), there exists edge \(b'c'\) where \(b'\in B\) and \(c'\in C\) such that \(\lvert f(b)-f(c)\rvert+\lvert f(b')-f(c')\rvert=2n\).
(\(\alpha3\)) For every \(b\in B\) and \(c\in C\), \(\lvert f(b)-f(c)\rvert\neq2n\).
Regarding property \(\alpha2\), the edge \(b'c'\) is called the complement of \(bc\), though these edges need not be distinct. When \(bc=b'c'\), this edge is said to be self-complementary. Our catalogs will only feature self-complementary edges.
Definition 3.2 can be modified to yield an equally useful tool. The following idea was introduced by Bunge in [3].
Definition 3.3. Let \(H\) be a graph on \(n\) edges with tripartition \((A,B,C)\) where \(uv\in E(H)\) is a pendant edge with \(\deg(v)=1\). A 1-rotational \(\rho\)-tripartite labeling \(f\) of \(H\) is an injection \(f:V(H)\rightarrow\{0,1,\dots,2n-2\}\cup\{\infty\}\) inducing length function \(\tilde{\ell}:E(H)\rightarrow\{1,2,\dots,n-1\}\cup\{\infty\}\) defined as \[\tilde{\ell}(xy)=\begin{cases} \min\{\lvert f(x)-f(y)\rvert,\,\,2n-1-\lvert f(x)-f(y)\rvert\}, & \textrm{if } x,y\neq v ,\\ \infty, & \textrm{otherwise}, \end{cases}\] with the additional properties:
(\(\beta1\)) \(\{\tilde{\ell}(xy):xy\in E(H)\}=\{1,2,\dots,n-1\}\cup\{\infty\}\).
(\(\beta2\)) \(f(v)=\infty\).
(\(\beta3\)) \(f(a)<f(x)\) for every \(ax\in E(H)\backslash\{uv\}\) where \(a\in A\) and \(x\in B\cup C\).
(\(\beta4\)) For every edge \(bc\) where \(b\in B\) and \(c\in C\), there exists edge \(b'c'\) where \(b'\in B\) and \(c'\in C\) such that \(\lvert f(b)-f(c)\rvert+\lvert f(b')-f(c')\rvert=2n\).
Many of the results in this paper are cyclic designs obtained by clicking the labelings above. Cyclic designs were briefly discussed in a previous section, but we now provide a formal definition.
Definition 3.4. An \(H\)-design \(\mathcal{D}\) of the complete graph \(K_p\) is cyclic if there exists an ordering \((x_0, x_1, \dots, x_{p-1})\) of the vertices of \(K_p\) and a permutation \(\varphi:V\left(K_p\right)\rightarrow V\left(K_p\right)\) defined by \(\varphi (x_j) = x_{j+1}\) for \(j=0,1,\dots, p-1\) inducing an automorphism on \(\mathcal{D}\), where the addition is performed modulo \(p\).
We now introduce some related theorems that will be used frequently. The first of which was proved by Bunge et al. in [4] and the latter by Bunge in [3].
Theorem 3.5(Bunge, et al., 2013).Let \(H\) be a tripartite graph with \(n\) edges. If \(H\) admits a \(\rho\)-tripartite labeling, then there exists a cyclic \((K_{2nk+1},H)\)-design for all positive integers \(k\).
Theorem 3.6(Bunge, 2019).Let \(H\) be a tripartite graph on \(n\) edges. If \(H\) admits a 1-rotational \(\rho\)-tripartite labeling, then there exists a 1-rotational \((K_{2nk},H)\)-design for all positive integers \(k\).
These theorems are useful on their own, but they can complete our task most efficiently when combined. To do this, we must first discuss another labeling defined by Rosa in [8].
Definition 3.7. If a \(\rho\)-labeling is constructed using the restrictive length function \(\ell(uv)=\lvert f(u)-f(v)\rvert\), then it is called a \(\sigma\)-labeling.
We will combine this restricted length function with Definition 3.2 to construct a new labeling which we will call the \(\sigma^*\)-tripartite labeling.
Definition 3.8. Let \(H\) be a graph on \(n\) edges with vertex tripartition \((A,B,C)\). A \(\sigma^*\)-tripartite labeling \(f\) of \(H\) is a \(\rho\)-tripartite labeling with the additional properties:
(\(\mathcal{C}1\)) \(\ell(xy)=\lvert f(x)-f(y)\rvert\)
(\(\mathcal{C}2\)) \(\max\{f(x):x\in V(H)\}=2n-2\)
(\(\mathcal{C}3\)) There is a pendant edge \(uv\) of length \(n-1\) that does not join \(B\) and \(C\).
We will eventually be labeling supergraphs of \(C_3\). For such \(H\), \(\sigma^{*}\)-tripartite labelings do not present so easily. In view of this, we introduce a variant that allows one exception to \(\mathcal{C}1\) under certain circumstances. Due to this deviation from the restrictive length function, we call this the \(\rho^*\)-tripartite labeling.
Definition 3.9. Let \(H\) be a graph on \(n\) edges with vertex tripartition \((A,B,C)\). A \(\rho^*\)-tripartite labeling \(f\) of \(H\) is a \(\rho\)-tripartite labeling with the additional properties:
(\( {D}1\)) \(\ell(xy)=2n+1-\lvert f(x)-f(y)\rvert=n-1\) for exactly one edge \(st\) and \(\ell(xy)=\lvert f(x)-f(y)\rvert\) otherwise. We add that \(st\) does not join \(B\) and \(C\).
(\( {D}2\)) \(\max\{f(x):x\in V(H)\}=2n-2\)
(\( {D}3\)) There is a pendant edge \(uv\) of length \(n-3\) that does not join \(B\) and \(C\).
Regarding \( {D}\)1, recall that our paper only uses self-complementary edges. If this edge \(st\) were to join \(B\) and \(C\), we could not satisfy \(\beta4\) in Definition 3.3.
We can combine these two labelings with Theorems 3.5 and 3.6 to yield the following result.
Theorem 3.10. Let \(H\) be a graph on \(n\) edges with tripartition \((A,B,C)\). If \(H\) admits a \(\sigma^*\)-tripartite or \(\rho^*\)-tripartite labeling, then there exist \(H\)-designs of \(K_{2nk+1}\) and \(K_{2nk}\) for all positive integers \(k\).
Proof. Since both labelings are special cases of Definition 3.2, the decomposition of \(K_{2nk+1}\) for all \(k\in\mathbb{N}\) follows from Theorem 3.5.
Let \(H\) be a graph on \(n\) edges that admits a \(\sigma^*\)-tripartite labeling \(f_{\sigma}^*\) with \(uv\in E(H)\) where \(\deg(v)=1\) and \(\ell(uv)=n-1\). We can easily convert \(f_{\sigma}^*\) into a 1-rotational \(\rho\)-tripartite labeling \(\tilde{f}^{3}_{\rho}\) by relabeling \(f_{\sigma}^*(v)\to\infty\). This alters the edge of length \(n-1\) and also satisfies \(\beta2\); we now check the other three properties of this new labeling. Note that \(\beta3\) is preserved from \(\alpha1\), as \(E(H)\backslash\{uv\}\subset E(H)\). From \(\mathcal{C}3\), there is no edge \(bc\) with \(\ell(bc)=\infty\) where \(b\in B\) and \(c\in C\), thus every edge \(bc\) retains its complement, satisfying \(\beta4\).
Let \(st\in E\left(H\right)\) denote the edge such that \(\ell\left(st\right) = n\). To check \(\beta1\), we need to show that \(\tilde{\ell}\left(st\right) = n-1\), with no other edge lengths altered apart from \(\ell\left(uv\right) = n-1\) to \(\tilde{\ell}\left(uv\right) = \infty\). To do so, we rewrite \(\tilde{\ell}\) from Definition 3.3 as \[\tilde{\ell}(xy)=\begin{cases} \min\{\ell\left(xy\right),\,2n-1-\ell\left(xy\right)\}, & \textrm{if } x,y\neq v ,\\ \infty, & \textrm{otherwise}, \end{cases}\] where \(\ell(xy)=\left\lvert f^{*}_{\sigma}(x)-f^{*}_{\sigma}(y)\right\rvert\), our original length function. For brevity, we will use \(\ell\) to generically denote \(\ell\left(xy\right)\). We will now find all edge lengths for which \(\ell\) exceeds \(2n-1-\ell\); these are the edge labels that will be remapped as we move from \(f_{\sigma}^*\) to \(\tilde{f}^{3}_{\rho}\). Consider \[\{\ell:\ell>2n-1-\ell\}=\{\ell:\ell>n-1/2\}=\{\ell:\ell\geq n\}.\]
It follows that there is only one edge length for which \(\tilde{\ell}(uv)\) favors \(2n-1-\ell\) and it is \(n\); this edge length then becomes \(2n-1-n=n-1\) under \(\tilde{\ell}\), as desired. In summary, this transformation from \(f_\sigma^*\) to \(\tilde{f}^{3}_\rho\) has changed our image from \(\{1,2,\dots,n\}\) to \(\{1,2,\dots,n-1\}\cup\{\infty\}\), satisfying \(\beta1\).
Now suppose \(H\) instead admits a \(\rho^*\)-tripartite labeling \(f_\rho^*\) with \(uv\in E(H)\) where \(\deg(v)=1\) and \(\ell(uv)=n-3\). In relabeling \(f_\rho^*(v)\to\infty\), the arguments for \(\beta2\) and \(\beta3\) are unchanged and thus follow from \(\alpha1\) and \( {D}3\). Condition \(\beta4\) follows from \( {D}3\) and \( {D}1\), as no vertex labels of complementary edges are altered. Furthermore, recall that no edge length with \(\ell(xy)=\left\lvert f_\rho^*(x)-f_\rho^*(y)\right\rvert<n\) is altered under \(\ell\to\tilde{\ell}\) (with the exception of \(n-3\to\infty\)). Also, we have already shown that the edge of length \(n\) is remapped to \(n-1\).
To complete this proof, we need only show that the edge previously of length \(n-1\) is assigned length \(n-3\) under \(\tilde{\ell}\). Let \(d=\left\lvert f_\rho^*(a)-f_\rho^*(b)\right\rvert\). From \( {D}1\), we have \(\ell(ab)=2n+1-d=n-1\) which then implies \(2n+1-d<d\) by Definition 3.1. It follows that \(2n-1-d<d\) so that \(\tilde{\ell}(ab)=2n-1-d\). With \(\ell(ab)=2n+1-d=n-1\), we have \(\tilde{\ell}(ab)=2n-1-d=n-3\), effectively transforming the image of our length function from \(\{1,2,\dots,n\}\) to \(\{1,2,\dots,n-1\}\cup\{\infty\}\).
Finally, we note that \(\mathcal{C}2\) and \( {D}2\) ensure the codomain of \(\tilde{f}^{3}_\rho\) is satisfied in \(f_\sigma^*\to\tilde{f}^{3}_\rho\) and \(f_\rho^*\to\tilde{f}^{3}_\rho\), respectively. We now invoke Theorem 3.6 for a 1-rotational \(H\)-design of \(K_{18k}\) for all \(k\in\mathbb{N}\) and we are done. ◻
This idea is very useful in cutting computational costs. Rather than finding two labelings for each graph that satisfy Theorems 3.5 and 3.6, we can invoke both simultaneously by finding one as in Definitions 3.8 or 3.9.
We note that Definition 3.9 can be generalized to allow for more than one exception to the restricted length function, but this will not be necessary for our inquiry and is thus omitted.
The remainder of this paper is dedicated to finding \(\sigma^*\)-tripartite or \(\rho^*\)-tripartite labelings for all unicyclic, disconnected, non-bipartite graphs on nine edges, up to isomorphism.
We will now demonstrate how Theorem 3.10 works using our smallest class of graphs – those \(H\) featuring cyclic component \(C_7\). We first present \(\rho\)-tripartite labelings for all three non-isomorphic graphs in this family. Partite sets are vertically oriented and dashed lines mark pendant edges of length \(8\).
These labelings satisfy all conditions of Definition 3.8 and are thus \(\sigma^*\)-tripartite labelings. Using the transformation described in the proof of Theorem 3.10, we obtain 1-rotational \(\rho\)-tripartite labelings of these same graphs. The following figures depict these changes.
Only two changes have occurred here. The edge previously of length \(8\) now reads \(\infty\), and the edge previously of length \(9\) assumes a length of \(8\) to take its place. The latter is a result of our shift from \(\ell\) to \(\tilde{\ell}\). This leaves us with a 1-rotational \(\rho\)-tripartite labeling of the same graph satisfying all conditions of Definition 3.3.
We now consider supergraphs of \(C_5\). This catalog is much longer than its predecessor. We now present \(\sigma^*\)-tripartite labelings for all such graphs \(H\) up to isomorphism. Partite sets are again vertically oriented and edge labels are now omitted. Graphs are sorted primarily by the number of trees attached to the cyclic component, then by the number of trees in the accompanying forest.
Our final class considers those \(H\) with cyclic component \(C_3\). For such graphs, we note that \(\sigma^*\)-tripartite labelings are difficult to come by. Instead, we rely on Definition 3.9. The figure below provides a brief example.
On the left, we have a \(\rho\)-labeling satisfying Definition 3.9. It is therefore a \(\rho^{*}\)-tripartite labeling and can easily be transformed into a 1-rotational \(\rho\)-tripartite labeling. While similar, the process is a bit more complex than that of its \(\sigma^{*}\) counterpart. The pendant vertex on the edge of length 6 is remapped to \(\infty\), and the edge length follows suit. The 1-rotational length function then remaps the edges of length 9 and 8 to 8 and 6, respectively. The result is a valid 1-rotational \(\rho\)-tripartite labeling that can break down the odd-regular \(K_{18k}\). A matrix representation of the mapping is given below: \[\begin{bmatrix} 1\\ 2\\ 3\\ 4\\ 5\\ 6\\ 7\\ 8\\ 9 \end{bmatrix} \rightarrow \begin{bmatrix} 1\\ 2\\ 3\\ 4\\ 5\\ {\color{red}{\infty}}\\ 7\\ {\color{red}{6}}\\ {\color{red}{8}} \end{bmatrix}.\]
We now present \(\rho^*\)-tripartite labelings for all non-isomorphic \(H\). Graphs are again sorted by the number of trees attached to the cyclic component, then by the number of trees in the accompanying forest; when this first number changes, a new row will be started.
We have exhausted the 215 unicyclic, disconnected, non-bipartite graphs on nine edges. These labelings can be combined with Theorem 3.10 and the findings of [2] to yield the following result.
Lemma 7.1. Let \(H\) be a unicyclic, disconnected graph on nine edges. Then there exist \(H\)-designs of \(K_{18k+1}\) and \(K_{18k}\) for all \(k\in\mathbb{N}\).
Proof. The proof for bipartite \(H\) is given in [2]. For all non-bipartite \(H\), we have presented \(\sigma^*\)-tripartite or \(\rho^*\)-tripartite labelings. The desired result follows from Theorem 3.10. ◻
We now combine the findings of this paper with the catalog presented in [1] to obtain our main result.
Theorem 7.2. Let \(H\) be a unicyclic graph on \(9\) edges. If \(H\not\cong C_9\), then there exist \(H\)-designs of \(K_{18k+1}\) and \(K_{18k}\) for all \(k\in\mathbb{N}\).
Proof. In [1], it is shown that all unicyclic, connected graphs on nine edges decompose \(K_{18k+1}\) and \(K_{18k}\) for all \(k\in\mathbb{N}\), with the exception of \(H\cong C_9\). This is due to the odd-regularity of \(K_{18k}\), as no decomposition could be permitted by a \(2\)-regular graph. With connected graphs cataloged, the result follows from Lemma 7.1 ◻
This paper, along with its complement [2], omits consideration of \(K_p\) when \(p=18k+9\) and \(p=18k+10\). The tools for such an inquiry are not included in this effort. Furthermore, this paper merely settles the unicyclic case on nine edges; further study may be conducted on the bicyclic and tricyclic cases, or perhaps on those graphs with more than nine edges (though likely unrealistic).
Additionally, decompositions of \(K_{18k+1}\) and \(K_{18k}\) into nine-edge forests have not been thoroughly explored. Some progress has been made in decomposing \(K_{2n+1}\) and \(K_{2n}\) into \(n\) edge forests, but this would only allow us to partially address our concerns when \(k=1\). For more details, see [6] and [7].
Finally, \(\rho^*\)-tripartite labelings can be generalized to allow for more than one exception to the restrictive length function. This technique could be extended to formally define a family of “chain-labelings,” which may cut the computational costs of further cataloging.