Let \(G\) be a disconnected tripartite unicyclic graph on seven edges with two or more connected components. We prove that \(G\) decomposes the complete graph \(K_{n}\) whenever \(n\equiv0,1\pmod{14}\) using labeling techniques.
A decomposition of a graph \(K\) is a collection of pairwise edge-disjoint subgraphs \(\Gamma=\{G_{1}, G_{2},\dots, G_{k}\}\) of \(K\) such that \(E(K)=E(G_{1})\cup E(G_{2})\cup\dots\cup E(G_{k})\). We call such a collection \(\Gamma\) a \(G\)-decomposition if all of its members are isomorphic to some graph \(G\). We refer to a \(G\)-decomposition of \(K_{n}\) as a \(G\)-design of order \(n\). If we take the vertex set of \(K\) to be \(\mathbb{Z}_{n}\) where \(|V(K)|=n\), and \(\pi:v\mapsto v+1\) is an automorphism of \(\Gamma\), we call \(\Gamma\) cyclic. If instead we take the vertex set of \(K\) to be \(\mathbb{Z}_{n-1}\cup\{\infty\}\) and \(\pi\) is an automorphism of \(\Gamma\) (with \(\infty + 1 = \infty\) by definition), we call \(\Gamma\) \(1\)-rotational. In 1967, Rosa [12] developed a family of graph labelings now referred to as ‘Rosa-type labelings’ which ensure various \(G\)-decompositions of infinite families of complete graphs exist if \(G\) admits such a labeling.
A graph is unicyclic if it contains exactly one cycle. If a unicyclic graph on \(7\) edges admits a \(\rho\)-tripartite and a \(1\)-rotational \(\rho\)-tripartite labeling (defined in Section 4), then it decomposes \(K_{14t+1}\) and \(K_{14t}\) for \(t\geq 1\). In this paper we show that the statement above holds for disconnected tripartite unicyclic graphs on \(7\) edges. A \(G\)-decomposition of \(K_n\) into graphs on \(7\) edges can exist only if \(7\) divides \(|E(K_n)|\). Therefore, a \(G\)-design of order \(n\) for a graph \(G\) on \(7\) edges can only be found if \(n\equiv 0,1\pmod{7}\). The labeling methods discussed in this paper cannot be used to find a \(G\)-design of \(K_{n}\) if \(n\equiv 7,8\pmod{14}\) because the number of distinct edge lengths in such a \(K_{n}\) is not a multiple of \(7\). Therefore, the scope of this paper is limited to the case where \(n\equiv 0,1\pmod{14}\).
The decomposition spectrum for graphs with up to six edges has been completely determined, although the latest results on some small classes of graphs with five or six edges have not been published yet. For an overview, see, [8].
Graphs with seven edges and five vertices were investigated in [3], [4], and [11]. Cui [7], Blinco [4], and Tian, Du, and Kang [13] studied connected graphs with seven edges and six vertices.
The only disconnected graph with seven edges and six vertices is \(K_4\cup K_2\). The spectrum for this graph was determined by Tian, Du and Kang [13].
All graphs with seven edges and seven vertices are either unicyclic or disconnected. We are not aware of any attempt to classify disconnected graphs with seven edges and seven vertices.
Froncek and Kubesa classified connected unicyclic bipartite graphs with seven edges [8] and disconnected bipartite graphs with seven edges and eight vertices (which are necessarily unicyclic) [9]. Decompositions for disconnected unicyclic bipartite graphs with seven edges and more than eight vertices were completely characterized by Banegas, Carlson, and Froncek [1].
Connected graphs with seven edges and eight vertices are trees, which were investigated by Huang and Rosa [10]. Forests with seven edges were studied by Banegas and Freyberg [2].
In this paper, we focus on disconnected tripartite unicyclic graphs.
Below we present a catalog of all disconnected unicyclic tripartite graphs on seven edges. There are 27 such graphs; 25 of them contain a triangle (shown in Figures 1–25), and 2 contain a pentagon (Figures 26–27).
Figures 1–15 show triangular graphs with two components, Figures 16–22 triangular graphs with three components, Figures 23–24 with triangular graphs with four components, and Figure 25 the triangular graph with five components. Figures 26 and 27 show the pentagonal graphs with two and three components, respectively.
Some definitions and tools taken from previous results in graph decompositions are shown here. These tools help identify if a graph \(G\) decomposes a certain \(K_m\) by labeling the vertices and edges of \(G\) such that certain conditions are met. However, before getting into more definitions and theorems, consider how a decomposition of the graph \(K_n\) into a subgraph \(G\) must behave. Note that \(K_m\) has \(\frac{m(m-1)}{2}\) edges. Since we want \(K_m\) to decompose into isomorphic copies of \(G\), the number of edges of \(G\) must divide \(\frac{m(m-1)}{2}\). As stated in the introduction, for the graphs that we are working with (all on 7 edges), they can only decompose complete graphs of form \(K_m\) where \(m \equiv 0, 1\pmod7\), as 7 divides \(\frac{m(m-1)}{2}\) only when \(m \equiv 0, 1\pmod{7}\).
In 1967, Rosa [12] introduced a definition of what he then called a graph \(\rho\)-valuation. This laid foundations for later generalizations or modifications that we will list below.
Definition 4.1. [12] Let \(G\) be a graph with \(n\) edges. A \(\rho\)-labeling of \(G\) is a one-to-one function \(f : V (G) \rightarrow \{0, 1,\dots, 2n\}\) inducing a function \(\ell : E(G) \rightarrow \{1, 2,\dots, n\}\) defined as \[\ell(uv) = \min\{|f(u)-f(v)|, 2n + 1 – |f(u)-f (v)|\},\] with the property that \(\{\ell(uv) : uv \in E(G)\} = \{1, 2,\dots , n\}\).
This definition is the foundation upon which everything else we will talk about is built. Finding \(\rho\)-labelings is instrumental in identifying decompositions of complete graphs, and many other methods striving to achieve the same goal are variations of \(\rho\)-labelings.
The following definition is a slight variation on \(\rho\)-labelings that is only defined for bipartite graphs.
Definition 4.2. [14] An ordered \(\rho\)-labeling is a \(\rho\)-labeling \(f\) for a bipartite graph \(G\) with bipartition \(\{A,B\}\) such that \(f(a) < f(b)\) for \(a\in A\) and \(b \in B\) when \(a\) and \(b\) are neighbors.
When we can ‘rotate’ one copy of \(G\) through the whole \(K_m\) to obtain a \(G\)-design, we speak about a cyclic decomposition.
Definition 4.3. Let \(V(K_m)=\mathbb{Z}_{m}\), and let \(G\) be a subgraph of \(K_m\). The length of an edge \(ij \in E(G)\) is defined as \(\min\{|i-j|,m-|i-j|\}\). The act of clicking \(G\) implies applying the permutation \(i \rightarrow i+1\) to \(V(G)\). A \(G\)-decomposition \(\Gamma\) of \(K_m\) is cyclic if clicking is an automorphism of \(\Gamma\).
Clicking can be intuitively thought of as visualizing a subgraph of some \(K_m\) on top of that \(K_m\) with vertices arranged around a regular polygon with \(m\) sides, and then “rotating” all vertices by one vertex clockwise to create a new subgraph isomorphic to the original. If one imagines continuing this act of clicking \(m\) times, we get an intuitive idea leading to the following theorem:
Theorem 4.4. [12]. A cyclic decomposition of the complete graph \(K_{2n+1}\) into subgraphs isomorphic to a given graph \(G\) with n edges exists if and only if there exists a \(\rho\)-labeling of the graph \(G\).
We see from Theorem 4.4 that we can only form a cyclic decomposition into subgraphs with 7 edges for the complete graph \(K_{15}\). However, our goal is to find \(G\)-designs for all \(K_{2nk+1}\) and Theorem 4.4 only covers one of the cases of our \(k\), where \(k=1\). Luckily, the Theorem was extended by El-Zanati, Vanden Eynden and Punnim [14] into a more general result about complete graphs of the form \(K_{2nk+1}\).
Theorem 4.5. [14] Let \(G\) be a bipartite graph with \(n\) edges. If \(G\) admits an ordered \(\rho\)-labeling, then there exists a cyclic G-decomposition of \(K_{2nk+1}\) for any positive integer k.
Definitions 4.1, 4.2 and Theorem 4.5 together create a relatively simple technique to find decompositions. Most other labelings of graphs in decomposition problems stem from a variation of \(\rho\)-labelings.
A variation extends the utility of ordered \(\rho\)-labelings (which only apply to bipartite graphs) to tripartite graphs. The changes needed such that there is a similar theorem to 4.5 for tripartite graphs necessarily requires a bit more of a complex labeling. Such generalization was obtained by Bunge, Chantasartrassmee, El-Zanati, and Vanden Eynden [6].
Definition 4.6. [6] Let \(G\) be a tripartite graph with \(n\) edges and vertex tripartition \(\{A,B,C\}\). A \(\rho\)-tripartite labeling of \(G\) is a \(\rho\)-labeling \(f\) that satisfies the following:
\(f(a) < f(v)\) for all \(av \in E(G)\) with \(a \in A\).
For every edge \(bc \in E(G)\) with \(b \in B\) and \(c \in C\), there exists an edge \(b'c' \in E(G)\) with \(b' \in B\) and \(c' \in C\) where \(|f(c)-f(b)|+|f(c')-f(b')|=2n\).
for any \(b \in B\) and \(c \in C\), \(|f(b)-f(c)| \ne 2n\).
The definition provides us with an important result that is one of the two main building blocks in our constructions.
Theorem 4.7. [6] Let \(G\) be a tripartite graph with \(n\) edges. If \(G\) admits a \(\rho\)-tripartite labeling, then there exists a cyclic \(G\)-decomposition of \(K_{2nk+1}\) for any positive integer \(k\).
Theorem 4.7 further expands the set of graphs we can decompose complete graphs into, specifically allowing for decompositions into tripartite graphs. The following definitions by Bunge [5] allow finding \(G\)-designs for complete graphs \(K_{2nk}\).
Definition 4.8. Let \(V(K_m)=\mathbb{Z}_{m-1} \cup \{\infty\}\), and let \(G\) be a subgraph of \(K_m\). The length of an edge \(ij \in E(G)\) where \(i,j \ne \infty\) is defined again as \(\min\{|i-j|,m-1-|i-j|\}\). The act of clicking \(G\) implies applying the same permutation \(i \rightarrow i+1\) to \(V(G)\) for integer vertices, with the convention \(\infty +1 \rightarrow \infty\). A \(G\)-decomposition \(\Gamma\) of \(K_m\) is \(1\)-rotational if clicking is an automorphism of \(\Gamma\).
Observe that this definition is very similar to that of a cyclic decomposition. Visually, when looking at \(K_m\), it looks like the standard way to draw \(K_m\) save for a vertex that lies in the center. Clicking a subgraph is rotating that subgraph about the center vertex.
Definition 4.9. [5] Let \(G\) be a graph with \(n\) edges, no isolated vertices, and a vertex \(w\) of degree \(1\). A \(1\)-rotational \(\rho\)-labeling of \(G\) is a one-to-one function \(f:V(G)\rightarrow[0,2n-2]\cup\{\infty\}\) where \(f(w) = \infty\) and such that \(f\) is a \(\rho\)-labeling of \(G- \{w\}\).
Definition 4.10. [5] Let \(G\) be a tripartite graph with \(n\) edges, vertex tripartition \(\{A,B,C\}\), and edge \(uw\) where deg \(w=1\). A 1-rotational \(\rho\)-tripartite labeling of \(G\) is a 1-rotational \(\rho\)-labeling \(f\) that satisfies the following:
\(f(w)= \infty\)
\(f(a) < f(v)\) for all \(av \in E(G)\) with \(a \in A, v\neq w\).
For every edge \(bc \in E(G)\) with \(b \in B\) and \(c\in C\), there exists an edge \(b'c' \in E(G)\) with \(b' \in B\) and \(c' \in C\) where \(|f(c)-f(b)|+|f(c')-f(b')|=2n\).
Definition 4.10 is to Definition 4.6 as the definition of a 1-rotational decomposition is to a cyclic decomposition. These tripartite labelings allow us to find decompositions after invoking the following theorem.
Theorem 4.11. [5] Let \(G\) be a tripartite graph with \(n\) edges and a vertex of degree 1. If \(G\) admits a 1-rotational \(\rho\)-tripartite labeling, then there exists a 1-rotational \(G\)-decomposition of \(K_{2nk}\) for any positive integer \(k\).
Below we present \(\rho\)-tripartite labelings and 1-rotational \(\rho\)-tripartite labelings for all 27 disconnected unicyclic tripartite graphs on 7 edges. In each figure, the \(\rho\)-tripartite labeling is on the left, and the 1-rotational \(\rho\)-tripartite labeling is on the right. The partite sets \(A, B, C\) are in one row each, and the row is labeled by the corresponding letter in the middle between the two labelings.
Now we are ready to prove our main result.
Theorem 5.1. Every disconnected tripartite unicyclic graph on seven edges decomposes complete graphs \(K_{14k}\) and \(K_{14k+1}\) for every \(k\geq1\).
Proof. The assertion follows directly from Theorems 4.7 and 4.11 and our labelings in Figures 28–54. ◻
Our result completely characterizes the existence of \(G\)-designs for disconnected unicyclic tripartite graphs for the complete graphs \(K_{14k}\) and \(K_{14k+1}\). A similar result for connected unicyclic tripartite graphs is currently under preparation by a subset of the authors of this paper.
The case of the complete graphs \(K_{14k+7}\) and \(K_{14k+8}\) remains still open.
The results presented in this paper for the graphs with two components were obtained by M. Heck and Y. Hong under the supervision and with co-authorship of B. Freyberg. Y. Hong’s participation was partially funded by the University of Minnesota Office of Undergraduate Research.
The results for the graphs with more than two components were obtained by D. Banegas, A. Carlson, L. Hawkes, C. Higgins, K. Jiang, N. Palme, D. Qi, X. Sundvall, and J. Waadevig as a part of a final project in a graph theory class taught at University of Minnesota Duluth in the spring of 2024 under the supervision and with co-authorship of D. Froncek.