Menu
We show that connected, bicyclic graphs on nine edges with at least one cycle other than \(C_3\) decompose the complete graphs \(K_{18k}\) and \(K_{18k+1}\), for \(k\geq1\), 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.
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_{18k}\) and \(K_{18k+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\equiv0,1\pmod{9}\) if there is a \(G\)-design of \(K_n\). This paper considers only \(G\)-designs of \(K_n\) in the cases when \(n\equiv0,1\pmod{18}\).
In this section, we introduce the definitions and tools needed to find the desired decompositions. We begin with the definition of a \(\rho\)-labeling:
Definition 1. [2] Given a simple graph \(G\) with vertex set \(V(G)\) and edge set \(E(G)\) where \(|E(G)|=n\), a \(\rho\)-labeling of \(G\) is a one-to-one function \(f\colon V(G)\to\{0,1,2,\ldots,2n\}\) such that the induced length function \(\ell\colon E(G)\to\{0,1,2,\ldots,n\}\) where \[\ell(uv)=\min\{|f(u)-f(v)|,2n+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 \(\rho\)-labeling of \(G\). Then \(f\) is an \(\alpha\)-labeling if for all \(a\in A\) and \(b\in B\) we have \(f(a)<f(b)\leq n\).
The \(\rho\)– and \(\alpha\)-labelings were defined by Rosa [2] as a means to determine if \(K_{2n+1}\) or \(K_{2nk+1}\) has a \(G\)-design. The following definition is a variation of the \(\rho\)-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 \(\rho\)-labeling of \(G\). Then \(f\) is a \(\rho\)-tripartite labeling of \(G\) if
\(f(a)<f(v)\) for any edge \(av\in E(G)\) where \(a\in A\);
for every edge \(bc\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 \(\lvert f(b)-f(c)\rvert+\vert f(b')-f(c')\rvert=2n\);
for all \(b\in B\) and \(c\in C\), we have \(|f(b)-f(c)|\neq 2n\).
Notice that this definition can be also used when \(C\) is empty. In that case, we obtain a slightly less restrictive version of the \(\alpha\)-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 \(ab\) is an edge.
We now present definitions of a 1-rotational \(\rho\)-labeling and a 1-rotational \(\rho\)-tripartite labeling as tools to find \(G\)-designs of \(K_{2n}\). By \(G\ominus 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 \(\rho\)-labeling of \(G\) is a one-to-one function \(f\colon V(G)\to\{0,2n-2\}\cup\{\infty\}\) such that
for some pendant vertex \(w\in V(G)\), we have \(f(w) = \infty\);
\(f\) restricted to \(V(G\ominus w)\) is a \(\rho\)-labeling of \(G\ominus w\).
Definition 5. [4] Let \(G\) be a tripartite graph with \(n\) edges and vertex tripartition \(\{A, B, C\}\). Then a 1-rotational \(\rho\)-tripartite labeling of \(G\) is a one-to-one function \(h\colon V(G)\to\{0,1,2,\ldots,2n-2\}\cup\{\infty\}\) such that
\(h\) is a 1-rotational \(\rho\)-labeling of \(G\) with \(h(w)=\infty\), where \(w\) has a degree of one;
if the edge \(av\in E(G)\setminus \{uw\}\), where \(a\in A\), then \(h(a)<h(v)\);
if \(bc\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')|=2n\).
Having defined our means of decomposing \(K_{18k}\) and \(K_{18k+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_{2n+1}\) if \(G\) admits a \(\rho\)-labeling.
Theorem 2. [2] Let \(G\) be a bipartite graph on \(n\) edges that admits an \(\alpha\)-labeling. Then there exists a cyclic \(G\)-decomposition of \(K_{2nk+1}\) for all \(k\geq1\).
Theorem 3. [3] Let \(G\) be a tripartite graph on \(n\) edges that admits a \(\rho\)-tripartite labeling. Then there exists a cyclic \(G\)-decomposition of \(K_{2nk+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 \(\rho\)-tripartite labeling. Then there exists a 1-rotational \(G\)-decomposition of \(K_{2nk}\) 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\ominus w\) admits an \(\alpha\)-labeling. Then there exists a 1-rotational \(G\)-decomposition of \(K_{2nk}\) 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_{18k}\) and \(K_{18k+1}\).
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;\ell)\), which defines the \(i\)-th non-isomorphic graph containing cycles \(C_j\) and \(C_k\) connected by a path of length \(\ell\). 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\equiv0,1\pmod{9}\). Furthermore, if \(G\in\bigl\{H_1(6,3;0),\) \(H_1(5,4;0)\bigr\}\), then \(n\equiv1,9\pmod{18}\).
Proof. Because our graphs have nine edges, we must have \(9\mid n(n-1)/2\), which implies \(n\equiv0,1\pmod9\). Furthermore, consider if \(G\in\bigl\{H_1(6,3;0),\) \(H_1(5,4;0)\bigr\}\). 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\equiv0,10\pmod{18}\). ◻
A \(\rho\)-tripartite labeling for each graph can be found in the Appendix. Also, 1-rotational \(\rho\)-tripartite labelings for each such tripartite graph with a pendant edge (i.e., a degree-1 vertex) can be found along side those \(\rho\)-tripartite labelings. For the bicyclic graphs that are bipartite, we provide \(\alpha\)-labelings and, for those with a pendant edge, 1-rotational \(\rho\)-labelings where the removal of the degree-1 vertex \(w\) results in an \(\alpha\)-labeling of the remaining graph \(G\ominus 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_{18k}\) at all. Decompositions of \(K_{18k}\) 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.
For those graphs that do not have a degree-1 vertex, a 1-rotational \(\rho\)-labeling is not possible. In this section, we find an alternative approach for settling decompositions of \(K_{18k}\). 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 \(mG\), 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\setminus H\) to denote the subgraph of \(G\) with edge set \(E(G)\setminus E(H)\). If \(G\) and \(H\) are vertex-disjoint, then we use \(G \vee 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 \bigl\{uv : u\in V(G), v\in V(H)\bigr\}\). 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 \(\mathrm{PBD}(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 \mathbb{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 \(\{ag,ah, be, bf, bg, cd, ce, de,fh\}\), \(\{ag,ah, bf, bg, bh, ce, cf, de,df\}\), and \(\{ag,ah, bf, bg, bh, cd, ce, cf,de\}\), respectively. For example, if we identify the vertex labels seen in the Appendix with their vertices, then the \(\rho\)-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}) = \mathbf{Z}_9\) and let \[\begin{aligned} \Delta_1 = \bigl\{& 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] \bigr\} , \\ \Delta_3 = \bigl\{& 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] \bigr\} . \end{aligned}\] Then \(\Delta_j\) is a \(G_j\)-decomposition of \(K_{9}\), for \(j\in\{1,3\}\).
Example 2. Let \(V(K_{18}) = \mathbf{Z}_{18}\) and let \[ \begin{align} \Delta_2 = \bigl\{& 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]%, \, \bigl\} . \end{align} \] Then \(\Delta_2\) is a \(G_2\)-decomposition of \(K_{18}\).
Example 3. Let \(V(K_{18} \setminus K_{9}) =
\mathbf{Z}_{18}\) where \(\{9,10,\ldots,17\}\) are the vertices in
the hole. Let
\[\begin{align*}
\Delta_1 = \bigl\{& 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] \bigl\} , \\[3pt] \end{align*}\]
\[ \begin{align*} \Delta_2 = \bigl\{& 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] \bigr\} , \end{align*}\]
\[ \begin{align*}
\Delta_3 = \bigl\{& 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] \bigr\} .
\end{align*}
\]
Then \(\Delta_j\) is a
\(G_j\)-decomposition of \(K_{18}\setminus K_{9}\), for \(j\in\{1,2,3\}\).
Example 4. Let \(V(K_{9,9}) = \mathbf{Z}_{18}\) with bipartition \(\bigl\{ \{j\in\mathbf{Z}_{18}:j\equiv k\pmod{2}\} : k\in\mathbf{Z}_2 \bigr\}\). Let \[\begin{aligned} \Delta_2 &= \bigl\{ G_2[2,0,16,12,11,9,7,3] +j : j\in\{0,1,\ldots,8\} \bigr\} . \end{aligned}\] Then \(\Delta_2\) is a \(G_2\)-decomposition of \(K_{9,9}\).
Example 5. Let \(V(K_{9,9,9}) = \mathbf{Z}_{27}\) with tripartition \(\bigl\{ \{j\in\mathbf{Z}_{27}:j\equiv k\pmod{3}\} : k\in\mathbf{Z}_3 \bigr\}\). Let \[\begin{aligned} \Delta_1 &= \bigl\{ G_1[0,1,4,9,2,5,11,13] +j : j\in\mathbf{Z}_{27} \bigr\} , \\ \Delta_3 &= \bigl\{ G_3[0,2,5,18,16,6,7,10] +j : j\in\mathbf{Z}_{27} \bigr\} . \end{aligned}\] Then \(\Delta_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}) = \mathbf{Z}_{45}\) with vertex partition \(\bigl\{ \{j\in\mathbf{Z}_{45}:j\equiv k\pmod{5}\} : k\in\mathbf{Z}_5 \bigr\}\). Let \[\begin{aligned} \Delta_1 &= \bigcup_{j\in\mathbf{Z}_{45}} \bigl\{ G_1[0,1,2,3,5,7,8,16] +j,\, G_1[0,1,2,13,25,14,19,28] +j \bigr\} , \\ \Delta_3 &= \bigcup_{j\in\mathbf{Z}_{45}} \bigl\{ G_3[0,1,2,3,5,8,19,22] +j,\, G_3[0,1,3,7,15,12,14,17] +j \bigr\} . \end{aligned}\] Then \(\Delta_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\bigl\{ H_1(5,3;1),\, H_1(4,4;1),\, H_1(4,3;2) \bigr\}\), then there exists a \(G\)-decomposition of \(K_{18k}\) for any \(k\geq1\).
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\}=\bigl\{H_1(5,3;1),H_1(4,3;2)\bigr\}\), then the result follows from Examples 1 and 3 and the fact that \(K_{18} \cong \bigl( K_{18} \setminus K_{9} \bigr) \cup K_{9}\). We now assume that \(k\geq2\). Note that \(K_n \cong \bigl( (2k-1)\cdot K_{9} \bigr) \vee K_{9} \cup K_{(2k-1)\times9} \cong K_{18} \cup (2k-2)(K_{18}\setminus K_{9}) \cup K_{(2k-1)\times9}\). Hence, we need only prove the existence of \(G\)-decompositions of \(K_{18}\setminus K_{9}\) and \(K_{(2k-1)\times9}\). The former is shown in Example 3. If \(G=G_2\), then a \(G\)-decomposition of \(K_{(2k-1)\times9}\) 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\times9},K_{5\times9}\}\)-decomposition of \(K_{(2k-1)\times9}\) (by Corollary 2), and the result follows from Examples 5 and 6. ◻
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_{18k+1}\) for any \(k\geq 1\).
Proof. For \(K_{18k+1}\) for any \(k\geq 1\), the proof follows from Theorems 2 and 3 and the \(\alpha\)-labelings and \(\rho\)-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_{18k}\) 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 \(\rho\)-tripartite labelings and 1-rotational \(\rho\)-labelings given in the Appendix. ◻
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_{18k}\) and \(K_{18k+1}\). It was found that all graphs decompose \(K_{18k+1}\) and all graphs except for \(H_1(6,3;0)\) and \(H_1(5,4;0)\) decompose \(K_{18k}\). 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_{18k+1}\) and \(K_{18k}\) for \(k\geq 1\), and they do not apply to \(K_{18k+9}\) and \(K_{18k+10}\). It may be worth further exploring other graph classes as well as decompositions of these other complete graphs.
The authors declare no conflict of interest.
The left column contains the \(\rho\)-tripartite labelings for each graph, and the 1-rotational \(\rho\)-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.
