Harmonious Labelings of Families of Disjoint Unions of an Odd Cycle and Certain Trees

1. Introduction

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\to {\mathbf{Z}}_m$ is said to be a harmonious labeling of $G$ provided that whenever $e_1\ne 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)(\text{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)(\text{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\to \{0,\dots ,2m\}$ is said to be even harmonious labeling of $G$ if the induced function $f^{\ast }:E(G)\to \{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\to \{0,1,\dots ,2m-1\}$ as properly even harmonious labeling of $G$ if the induced function $f^{\ast }:E(G)\to \{0,2,\dots ,2m-2\}$ defined by $f^{\ast }(uv)=f(u)+f(v)$ (mod $2m$) is bijective. An injective function $f:V\to {\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\to \{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.

2. Labeling and proofs

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:

There is an extension of Theorem 1 at [8] that states the following:

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\ge 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.

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),\dots (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.

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,\dots ,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,\dots ,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.

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.

We next compare edge labels from different $s$-paths.

Next, we start joining the paths by edges in the following manner: For $i=1,2,\dots 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.

Now to (2).

We now compare the label of a coset-to-coset edge to the label of an internal coset edge.

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.

Finally, we compare the labels of edges incident to $v_0$ to those of the coset-to-coset edge labels.

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\ge 2$ be even and $s\ge 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.

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\le {\mathbf{Z}}_{s(t+1)}$ of order $s$ generated by $t+1$. That is, we have $H=⟨t+1⟩=\{0,t+1,2(t+1),\dots (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,\dots ,P_s^t$. The vertices of $P_s^i$ are labeled using elements of the coset $H+i$ of $H$, where $1\le i\le 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,\dots ,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,\dots ,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\ne 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.

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\ge 3$ and even $t\ge 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\le \alpha \le 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\le i\le 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\le \alpha \le 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>\le {\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:

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\ge 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>\le {\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.