Menu
A graph \(G\) with vertex set \(V = V(G)\) and edge set \(E = E(G)\) is harmonious if there exists a harmonious labeling of \(G\); which is an injective function \(f:V(G) \rightarrow \mathbf{Z}_m\) provided that whenever \(e_1, e_2 \in E\) are distinct with endpoints \(u_1,v_1\) and \(u_2,v_2\), respectively, then \(f(u_1) + f(v_1) \not\equiv f(u_2) + f(v_2) (\hbox{mod } m )\). Using basic group theory, we prove in a different manner an already established result that a disjoint union of an odd cycle and a path is harmonious provided their lengths satisfy certain conditions. We apply the same basic idea to establish that, under the same conditions, a disjoint union of an odd cycle with a certain starlike tree is harmonious (where a starlike tree consists of a central vertex that is adjacent to an endpoint of a certain number of fixed length paths). Finally, we extend the latter result to include specifying that the central vertex in the tree be adjacent to different vertices in each of the \(t\)-many \(s\)-paths.
Our notation is fairly standard, following [1]. Let \(G = (V,E)\) be a simple graph with \(|V| = n\) and \(|E| = m\). An injection \(f:V \rightarrow \mathbf{Z}_m\) is said to be a harmonious labeling of \(G\) provided that whenever \(e_1 \neq e_2 \in E\) with respective endpoints \(u_1,v_1\) and \(u_2,v_2\), then \(f(u_1) + f(v_1) \not\equiv f(u_2) + f(v_2) (\hbox{mod } m )\). If there exists a harmonious labeling of \(G\), then the graph \(G\) is said to be harmonious. The elements of the range of \(f\) are the vertex labels. For an edge \(e\) with endpoints \(u\) and \(v\), then \(f(u) + f(v) (\hbox{mod } m )\) is the edge label of \(e\).
In the case of trees, as there would not be enough labels of the vertices for there to be such an injection, it is permitted for there to be precisely two vertices having the same label; however, the edge labels must still be all distinct.
Much is known about harmonious labelings of particular graphs; for a comprehensive chronicling of known results, please refer to Gallian’s work [2]. Although it is not known whether all trees are harmonious, many classes of trees are known to be harmonious. For example, all trees with at most 31 vertices are known to be harmonious (see [3]). It is not difficult to show that all path graphs and stars are harmonious. Caterpillars are known to be harmonious (see [4]). As for cycle graphs, odd cycles are known to be harmonious; even cycles are known to not be harmonious (see [4]).
An injection \(f: V \rightarrow \{0, \dots, 2m\}\) is said to be even harmonious labeling of \(G\) if the induced function \(f^{\ast}: E(G) \rightarrow \{0,2, \dots, 2m \}\) defined by \(f^{\ast} (uv) = f(u) + f(v)\) (mod \(2m\)) is bijective. Gallian and Schoenhard, [5], define an injective function \(f : V \rightarrow \{0,1, \dots, 2m-1\}\) as properly even harmonious labeling of \(G\) if the induced function \(f^{\ast} : E(G) \rightarrow \{0,2,\dots, 2m-2\}\) defined by \(f^{\ast} (uv) = f(u) + f(v)\) (mod \(2m\)) is bijective. An injective function \(f:V \rightarrow \mathbf{Z}_m\) is said to be \(a\)-sequential labeling if for each edge \(uv\), the edge label induced by \(f(u) + f(v)\) is in \(a, \dots, a+ m-1\) and all the edge labels are distinct. If the graph \(G\) is a tree then the domain of \(f\) is \(\{0, 1, \dots, m\}\). An injective function \(f : V \rightarrow \{0,1, \dots, 2m-1\}\) is said to be even 2a-sequential if for each edge \(uv\), the edge label induced by \(f(u) + f(v)\) is in \(2a, 2a+2, \dots, 2a+ 2m-2\) and all the edge labels are distinct. If the graph \(G\) is a tree then the domain of \(f\) is \(\{0, 1, \dots, 2m\}\).
In this paper, we first show that if the cycle is odd and the number of vertices in the path is one more than an even multiple of the number of vertices in the cycle is indeed harmonious; we achieve this using a subgroup and its cosets. We are re-proving a known result using a different method involving cosets of a subgroup. Then, we apply the coset method used in that proof to the another family of graphs for which it is unknown whether they are harmonious. A starlike tree consists of a central vertex called a root and several path graphs attached to it (at a leaf of the path). More formally, a tree is starlike if it has exactly one vertex of degree greater than or equal to 2. We show that the disjoint union of an odd cycle on \(s\) vertices with a starlike tree of \(t\)-many \(s\)-paths (where \(t\) is even) is harmonious. We also show how a simple re-labeling of the root can lead to a harmonious labeling of a disjoint union of an odd cycle with the root attached to \(t\)-many \(s\)-paths at selected vertices in the paths.
It has been determined that the \(C_s \cup P_3\) is harmonious when \(s\) is odd (see [6]). Gallian and Stewart (see [7]) proved the following:
Theorem 1. [7] \(G \cup P_n\) is properly even harmonious if \(G\) is an even \(2a\)-sequential graph when \(n> 1\) and \(n \equiv 1, 2\) (Mod 4).
There is an extension of Theorem 1 at [8] that states the following:
Theorem 2. \(G \cup P_n\) is properly even harmonious if \(G\) is an even \(2a\)-sequential graph with \(q\) edges, \(n > 1\), \(n \equiv 1, 2\) (mod 4) or \(n > 1\) and \(q + n\) is even.
As odd cycles are even \(2a\)-sequential graphs, the graph \(C_s \cup P_{st+1}\) is harmonious when \(st+1 \equiv 1,2\) (mod 4).
Although already implied by Theorem 2 above, we provide the following theorem and its proof (which is different than the one provided by Gallian and Stewart) for completeness as well as the reuse of part of the proof in the following theorems.
Let \(G = C_s \cup P_{st+1}\), where \(s \geq 3\) is odd and \(t\) is even. Since \(|E(G)| = s(t+1)\), we label the vertices of \(G\) with the elements of the additive cyclic group \(\mathbf{Z}_{s(t+1)}\), with one repeated vertex label permitted (allowing for the path). For detailed information on Group Theory, see [9]. Our main goal is to prove the following theorem.
Theorem 3. Let \(s \geq 3\) be odd and let \(t\) be even. Then \(G = C_s \cup P_{st+1}\) is harmonious.
Our proof will consist of a number of cases, which compare different edge labels based on the labeling function. We shall label the vertices of \(C_s\) with the elements of the subgroup \(H\) of \(\mathbf{Z}_{s(t+1)}\) of order \(s\), i.e., \(H = \{0, t + 1, 2(t+1), \ldots (s-1)(t+1)\}\). We do this by starting from a vertex in the cycle and consecutively label the vertices starting with the smallest element of the subgroup and finishing with the greatest such element. We now show the induced edge labels are distinct.
Case 1. With the labeling of the vertices of the \(s\)-cycle described above, the resulting edge labels are distinct.
Proof. Observe that each edge label has the form \(i(t+1) + (i+1)(t+1)(\hbox{mod } s(t+1)) \equiv (2i+1)(1+t)(\hbox{mod }s(t+1))\), where \(i \in \{0,1,\ldots , s-1\}\). So, consider the scenario, for \(i \neq j\), that \((2i+1)(t+1) \equiv (2j+1)(t+1)(\hbox{mod } s(t+1))\). This implies that \(2(i-j)(t+1) = \gamma s(t+1)\) for some integer \(\gamma\). Since \(s, t+1\) are both odd, then \(\gamma\) is even. Thus, \(i-j = \delta s\), where \(\delta = \gamma/2 \in \mathbf{Z}\), which is contrary to \(i,j \in \{0,1,\ldots, s – 1\}\). ◻
For the path, the idea is to eventually construct a path on \(st+1\) vertices from smaller paths each of which has \(s\) vertices and each of whose vertices are labeled using elements of a coset of \(H\). Here is the first piece of the labeling function: A coset \(H + i\) of \(H\) will correspond to a path of \(s\)-many vertices; working from one end of the path consecutively to the other, we label the vertices in order using the elements of the coset. In particular, consider the cosets \(H+1, \ H+2, \ldots , H + t\) of \(H\); these correspond to paths each with \(s\) vertices. For future reference, we shall denote the corresponding paths by \(P_s^1, P_s^2, \ldots , P_s^t\). Based upon this correspondence, sometimes we will refer to the edges within a particular \(s\)-path as “internal coset” edges and edges that connect different \(s\)-paths as “coset-to-coset” edges
We shall now compare an edge label of the \(s\)-cycle to an edge label within an \(s\)-path.
Case 2. For an edge with both ends in the cycle and an edge with its ends in \(P_s^i\) (\(i \in \{1,2,\ldots , t\}\)), the two edges have different labels.
Proof. Consider an edge whose endpoints are in the \(P_s^i\), \(i \in \{1,2,\ldots , t\}\). Now observe that \(H+i = \{i, i + (t+1), i + 2(t+1), \ldots , i + (s-1)(t+1)\}\); these elements are the vertex labels of \(P_s^i\). Then the edge label would be \(i + \alpha(t+1) + i + \alpha(t+1) + (t+1) \equiv 2i + (2\alpha + 1)(t+1)(\hbox{mod }s(t+1))\), for some \(\alpha \in \{0,1,\ldots,s-2\}\). Thus, since \(1 \leq i \leq t\), then \(2 \leq 2i \leq 2t < 2(t+1)\) and since \(t\) is even (hence \(t+1\) is odd), then \(2i\) term in the expression above cannot equal \(t+1\). Consequently, the edge-label cannot be an element of the subgroup \(H\) generated by \(t+1\). And since, by closure of \(H\), all the edge labels of \(C_s\) are elements of \(H\), then the edge label under consideration is distinct from the edge labels of \(C_s\). ◻
Next, we compare edge labels of a pair of edges within a single one of these \(s\)-paths; i.e., we compare internal coset edges.
Case 3. For every \(i = 1, 2, 3, \ldots ,t\), any pair of edges whose endpoints are labeled with elements of \(H + i\) have distinct labels.
Proof. From the previous case, a pair of internal coset edges have labels \(2i + (2\alpha +1)(t+1)(\hbox{mod }s(t+1))\) and \(2i + (2\beta +1)(t+1)(\hbox{mod }s(t+1))\) for some \(\alpha, \beta \in \{0,1,\ldots , s-2\}\), and \(\alpha \neq \beta\). Without loss of generality, assume \(\alpha < \beta\).
By contradiction, assume \(2i + 2\alpha(t+1) + (t+1) \equiv 2i + 2\beta(t + 1) + (t+1)(\hbox{mod }(s(1+t)))\). Consequently, we have \([2i+2\beta(t+1) + (t+1)]-[2i+2\alpha( t+ 1) + (t + 1) ] = \gamma s (1+t)\), for some \(\gamma \in \mathbf{Z}^+\). Hence, \(2(\beta + 1) – 2(\alpha + 1)(t+1) = \gamma s (1+t)\), or \(2(\beta – \alpha)(1+t) = \gamma s(1+t)\). Therefore, \(2(\beta – \alpha) = \gamma s\). Since \(s\) is odd, then \(\gamma\) is even. Thus, dividing by 2 gives \((\beta – \alpha) = \lambda s\), where \(\lambda = \gamma/2 \in \mathbf{Z}^+\). So, \(\beta – \alpha \geq s\). And since \(\alpha, \beta \in \{0,1,2, \ldots , s – 2\}\), then \(\beta – \alpha \leq s -2\), a contradiction. ◻
We next compare edge labels from different \(s\)-paths.
Case 4. For an edge in \(P_s^i\) and an edge in \(P_s^j\), where \(i \neq j\), their edge labels are not equivalent.
Proof. In this case, the edge labels would be of the form \(2i + (2\alpha + 1)(t+1)\) and \(2j+(2\beta+1)(t+1)\), where \(\alpha, \beta \in \{0,1,\ldots , s-2\}\) and both edge labels are taken \(\hbox{mod } s(t+1)\). We may assume, without loss of generality, that \(i < j\). To the contrary, we assume these labels are equivalent. Thus, we have \(2(j-i) + 2(\beta – \alpha )(t+1) = \gamma s (t+1), \hbox{for some } \gamma \in \mathbf{Z}^+\). Since \(s, t+1\) are odd, then \(\gamma\) is even; hence, \((j-i) + (\beta – \alpha)(t+1) = \delta s(t+1)\), where \(\delta = \gamma/2 \in \mathbf{Z}^+\). It follows that \(j-i\) is a multiple of \(t+1\). But this would imply that since \(i, j \in \{1,2,3,\ldots ,t\}\), then \(j -i = 0\), a contradiction. ◻
Next, we start joining the paths by edges in the following manner: For \(i = 1,2,\ldots t-2\), create an edge between the vertex with the label \(i\) in the path \(P_s^i\) and the vertex in the path \(P_s^{i+2}\) with the label \((i+2) + (s-1)(t+1)\). Moreover, we create a new vertex \(v_0\) with label 0 (note that 0 was already used once in the cycle labeling and is the only re-used label) and create an edge between vertex \(v_0\) and the vertex in \(P_s^{t-1}\) with the label \(t-1\). Note that this induces the edge label \(t-1\). Next, create an edge between \(v_0\) and the vertex in \(P_s^2\) with label \(2 + (s-1)(t+1)\). Note that this induces the edge label of \(2 + (s-1)(t+1)\). Observe that even apart from this labeling, that joining the edges in this manner will produce a path with \(st + 1\) vertices, as required. We still must prove the following regarding this labeling: (1) The labels of edges joining vertices from the cycle have labels are different from the labels of the coset-to-coset edges, (2) the labels of a pair of distinct coset-to-coset edges are different, (3) the label of a coset-to-coset edge is different than the label of an internal coset edge, (4) the edge label of an edge joining the vertex \(v_0\) with label 0 to either of one of its neighbors is different from (a) the label of an internal coset edge , and (b) the label of a coset-to-coset edge.
We begin with (1) above.
Case 5. The label of a coset-to-coset edge cannot be an element of \(H\) (and thus cannot have the label of an edge label of the cycle).
Proof. Observe, by the construction above, that a coset-to-coset edge has the label \(i + (i + 2) + (s-1)(t+1) \equiv 2i+2 +(s-1)(t+1) (\hbox{mod }s(t+1))\), where \(i \in \{1,2,\ldots , t-2\}\). Thus, \(2i+2 \in \{4,\ldots 2t-2 = 2(t-1) \}\), all of which are taken \(\hbox{mod }s(t+1)\); thus, as \(2i +2 < 2(t+1)\) the resulting label could only be an element of the subgroup \(H\) provided that \(2i+2 = t+1\) . This is impossible since \(t+1\) is odd and \(2i+2\) is even. ◻
Now to (2).
Case 6. A pair of distinct coset-to-coset edges have different labels.
Proof. We note the form of the coset-to-coset edge label above. In particular, consider edges with labels \(2i+2 +(s-1)(t+1) (\hbox{mod }s(t+1))\) and as well as \(2j+2 +(s-1)(t+1) (\hbox{mod }s(t+1))\), where \(i,j \in \{1,2, \ldots, t-2\}\). Without loss of generality, assume \(i<j\). By contradiction, assuming their edge labels are equivalent modulo \(s(t+1)\), it follows that \(2(j-i) = \gamma s(t+1)\) for some \(\gamma \in \mathbf{Z}^+\). This contradicts the fact that \(i,j \leq t\). ◻
We now compare the label of a coset-to-coset edge to the label of an internal coset edge.
Case 7. The label of a coset-to-coset edge is not equivalent to the label of an internal coset edge.
Proof. Suppose, on the contrary, that \(2i +2 + (s-1)(t+1) \equiv 2j + (2\alpha+1)(t+1) (\hbox{mod } s(t+1))\), where \(i,j \in \{1,2,\ldots , t\}\) and \(\alpha, \beta \in \{0,1,\ldots , s-2\}\). Thus, \(2(i – j + 1)+ [(s-1)-(2\alpha +1)](t+1) =\gamma s(t+1)\), for some integer \(\gamma\). Therefore, \(2(i-j + 1) = (t+1)[2\alpha + \gamma s -s +2 ]\). Now, \(t+1, \gamma s, 2\alpha > 0\); since \(\gamma \geq 1\), then \(2\alpha + \gamma s – s – 2 > 0\). Since \(t+1\) is odd, then \(2 \alpha + \gamma s – s – 2\) is even and positive, from which it follows that \(i – j + 1\) is positive and a positive multiple of \(t+1\). As \(s,t+1\) are odd, then \(\gamma\) is even, which implies that \(j – i = \delta s (t+1)\), where \(\delta = \gamma/2 \in \mathbf{Z}^+\). This contradicts the fact that \(i,j \in \{1,2,\ldots,t\}\). ◻
Finally, we compare the label of the edges incident to \(v_0\) to the labels of the cycle edges, the internal coset edges, and the coset-to-coset edges. First, as mentioned earlier, the labels of the edges incident to \(v_0\) are \(t-1\) and \(2 + (s-1)(t+1)\). It is clear that neither of these are edge labels in the cycle, as the cycle only admits labels from the subgroup \(H\). We show that neither of these are the labels of internal coset edges.
Case 8. The labels of the edges incident to \(v_0\) are not equal to the edges incident to the labels of the internal coset edges.
Proof. As earlier, the labels of the internal coset edges have the form \(2i+(2\alpha + 1)(t+1)(\hbox{mod }s(t+1))\), for some \(i\in\{1,2,\ldots,t-2\}\) and \(\alpha \in \{0,1,\ldots , s-1\}\). By contradiction, if we assume that \(2i + (2\alpha +1)(t+1) \equiv t-1(\hbox{mod } s(t+1))\), then we have that \((2i – t + 1) + (2\alpha + 1)(t+1) = \gamma s(t+1)\) for some integer \(\gamma\). Thus, \(2i-t+1\) is a multiple of \(t+1\). As \(i \leq t\), we have \(2i-t+1 \leq t+1\). Thus, either \(2i-t+1=0\) – which is contrary to \(t\) being even – or we have \(2i + t + 1 = t + 1\) . This latter case implies \(2i = 0\), a contradiction.
Now, we show this internal coset edge label is different from the label of the other edge incident to \(v_0\). So suppose, on the contrary, that \(2 + (s-1)(t+1) \equiv 2i + (2\alpha + 1)(t+1)(\hbox{mod }s(t+1))\), where \(i \in \{1,2,\ldots ,t \}\) and \(\alpha \in \{0,1,\ldots, s-2\}\). Hence, \(2i-2 +(2\alpha + 1-s+1)(t+1) = \gamma s(t+1)\) for some \(\gamma \in \mathbf{Z}^+\); and so \(2i-2\) must be a multiple of \(t+1\). Since \(i\leq t\), then \(2i-2 \leq 2t-2 < 2(t+1)\); hence \(2i-2 = t+1\) or \(2i-2 = 0\). The former case is a contradiction, as \(t\) is even. The latter case implies that \(i = 1\); so we are working in the coset \(H+1\). In this coset, the edge labels are of the form \(2 + (2\alpha + 1)(t+1) (\hbox{mod } s(t+1)\), where \(\alpha \in \{0,1,\ldots ,s-2\}\). This range of values for \(\alpha\) loops through the odd multiples of \((t+1)\) through its first half of values; thus the edge label will not equal \(2 + (s-1)(t+1)\) (an even multiple of \(t+1\)) in this round. In the second and final round of the loop values of \(\alpha\), it will reach up to \(s-2\), and so, at this maximum, the multiple of \(t+1\) is \(2(s-1) -2\), and thus the edge label in this round reaches its maximum just short (and not equal to \(2+(s-1)(t+1))\). ◻
Finally, we compare the labels of edges incident to \(v_0\) to those of the coset-to-coset edge labels.
Case 9. The labels of the edges incident with \(v_0\) are different from the labels of the edges of the form \(2i + 2 + (s-1)(t+1)\), where \(i \in \{1,2,\ldots, t-2\}\).
Proof. First, we consider the edge with label \(t-1\) incident to \(v_0\). By contradiction, assume that \(t-1 \equiv 2i+2 +(s-1)(t+1)(\hbox{mod }s(t+1))\). Thus, \(2i +3 -t +(s-1)(t+1) = \gamma s(t+1)\) for some integer \(\gamma\); this implies that \(2i+3-t\) is a multiple of \(t+1\). Now, as \(i\leq t-2\), we have \(2i+3-t \leq t-1 < t+1\). Thus, \(2i+3-t=0\); hence \(t\) is odd, a contradiction.
Next, we consider the edge with label \(2+(s-1)(t+1)\) incident to \(v_0\). To the contrary, we assume that \(2 + (s-1)(t+1) \equiv 2i +2 +(s-1)(t+1) (\hbox{mod } s(t+1))\). Therefore, \(2i = \gamma s(t+1)\) for some integer \(\gamma\). Since \(i \leq t-2\), we have \(2i \leq 2t-4 < 2(t+1)\). It follows that either \(2i = t+1\) or \(2i=0\). The former contradicts the fact that \(t\) is even. Thus, \(2i = 0\). This is impossible as \(1\leq i \leq t-2\) precludes this. ◻
The following is an example the harmonious labeling of \(C_5 \cup P_{11}\) using the theorem above.
Now, we apply this subgroup and coset method to other disjoint unions of odd cycles and trees. Again, let \(t\geq 2\) be even and \(s\geq 3\) be odd. Then let \(T = T_{st+1}\) be a starlike tree consisting of \(t\)-many \(s\)-paths; i.e., \(T\) consists of a central vertex (root) adjacent to a leaf of each of \(t\) paths with \(s\) vertices. Let \(G = C_s \cup T\). As before, we label the vertices of \(G\) with the elements of the additive group \(\mathbf{Z}_{s(t+1)}\), with one repeated vertex label permitted.
In light of the previous theorem, with a little adjustment, we have the following theorem.
Theorem 4. Let \(s \geq 3\) be odd and let \(t\geq 2\) be even. Then \(G = C_s \cup T_{st+1}\) is harmonious.
Again, we proceed by cases, comparing the labels of classes of edges. As before, we label the vertices of \(C_s\) with all the elements of the cyclic subgroup \(H \leq \mathbf{Z}_{s(t+1)}\) of order \(s\) generated by \(t+1\). That is, we have \(H = \langle t+1 \rangle = \{0, t + 1, 2(t+1), \ldots (s-1)(t+1)\}\). In light of case 1 of the proof of the previous theorem, we omit the proof of the following:
Case 1. The edge labels of \(C_s\) are distinct.
In a manner similar to using cosets to label smaller paths in the proof of Theorem 1, we construct a starlike tree on \(st+1\) vertices (along with its labeling function) by labeling the \(s\)-paths (not including the root). Start with \(t\)-many copies of \(P_s\), namely, \(P_s^1, P_s^2, \ldots , P_s^t\). The vertices of \(P_s^i\) are labeled using elements of the coset \(H + i\) of \(H\), where \(1\leq i \leq t\). For each such path, working from one end of the path consecutively to the other, we label the vertices in order with the elements of its corresponding coset (in order of the elements of the coset). .
Again, since we have proved this earlier, we have that the labels on the vertices in \(s\)-cycle is different than the label of an internal coset edge.
Case 2. For an edge with both endpoints in the \(s\)-cycle and an edge with its endpoints in \(P_s^i\) (\(i \in \{1,2,\ldots , t\}\)), the two edges have different labels.
Now, we again note that edge labels of a pair of edges within a single \(s\)-path are distinct. As with other cases so far, we do not repeat the proof.
Case 3. For all \(i = 1, 2, 3, \ldots ,t\), any pair of edges in \(P_s^i\) whose endpoints are labeled with elements of \(H + i\) have distinct labels.
As in theorem 1, the edge labels from different \(s\)-paths are distinct.
Case 4. For an edge in \(P_s^i\) and an edge in \(P_s^j\), where \(i \neq j\), their edge labels are distinct.
Now, we label the root of the tree, call it \(v_0\), with vertex label \(0\) (note that \(0\) was already used once in the cycle labeling and is the only re-used label). For odd \(i\) (for even \(i\)), for i between 1 and \(t\), create an edge between \(v_0\) and the vertex labeled \(i\) (vertex labeled \(i + (s-1)(t+1)\)). Obviously, the resulting edge labels would then be \(i\) (for odd \(i\)) and \(i + (s-1)(t+1)\) (for even \(i\)).
It is obvious that the edges incident to \(v_0\) have distinct labels. It is also clear that the edges incident to \(v_0\) are different than these edge labels in the cycle, as the cycle only admits labels from the subgroup \(H\). It remains to show that the edges incident to \(v_0\) have different labels than the internal edges of the paths.
Case 5. The labels of the edges incident to \(v_0\) are not equal to the labels of the internal coset edges.
Proof. As earlier, the labels of the internal coset edges have the form \(2i+(2\alpha + 1)(t+1)(\hbox{mod }s(t+1))\), for some \(i\in\{1,2,\ldots,t\}\) and \(\alpha \in \{0,1,\ldots , s-2\}\). Since we the way we“hook” the root to each path depends on the parity of the path label, call it \(k\), we look at the proof of this case in terms of the parity of \(k\):
Case 5A: Let \(k\) be odd. For sake of contradiction assume that \(2i+(2\alpha + 1)(t+1) \equiv k (\hbox{mod }s(t+1))\), where \(1 \leq k \leq t-1\), \(1 \leq i \leq t\), and \(0 \leq \alpha \leq s-2\). Therefore, \(2i-k+(2 \alpha +1)(t+1) = \gamma s (t+1)\) for some positive integer \(\gamma\).
Since \(k\), \(2\alpha +1\), \(t+1\), and \(s\) are odd, \(\gamma\) is even. Hence \(\gamma \geq 2\).
We note that \(2i-k \leq 2t-1 < 2(t+1)\). Hence, \(2i-k = (t+1)[ \gamma s – (2 \alpha +1)] < 2(t+1)\). So, either \(2i-k = 0(t+1)\), or \(2i-k = 2(t+1)\). Since \(k\) and \(2i\) have different parity, \(2i-k \neq 0\). If \(2i-k = 1(t+1)\), then \(\gamma s – (2 \alpha +1)=1\). Since \(\gamma \geq 2\), \(\gamma s \geq 2s\). Note that \(2 \alpha +1 \leq 2 (s-2)+1=2s-3\). Hence, \(\gamma s – (2 \alpha +1) \geq 2s -(2s-3) =3\) which contradicts our assumption that \(\gamma s – (2 \alpha +1)=1\).
Case 5B: Let \(k\) be even. In this case the root will be “hooked” to the vertex labeled \(k + (s-1)(t+1)\). For sake of contradiction assume that \(2i+(2\alpha + 1)(t+1)\equiv k + (s-1)(t+1) (\hbox{mod }s(t+1))\), where \(1 \leq i \leq t\), \(2 \leq k \leq t\), and \(0 \leq \alpha \leq s-2\).
Hence, \(2i-k + (t+1)[2 \alpha +1 – (s-1)] = \gamma s (t+1)\) for some integer \(\gamma\). Observe \(-(t+1)<2t-2<2i-k<2(t+1)\). Hence, \(2i-k =(t+1)[\gamma s -(2 \alpha +2 – s)]\) equals \(0(t+1)\) or \(1(t+1)\). Now, if \(2i-k=0\), then \(\gamma s -(2\alpha + 2-s) = 0\). Hence \(s(\gamma + 1) = 2\alpha + 2 \leq 2(s-2) + 2 = 2s-2\). Since \(s(\gamma + 1) \leq 2s-2\) and both sides are positive, we have \(\gamma = 0\). Thus, the equation \(\gamma s – (2\alpha + 2 – s) = 0\) implies that \(s\) is even, a contradiction.
On the other hand, consider the case where \(2i-k =(t+1)[\gamma s -(2 \alpha +2 – s)]= t+1\). This is impossible since the left side is even, and the right side is odd. ◻
The following is an example of a harmonious labeling of \(C_5 \cup T_{21}\) using the theorem above.
Finally, we consider another disjoint union of an odd cycle and a tree and its harmonious labeling that results from a simple re-labeling of only the root in the labeling of the odd cycle with the starlike tree described in the proof of the previous theorem.
Again, consider the labeling of the graph \(C_s \cup T_{st+1}\) with odd \(s\geq 3\) and even \(t\geq 2\) described in the proof of Theorem 2. Now, we change the label of the root \(v_0\) to \(\alpha(t+1)\), for some \(1\leq \alpha \leq s-1\). Since \(\alpha(t+1) \in H\), we can “unhook” \(v_0\) from the ends of the paths described above, and “re-hook” \(v_0\) to a new vertex of \(P_s^i\) for each \(1 \leq i \leq t\), again depending on the parity of \(i\). If \(i\) is odd, then we add an edge between \(v_0\) and the vertex in \(P_s^i\) with label \(i + (s-\alpha)(t+1)\), creating the edge label of \(i + s(t+1)\). If \(i\) is even, then we add an edge between \(v_0\) and the vertex in \(P_s^i\) with label \(i + (s-1 -\alpha)(t+1)\); thus, we have \(i +(s-1)(t+1)\) as the corresponding new edge label. From the discussion before case 5 of the proof of Theorem 4, it is clear that this will yield the same edge labels between \(v_0\) and the new vertices to which they are adjacent as before. We note that no labels of the other edges have changed. These graphs are obviously different than the (admittedly, more symmetric) union of starlike graphs with paths. In particular, let \(R_{st+1}\) be the resulting tree. In particular, \(R_{st+1}\) will have vertex \(v_0\) that is adjacent to \(t/2\)-many \(s\)-paths at the vertex in each path that is \(s-\alpha\) from one end of the path; and \(v_0\) is adjacent to \(t/2\)-many \(s\)-paths at the vertex in each of these paths that is \(s-1-\alpha\) from one end of the path, where \(1 \leq \alpha \leq s-1\).
To illustrate the argument and the labeling, we consider the case of \(s = 5\), \(t = 2\), and \(\alpha = 2\). The cycle is labeled of course with the elements of the subgroup \(H = <3> \leq \mathbf{Z}_{15}\). The root \(v_0\) has label \(\alpha(t+1) = 6\). The path on the lower-left and lower-right would be, using the notation of the theorems, \(P_5^1\) and \(P_5^2\), respectively.
Thus, we have established the following result:
Theorem 5. Let \(s \geq 3\) be odd, \(t\geq 2\) be even, and \(R_{st+1}\) be the tree described above. Then \(C_s \cup R_{st+1}\) is harmonious.
Regarding the proofs, it should be noted that clearly the vertex labels (with the exception of the recycled label of 0 occurring once in the cycle and once again as the label of \(v_0\)) are distinct. Thus, the families of graphs \(C_s \cup P_{st+1}\), \(C_s \cup T_{st+1}\), and \(C_s \cup R_{st+1}\), where \(s \geq 3\) is odd and \(t\) is even, are indeed harmonious. The proofs work nicely to a large extent because of the existence of the subgroup whose order divides the order of the group; this occurred by design, as we chose the order of the cycle (and so the cyclic subgroup) to divide the order of the graph (and so the cyclic group). In particular, since \(s \mid |\mathbf{Z}_{s(t+1)}|\), we could use the elements of the subgroup \(H = <t+1>\leq \mathbf{Z}_{st+s}\) for the labels of the cycle vertices. We seek answers to further questions that arise such as the following: Could the proofs here be modified so to include paths and starlike trees with an odd number of paths emanating from the root? Or, what about starlike trees with an even number of paths, but with the paths having a different specified length other than \(s\). These questions would surely require further investigation. Curiously, we can still apply the same subgroup labeling to the vertices of the odd cycle when \(t\) is odd, but the labeling function presented here yields repeated edge labels on the trees. We leave it to the reader to verify this. Thus, for the future, we are left to ponder the question as to whether this disjoint union would be harmonious when \(t\) is odd.