On Decompositions of $K_{18k}$ and $K_{18k+1}$ into Certain Connected Bicyclic Graphs with Nine Edges

Bunge, Ryan; Froncek, Dalibor; Sailstad, Andrew

doi:10.61091/um119-05

Abstract

1. Introduction
2. Definitions and Tools
3. Relevant Theorems
4. Catalog of Graphs and Necessary Conditions
5. Graph Labelings
6. Graphs Without a Pendant Edge
7. Main Results
8. Conclusion
Conflict of Interest
Appendix

References

Utilitas Mathematica

Volume 119
Pages: 37-49

Research article

On Decompositions of $K_{18 k}$ and $K_{18 k + 1}$ into Certain Connected Bicyclic Graphs with Nine Edges

^¹, ^², ^³

¹Department of Mathematics, Illinois State University, USA

²Department of Mathematics and Statistics, University of Minnesota Duluth, USA

³School of Mathematics, University of Minnesota, Twin Cities, USA

Received: 04/03/2024
Accepted: 15/03/2024
Published: 31/03/2024

Copyright Link
License

Abstract

We show that connected, bicyclic graphs on nine edges with at least one cycle other than $C_{3}$ decompose the complete graphs $K_{18 k}$ and $K_{18 k + 1}$ , for $k \geq 1$ , when the necessary conditions allow for such a decomposition. This complements previous results by Freyberg, Froncek, Jeffries, Jensen, and Sailstad on connected bicyclic triangular graphs.

Keywords: Tripartite graphs,

ρ

-labelings, Graph decompositions

1. Introduction

The decomposition of a graph $H$ is a set of graphs ${G_{1}, G_{2}, \dots, G_{m}}$ such that for every edge $e$ in $H$ there exists exactly one graph $G_{i}$ , where $1 \leq i \leq m$ , such that $e \in E (G_{i})$ . If $H$ is the complete graph $K_{n}$ and all graphs $G_{i}$ are isomorphic to a fixed graph $G$ , then we say that there is a $G$ -design of $K_{n}$ . A graph is called bicyclic if it is a simple graph with exactly two cycles. A graph $G$ is connected if for every two vertices $u, v \in V (G)$ there exists a path between $u$ and $v$ . For this paper we will focus only on $G$ -designs of graphs $K_{n}$ where $G$ is a connected bicyclic graph on nine edges with at least one cycle that is not a 3-cycle, which we may refer to as non-triangular connected bicyclic graphs. The class of triangular unicyclic graphs—i.e., graphs with exactly two cycles of length three— with nine edges was completely characterized for $K_{18 k}$ and $K_{18 k + 1}$ by Freyberg, Froncek, Jeffries, Jensen, and Sailstad [1].

Assume $G$ is a non-triangular connected bicyclic graph with nine edges. Because a complete graph $K_{n}$ has $n (n - 1) / 2$ edges, it is apparent that $n \equiv 0, 1 (\mod 9)$ if there is a $G$ -design of $K_{n}$ . This paper considers only $G$ -designs of $K_{n}$ in the cases when $n \equiv 0, 1 (\mod 18)$ .

2. Definitions and Tools

In this section, we introduce the definitions and tools needed to find the desired decompositions. We begin with the definition of a $ρ$ -labeling:

Definition 1. [2] Given a simple graph $G$ with vertex set $V (G)$ and edge set $E (G)$ where $| E (G) | = n$ , a $ρ$ -labeling of $G$ is a one-to-one function $f : V (G) \to {0, 1, 2, \dots, 2 n}$ such that the induced length function $ℓ : E (G) \to {0, 1, 2, \dots, n}$ where $ℓ (u v) = min {| f (u) - f (v) |, 2 n + 1 - | f (u) - f (v) |}$ is a bijection.

For bipartite graphs, we can define a more restrictive (and more powerful) labeling.

Definition 2. [2] Let $G$ be a bipartite graph with $n$ edges and vertex bipartition ${A, B}$ and let $f$ be a $ρ$ -labeling of $G$ . Then $f$ is an $α$ -labeling if for all $a \in A$ and $b \in B$ we have $f (a) < f (b) \leq n$ .

The $ρ$ – and $α$ -labelings were defined by Rosa [2] as a means to determine if $K_{2 n + 1}$ or $K_{2 n k + 1}$ has a $G$ -design. The following definition is a variation of the $ρ$ -labeling for tripartite graphs.

Definition 3. [3] Let $G$ be a tripartite graph with $n$ edges and vertex tripartition ${A, B, C}$ and let $f$ be a $ρ$ -labeling of $G$ . Then $f$ is a $ρ$ -tripartite labeling of $G$ if

$f (a) < f (v)$ for any edge $a v \in E (G)$ where $a \in A$ ;
for every edge $b c \in E (G)$ , where $b \in B$ and $c \in C$ , there exists an edge $b^{'} c^{'} \in E (G)$ , where $b^{'} \in B$ and $c^{'} \in C$ , such that $| f (b) - f (c) | + | f (b^{'}) - f (c^{'}) | = 2 n$ ;
for all $b \in B$ and $c \in C$ , we have $| f (b) - f (c) | \neq 2 n$ .

Notice that this definition can be also used when $C$ is empty. In that case, we obtain a slightly less restrictive version of the $α$ -labeling. We do not require all vertices in $A$ to have lower labels than vertices in $B$ , but instead only $f (a) < f (b)$ whenever $a b$ is an edge.

We now present definitions of a 1-rotational $ρ$ -labeling and a 1-rotational $ρ$ -tripartite labeling as tools to find $G$ -designs of $K_{2 n}$ . By $G ⊖ w$ we denote the graph arising from $G$ by deletion of its vertex $w$ .

Definition 4. [4] Let $G$ be a graph on $n$ edges. A 1-rotational $ρ$ -labeling of $G$ is a one-to-one function $f : V (G) \to {0, 2 n - 2} \cup {\infty}$ such that

for some pendant vertex $w \in V (G)$ , we have $f (w) = \infty$ ;
$f$ restricted to $V (G ⊖ w)$ is a $ρ$ -labeling of $G ⊖ w$ .

Definition 5. [4] Let $G$ be a tripartite graph with $n$ edges and vertex tripartition ${A, B, C}$ . Then a 1-rotational $ρ$ -tripartite labeling of $G$ is a one-to-one function $h : V (G) \to {0, 1, 2, \dots, 2 n - 2} \cup {\infty}$ such that

$h$ is a 1-rotational $ρ$ -labeling of $G$ with $h (w) = \infty$ , where $w$ has a degree of one;
if the edge $a v \in E (G) ∖ {u w}$ , where $a \in A$ , then $h (a) < h (v)$ ;
if $b c \in E (G)$ , where $b \in B$ and $c \in C$ , then there exists an edge $b^{'} c^{'} \in E (G)$ , where $b^{'} \in B$ and $c^{'} \in C$ , such that $| h (b) - h (c) | + | h (b^{'}) - h (c^{'}) | = 2 n$ .

3. Relevant Theorems

Having defined our means of decomposing $K_{18 k}$ and $K_{18 k + 1}$ , we now provide theorems to support the legitimacy of our tools and definitions. The proofs for these can be found in the provided references.

Theorem 1. [2] Let $G$ be a graph with $n$ edges. There exists a cyclic $G$ -decomposition of $K_{2 n + 1}$ if $G$ admits a $ρ$ -labeling.

Theorem 2. [2] Let $G$ be a bipartite graph on $n$ edges that admits an $α$ -labeling. Then there exists a cyclic $G$ -decomposition of $K_{2 n k + 1}$ for all $k \geq 1$ .

Theorem 3. [3] Let $G$ be a tripartite graph on $n$ edges that admits a $ρ$ -tripartite labeling. Then there exists a cyclic $G$ -decomposition of $K_{2 n k + 1}$ for all $k \geq 1$ .

Theorem 4. [4] Let $G$ be a tripartite graph on $n$ edges and a vertex of degree one that admits a 1-rotational $ρ$ -tripartite labeling. Then there exists a 1-rotational $G$ -decomposition of $K_{2 n k}$ for all $k \geq 1$ .

When partite set $C$ (from Definition 5) is an empty set, then the following theorem is an easy corollary of the previous one.

Corollary 1. [4] Let $G$ be a bipartite graph on $n$ edges and a vertex $w$ of degree one such that $G ⊖ w$ admits an $α$ -labeling. Then there exists a 1-rotational $G$ -decomposition of $K_{2 n k}$ for all $k \geq 1$ .

Using our tools and the theorems that support them, we are now ready to label our class of graphs to find decompositions of $K_{18 k}$ and $K_{18 k + 1}$ .

4. Catalog of Graphs and Necessary Conditions

Here, we catalog all 33 non-isomorphic non-triangular connected bicyclic graphs with nine edges. Each graph is given a unique name $H_{i} (j, k; ℓ)$ , which defines the $i$ -th non-isomorphic graph containing cycles $C_{j}$ and $C_{k}$ connected by a path of length $ℓ$ . This notation was previously used by Froncek and Lee in [5].

The following necessary conditions for existence of the $G$ -designs are easy to observe.

Theorem 5. Let $G$ be a non-triangular connected bicyclic graph with nine edges. If there exists a $G$ -decomposition of $K_{n}$ , then $n \equiv 0, 1 (\mod 9)$ . Furthermore, if $G \in {H_{1} (6, 3; 0),$ $H_{1} (5, 4; 0)}$ , then $n \equiv 1, 9 (\mod 18)$ .

Proof. Because our graphs have nine edges, we must have $9 ∣ n (n - 1) / 2$ , which implies $n \equiv 0, 1 (\mod 9)$ . Furthermore, consider if $G \in {H_{1} (6, 3; 0),$ $H_{1} (5, 4; 0)}$ . When $n$ is even, then $K_{n}$ is odd-regular, and because all vertices in $G$ are even, no $G$ -decomposition of $K_{n}$ can exist with $n \equiv 0, 10 (\mod 18)$ .

5. Graph Labelings

A $ρ$ -tripartite labeling for each graph can be found in the Appendix. Also, 1-rotational $ρ$ -tripartite labelings for each such tripartite graph with a pendant edge (i.e., a degree-1 vertex) can be found along side those $ρ$ -tripartite labelings. For the bicyclic graphs that are bipartite, we provide $α$ -labelings and, for those with a pendant edge, 1-rotational $ρ$ -labelings where the removal of the degree-1 vertex $w$ results in an $α$ -labeling of the remaining graph $G ⊖ w$ .

Five of the graphs cataloged in Section4 do not have a pendant edge, two of which were shown in Theorem 5 not to decompose $K_{18 k}$ at all. Decompositions of $K_{18 k}$ into copies of the other three graphs without a pendant edge— i.e., $H_{1} (5, 3; 1)$ , $H_{1} (4, 4; 1)$ , and $H_{1} (4, 3; 2)$ —are treated in Section 6.

6. Graphs Without a Pendant Edge

For those graphs that do not have a degree-1 vertex, a 1-rotational $ρ$ -labeling is not possible. In this section, we find an alternative approach for settling decompositions of $K_{18 k}$ . Again, we note that this is only for graphs $H_{1} (5, 3; 1)$ , $H_{1} (4, 4; 1)$ , and $H_{1} (4, 3; 2)$ .

First, we define the following notation for any graphs $G$ and $H$ and positive integers $m$ and $n$ : Let $m \cdot G$ denote the graph composed of $m$ vertex-disjoint copies of $G$ ; whereas, if we write $m G$ , then the copies of $G$ need not be vertex-disjoint, just edge-disjoint. Let $G \cup H$ denote the edge-disjoint union of graphs $G$ and $H$ . If $H$ is a subgraph of $G$ , then we use $G ∖ H$ to denote the subgraph of $G$ with edge set $E (G) ∖ E (H)$ . If $G$ and $H$ are vertex-disjoint, then we use $G \lor H$ to denote the join of $G$ and $H$ , i.e., the graph with vertex set $V (G) \cup V (H)$ and edge set $E (G) \cup E (H) \cup {u v : u \in V (G), v \in V (H)}$ . We also use $K_{m \times n}$ to denote the complete multipartite graph with $m$ parts of size $n$ each. Now, consider the following.

Theorem 6. [6] If $v$ is an odd positive integer, then there exists a $P B D (v, {3, 5})$ .

Corollary 2. There exists a decomposition of $K_{v \times m}$ into copies of $K_{3 \times m}$ and $K_{5 \times m}$ for any positive integers $v, m$ with $v$ odd.

For brevity of notation, we now substitute the names $G_{1}$ , $G_{2}$ , and $G_{3}$ for graphs $H_{1} (5, 3; 1)$ , $H_{1} (4, 4; 1)$ , and $H_{1} (4, 3; 2)$ , respectively. When these graphs have vertex set ${a, b, c, d, e, f, g, h} \subset N$ , then we also use $G_{1} [a, b, c, d, e, f, g, h]$ , $G_{2} [a, b, c, d, e, f, g, h]$ , and $G_{3} [a, b, c, d, e, f, g, h]$ to denote the graphs with edge sets ${a g, a h, b e, b f, b g, c d, c e, d e, f h}$ , ${a g, a h, b f, b g, b h, c e, c f, d e, d f}$ , and ${a g, a h, b f, b g, b h, c d, c e, c f, d e}$ , respectively. For example, if we identify the vertex labels seen in the Appendix with their vertices, then the $ρ$ -tripartite labelings of $H_{1} (5, 3; 1)$ , $H_{1} (4, 4; 1)$ , and $H_{1} (4, 3; 2)$ shown therein correspond to $G_{1} [1, 3, 4, 11, 2, 0, 14, 5]$ , $G_{2} [0, 1, 2, 3, 4, 6, 7, 9]$ , and $G_{3} [12, 10, 8, 0, 17, 7, 6, 5]$ , respectively.

Example 1. Let $V (K_{9}) = Z_{9}$ and let $\begin{aligned} Δ_{1} = { & G_{1} [0, 1, 2, 3, 4, 5, 6, 7], G_{1} [1, 8, 6, 2, 5, 7, 0, 3], \\ G_{1} [4, 1, 6, 3, 8, 2, 7, 0], G_{1} [7, 4, 0, 3, 5, 8, 6, 2]}, \\ Δ_{3} = { & G_{3} [0, 1, 2, 3, 4, 5, 6, 7], G_{3} [3, 2, 8, 6, 4, 7, 0, 1], \\ G_{3} [6, 8, 5, 7, 4, 0, 2, 3], G_{3} [7, 5, 1, 0, 4, 8, 6, 3]} . \end{aligned}$ Then $Δ_{j}$ is a $G_{j}$ -decomposition of $K_{9}$ , for $j \in {1, 3}$ .

Example 2. Let $V (K_{18}) = Z_{18}$ and let $\begin{aligned} Δ_{2} = { & G_{2} [0, 4, 1, 2, 7, 5, 11, 15], G_{2} [1, 5, 2, 3, 4, 6, 8, 12], G_{2} [2, 6, 3, 0, 5, 7, 9, 13], \\ G_{2} [3, 7, 0, 1, 6, 4, 10, 14], G_{2} [4, 0, 11, 15, 5, 1, 9, 13], G_{2} [5, 1, 8, 12, 6, 2, 10, 14], \\ G_{2} [6, 2, 9, 13, 7, 3, 11, 15], G_{2} [7, 3, 10, 14, 4, 0, 8, 12], G_{2} [4, 0, 14, 16, 6, 2, 12, 17], \\ G_{2} [5, 1, 15, 16, 7, 3, 13, 17], G_{2} [6, 2, 12, 16, 4, 0, 14, 17], G_{2} [7, 3, 13, 16, 5, 1, 15, 17], \\ G_{2} [4, 0, 10, 17, 6, 2, 8, 16], G_{2} [5, 1, 11, 17, 7, 3, 9, 16], G_{2} [6, 2, 8, 17, 4, 0, 10, 16], \\ G_{2} [7, 3, 9, 17, 5, 1, 11, 16], G_{2} [15, 8, 13, 14, 11, 12, 9, 10], G_{2} [17, 9, 14, 15, 16, 13, 10, 11], \\ G_{2} [12, 10, 15, 17, 8, 14, 11, 16], G_{2} [13, 11, 17, 12, 9, 15, 16, 8], \\ G_{2} [14, 16, 12, 13, 10, 17, 8, 9]} . \end{aligned}$ Then $Δ_{2}$ is a $G_{2}$ -decomposition of $K_{18}$ .

Example 3. Let $V (K_{18} ∖ K_{9}) = Z_{18}$ where ${9, 10, \dots, 17}$ are the vertices in the hole. Let

$\begin{aligned} Δ_{1} = { & G_{1} [0, 1, 2, 3, 9, 4, 10, 11], G_{1} [0, 5, 2, 6, 11, 3, 9, 12], G_{1} [1, 7, 4, 5, 10, 6, 13, 14], \\ G_{1} [2, 3, 5, 12, 6, 14, 10, 7], G_{1} [2, 4, 8, 15, 6, 7, 14, 5], G_{1} [3, 1, 0, 7, 16, 5, 11, 17], \\ G_{1} [4, 0, 5, 8, 14, 2, 15, 13], G_{1} [5, 6, 3, 8, 13, 1, 16, 15], G_{1} [6, 8, 1, 2, 12, 7, 10, 9], \\ G_{1} [7, 4, 0, 6, 17, 8, 12, 11], G_{1} [8, 2, 3, 7, 15, 4, 17, 16], G_{1} [8, 4, 5, 13, 0, 3, 9, 1], \\ G_{1} [16, 0, 7, 17, 1, 8, 3, 2]}, \end{aligned}$ $\begin{aligned} Δ_{2} = { & G_{2} [0, 1, 2, 3, 4, 5, 6, 7], G_{2} [0, 4, 2, 3, 6, 9, 1, 5], G_{2} [0, 8, 3, 6, 10, 11, 12, 13], \\ G_{2} [1, 7, 0, 8, 15, 10, 13, 14], G_{2} [2, 4, 3, 6, 7, 8, 11, 0], G_{2} [2, 5, 1, 7, 12, 15, 14, 16], \\ G_{2} [3, 4, 2, 5, 13, 12, 17, 16], G_{2} [4, 2, 1, 5, 9, 17, 10, 15], G_{2} [4, 5, 0, 2, 3, 8, 6, 7], \\ G_{2} [5, 1, 0, 7, 17, 16, 10, 11], G_{2} [6, 3, 2, 8, 7, 1, 12, 15], G_{2} [7, 0, 6, 8, 16, 14, 9, 11], \\ G_{2} [8, 6, 3, 4, 14, 13, 9, 17]}, \end{aligned}$ $\begin{aligned} Δ_{3} = { & G_{3} [0, 1, 2, 3, 9, 10, 4, 11], G_{3} [0, 1, 11, 3, 5, 6, 9, 12], G_{3} [1, 2, 10, 5, 6, 7, 13, 14], \\ G_{3} [2, 4, 9, 6, 7, 8, 11, 15], G_{3} [4, 3, 13, 7, 8, 0, 10, 16], G_{3} [5, 6, 16, 0, 1, 2, 12, 13], \\ G_{3} [5, 6, 1, 3, 15, 8, 16, 17], G_{3} [6, 7, 17, 1, 2, 4, 14, 15], G_{3} [7, 8, 12, 2, 4, 3, 11, 16], \\ G_{3} [8, 0, 14, 3, 4, 5, 10, 17], G_{3} [8, 7, 5, 4, 9, 1, 0, 12], G_{3} [14, 15, 7, 3, 17, 5, 0, 8], \\ G_{3} [13, 6, 2, 5, 8, 0, 3, 4]} . \end{aligned}$

Then $Δ_{j}$ is a $G_{j}$ -decomposition of $K_{18} ∖ K_{9}$ , for $j \in {1, 2, 3}$ .

Example 4. Let $V (K_{9, 9}) = Z_{18}$ with bipartition ${{j \in Z_{18} : j \equiv k (\mod 2)} : k \in Z_{2}}$ . Let $\begin{aligned} Δ_{2} & = {G_{2} [2, 0, 16, 12, 11, 9, 7, 3] + j : j \in {0, 1, \dots, 8}} . \end{aligned}$ Then $Δ_{2}$ is a $G_{2}$ -decomposition of $K_{9, 9}$ .

Example 5. Let $V (K_{9, 9, 9}) = Z_{27}$ with tripartition ${{j \in Z_{27} : j \equiv k (\mod 3)} : k \in Z_{3}}$ . Let $\begin{aligned} Δ_{1} & = {G_{1} [0, 1, 4, 9, 2, 5, 11, 13] + j : j \in Z_{27}}, \\ Δ_{3} & = {G_{3} [0, 2, 5, 18, 16, 6, 7, 10] + j : j \in Z_{27}} . \end{aligned}$ Then $Δ_{j}$ is a $G_{j}$ -decomposition of $K_{9, 9, 9}$ , for $j \in {1, 3}$ .

Example 6. Let $V (K_{9, 9, 9, 9, 9}) = Z_{45}$ with vertex partition ${{j \in Z_{45} : j \equiv k (\mod 5)} : k \in Z_{5}}$ . Let $\begin{aligned} Δ_{1} & = ⋃_{j \in Z_{45}} {G_{1} [0, 1, 2, 3, 5, 7, 8, 16] + j, G_{1} [0, 1, 2, 13, 25, 14, 19, 28] + j}, \\ Δ_{3} & = ⋃_{j \in Z_{45}} {G_{3} [0, 1, 2, 3, 5, 8, 19, 22] + j, G_{3} [0, 1, 3, 7, 15, 12, 14, 17] + j} . \end{aligned}$ Then $Δ_{j}$ is a $G_{j}$ -decomposition of $K_{9, 9, 9, 9, 9}$ , for $j \in {1, 3}$ .

Finally, we turn our attention to how the above examples can be used to settle the missing case for our graphs without a pendant edge.

Theorem 7. If $G \in {H_{1} (5, 3; 1), H_{1} (4, 4; 1), H_{1} (4, 3; 2)}$ , then there exists a $G$ -decomposition of $K_{18 k}$ for any $k \geq 1$ .

Proof. If $k = 1$ and $G = G_{2} = H_{1} (4, 4; 1)$ , then the result follows from Example 2. If $k = 1$ and $G \in {G_{1}, G_{3}} = {H_{1} (5, 3; 1), H_{1} (4, 3; 2)}$ , then the result follows from Examples 1 and 3 and the fact that $K_{18} ≅ (K_{18} ∖ K_{9}) \cup K_{9}$ . We now assume that $k \geq 2$ . Note that $K_{n} ≅ ((2 k - 1) \cdot K_{9}) \lor K_{9} \cup K_{(2 k - 1) \times 9} ≅ K_{18} \cup (2 k - 2) (K_{18} ∖ K_{9}) \cup K_{(2 k - 1) \times 9}$ . Hence, we need only prove the existence of $G$ -decompositions of $K_{18} ∖ K_{9}$ and $K_{(2 k - 1) \times 9}$ . The former is shown in Example 3. If $G = G_{2}$ , then a $G$ -decomposition of $K_{(2 k - 1) \times 9}$ follows from the $G_{2}$ -decomposition of $K_{9, 9}$ . If $G \in {G_{1}, G_{3}}$ , then we note that there exists a ${K_{3 \times 9}, K_{5 \times 9}}$ -decomposition of $K_{(2 k - 1) \times 9}$ (by Corollary 2), and the result follows from Examples 5 and 6.

7. Main Results

From our constructions and labelings, we reach the following main results.

Theorem 9. Let $G$ be a connected bicyclic graph with exactly nine edges and at least one cycle that is not a 3-cycle. Then there exists a $G$ -decomposition of $K_{18 k + 1}$ for any $k \geq 1$ .

Proof. For $K_{18 k + 1}$ for any $k \geq 1$ , the proof follows from Theorems 2 and 3 and the $α$ -labelings and $ρ$ -tripartite labelings given in the Appendix.

Theorem 9. Let $G$ be a connected bicyclic graph with exactly nine edges and at least one cycle that is not a 3-cycle, except for $H_{1} (6, 3; 0)$ and $H_{1} (5, 4; 0)$ . Then there exists a $G$ -decomposition of $K_{18 k}$ for any $k \geq 1$ .

Proof. For graphs $G = H_{1} (5, 3; 1)$ , $H_{1} (4, 4; 1)$ and $H_{1} (4, 3; 2)$ , the result follows from Theorem 7. For the remaining graphs with a pendant edge, the proof follows from Theorem 4 and Corollary 1 along with the 1-rotational $ρ$ -tripartite labelings and 1-rotational $ρ$ -labelings given in the Appendix.

8. Conclusion

This paper provides a catalog of the 33 non-isomorphic connected bicyclic graphs on nine edges with at least one cycle that is not a 3-cycle and determines whether or not each decomposes $K_{18 k}$ and $K_{18 k + 1}$ . It was found that all graphs decompose $K_{18 k + 1}$ and all graphs except for $H_{1} (6, 3; 0)$ and $H_{1} (5, 4; 0)$ decompose $K_{18 k}$ . For further research in this direction, there are many classes of graphs on nine edges that have not yet been explored. Additionally, the tools used in this paper only apply to decompositions of $K_{18 k + 1}$ and $K_{18 k}$ for $k \geq 1$ , and they do not apply to $K_{18 k + 9}$ and $K_{18 k + 10}$ . It may be worth further exploring other graph classes as well as decompositions of these other complete graphs.

Conflict of Interest

The authors declare no conflict of interest.

References:

Freyberg, B., Froncek, D., Jeffries, J., Jensen, G. and Sailstad, A., submitted. $G$ -designs for the Triangular Bicyclic Graphs with Nine Edges.
Rosa, A., 1966. On certain valuations of the vertices of a graph. In Theory of Graphs Internat. Symposium, Rome (pp. 349-355).
Bunge, R. C., Chantasartrassmee, A., El-Zanati, S. I. and Vanden Eynden, C., 2013. On cyclic decompositions of complete graphs into tripartite graphs. Journal of Graph Theory, 72, pp.90-111.
Bunge, R. C., 2019. On 1-rotational decompositions of complete graphs into tripartite graphs. Opuscula Mathematica, 39(5), pp.624–643.
Froncek, D. and Lee, J., 2020. Decomposition of complete graphs in bi-cyclic graphs with eight edges. Bulletin of the Institute of Combinatorics and its Applications, 88, pp.30–49.
Abel, R. J. R., Bennett, F. E. and Greig, M., 2007. PBD-Closure. In C. J. Colbourn & J. H. Dinitz (Eds.), Handbook of Combinatorial Designs, pp.247-255. Chapman & Hall/CRC Press.

Appendix

The left column contains the $ρ$ -tripartite labelings for each graph, and the 1-rotational $ρ$ -tripartite labelings are provided in the right column, if they exist. The graph vertices are organized into three rows denoted by $A$ , $B$ , and $C$ ; each row denotes the partite set to which a vertex belongs. All lengths on edges between vertices in partite sets $B$ and $C$ show the positive difference of their labels (as mentioned in Definition 3, part 2, and in Definition 5, part 3)) in parentheses.

[1] Freyberg, B., Froncek, D., Jeffries, J., Jensen, G. and Sailstad, A., submitted. $G$ -designs for the Triangular Bicyclic Graphs with Nine Edges.

[2] Rosa, A., 1966. On certain valuations of the vertices of a graph. In Theory of Graphs Internat. Symposium, Rome (pp. 349-355).

[3] Bunge, R. C., Chantasartrassmee, A., El-Zanati, S. I. and Vanden Eynden, C., 2013. On cyclic decompositions of complete graphs into tripartite graphs. Journal of Graph Theory, 72, pp.90-111.

[4] Bunge, R. C., 2019. On 1-rotational decompositions of complete graphs into tripartite graphs. Opuscula Mathematica, 39(5), pp.624–643.

[5] Froncek, D. and Lee, J., 2020. Decomposition of complete graphs in bi-cyclic graphs with eight edges. Bulletin of the Institute of Combinatorics and its Applications, 88, pp.30–49.

[6] Abel, R. J. R., Bennett, F. E. and Greig, M., 2007. PBD-Closure. In C. J. Colbourn & J. H. Dinitz (Eds.), Handbook of Combinatorial Designs, pp.247-255. Chapman & Hall/CRC Press.

Contents

Utilitas Mathematica