Properly even harmonious labeling of a union of stars

Electronic Journal of Graph Theory and Applications

Zachary M. Henderson

University of Minnesota - Duluth

hende873@d.umn.edu

A function f is defined as an even harmonious labeling on a graph G with q edges if \(f:V(G) \to \{0,1,\ldots,2q\}\) is an injection and the induced function \(f^*:E(G) \to \{0,2,\ldots,2(q-1)\}\) defined by \(f^*(uv)=f(u)+f(v)\) (mod 2q) is bijective. A properly even harmonious labeling is an even harmonious labeling in which the codomain of f is \(\{0,1,\ldots,2q-1\}\), and a strongly harmonious labeling is an even harmonious labeling that also satisfies the additional condition that for any two adjacent vertices with labels u and v, \(0 < u + v \le 2q\). In [3], Gallian and Schoenhard proved that \(S_{n_1} \cup S_{n_2} \cup \cdots \cup S_{n_t}\) is strongly even harmonious for \(n_1 \ge n_2 \ge \cdots \ge n_t\) and \(t < \frac{n_1}{2} + 2\). In this paper, we begin with the related question "When is the graph of k n-star components, \(G = kS_n\), properly even harmonious?" We conclude that \(kS_n\) is properly even harmonious if and only if k is even or k is odd, k > 1, and \(n \ge 2\). We also conclude that \(S_{n_1} \cup S_{n_2} \cup \cdots \cup S_{n_k}\) is properly even harmonious when \(k \ge 2\), \(n_i \ge 2\) for all i and give some additional results on combinations of star and banana graphs.

Keywords: properly even harmonious, star graph, banana tree, graph labeling

Mathematics Subject Classification: 05C78

DOI: 10.5614/ejgta.2024.12.1.1

1. Introduction

A harmonious graph labeling was first defined by Graham and Sloane [5]. A function f is a harmonious labeling of a graph G with q edges if \(f:V(G) \to \{0,1,...,q-1\}\) is an injection and

Received: 15 June 2021, Revised: 28 May 2023, Accepted: 24 October 2023.

the induced function \(f^*: E(G) \to \{0, 1, ..., q-1\}\) defined by \(f^*(uv) = f(u) + f(v) \mod q\) is bijective, and when G is a tree, exactly one vertex label may be used on two vertices. An even harmonious labeling is a variation of harmonious labeling first defined by Sarasija and Binthiya [6] such that a graph with p vertices and q edges is even harmonious if it is possible to label the vertices with distinct integers from the set \(\{0, 1, ..., 2q\}\) in such a way that the set of induced edge labels is a bijection with the set of even integers (modulo 2q). In these labelings, the label of a given edge xy is the sum of the labels of the end vertices x and y, f(x) and f(y). In our paper, we determine when some unions of stars and banana trees are properly even harmonious.

2. Preliminaries

We start by presenting a formal definition of an even harmonious labeling.

Definition 2.1. A function f is an even harmonious labeling of a graph G with q edges if \(f:V(G) \to \{0,1,\ldots,2q\}\) is an injection and the induced function \(f^*:E(G) \to \{0,2,\ldots,2(q-1)\}\) defined by \(f^*(uv) = f(u) + f(v) \mod 2q\) is bijective.

Now, we define two variations of an even harmonious labeling with added restrictions.

Definition 2.2. A function f is a properly even harmonious labeling of a graph G with q edges if \(f:V(G) \to \{0,1,\ldots,2q-1\}\) is an injection and the induced function \(f^*:E(G) \to \{0,2,\ldots,2(q-1)\}\) defined by \(f^*(uv) = f(u) + f(v) \mod 2q\) is bijective.

Notice the only difference between Definition 2.1 from Definition 2.2 is that for f to be a properly even harmonious labeling, it cannot use the vertex label 2q.

Definition 2.3. A strongly even harmonious labeling is an even harmonious labeling that also satisfies the additional condition that for any two adjacent vertices with labels u and v, we have \(0 < u + v \le 2q\).

The following result by Gallian and Schoenhard was the main motivation for our original research. We asked the question "If we relax the condition of strongly even harmonious to properly even harmonious, when does the graph \(kS_n\) have a properly even harmonious labeling?"

Theorem 2.1. (Gallian and Schoenhard [3]) \(S_{n_1} \cup S_{n_2} \cup \cdots \cup S_{n_k}\) is strongly even harmonious for \(n_1 \geq n_2 \geq \cdots \geq n_k\) and \(k < \frac{n_1}{2} + 2\).

Additionally, we reference the following theorems to complete some remaining cases in our results. Notice that \(P_3 = S_2\), \(P_2 = S_1\), and \(S_n\) is a tree, so Theorems 2.2, 2.3, and 2.4 apply to unions of stars.

Theorem 2.2. (Gallian and Stewart [4]) \(P_m \cup S_{n_1} \cup S_{n_2} \cup \cdots \cup S_{n_k}\) is properly even harmonious when m > 2 and at least one \(n_i\) is greater than 1.

Theorem 2.3. (Gallian and Schoenhard [3]) \(kP_2\) is properly even harmonious if and only if k is

Theorem 2.4. (Gallian and Schoenhard [3]) A tree cannot have a properly even harmonious labeling.

3. Results

We begin by showing that \(S_{n_1} \cup S_{n_2} \cup \cdots \cup S_{n_k}\) is properly even harmonious when \(n_i \geq 2\). Lemma 3.1 reduces this situation to two additional cases. Then, after slightly altering the labeling method, we're able to produce the desired result (Theorem 3.1).

Lemma 3.1. \(S_{n_1} \cup S_{n_2} \cup \cdots \cup S_{n_k}\) is properly even harmonious when \(n_i \geq 2\) for all \(i, k \geq 2\), and \(n_1, n_2 \geq 3\).

Proof. Consider \(G = S_{n_1} \cup S_{n_2} \cup \cdots \cup S_{n_k}\), the union of k \(n_i\)-stars where \(n_i \geq 2\). Then, there are \(q = \sum_{i=1}^k n_i\) edges in G and the labeling is done modulo 2q. Because all edge labels are even, all vertex labels in a given star must have the same even/odd parity. Throughout the construction, we will use a to determine which parity the vertex labels of the stars have. We define a for the remainder of the construction as follows:

• if k even, let \(a = \frac{k}{2}\).
• if k odd, let \(a = \frac{k-1}{2}\).

Without loss of generality, we can assume \(n_1 \geq n_2 \geq \cdots \geq n_k\). Now, label G in the following way. For \(1 \leq i \leq k\), let \(v_{i,0}\) be the center vertex of \(S_{n_i}\), \(v_{i,j}\) be the leaf vertices of \(S_{n_i}\) (\(1 \leq j \leq n_i\)), and \(e_{i,j} = v_{i,0}v_{i,j}\). When no confusion may arise, we will identify a vertex/edge with its associated vertex/edge label; instead of saying "vertex \(v_{i,j}\) with label \(f(v_{i,j}) = c\)", we will say \(v_{i,j} = c\). Then, label the vertices and edges of \(S_{n_1}, \ldots, S_{n_a}\) as follows (see Figures 1 and 3) (all computations are assumed to be modulo 2q):

• 1. Recursively label all edges with \(e_{1,1}=0\), \(e_{i,1}=e_{i-1,n_i}+2\), and \(e_{i,j}=e_{i,j-1}+2\)
• 2. When \(1 \le i \le a\), recursively label the center vertices with \(v_{1,0} = q 1\) and \(v_{i,0} = v_{i-1,0} 2\). Then label the leaf vertices \((j \ne 0)\) recursively with \(v_{1,1} = q + 1\), \(v_{i,j} = v_{i,j-1} + 2\), and \(v_{i,1} = v_{i-1,n_{i-1}} + 4\).

Particularly, the closed form for these labels are

\[v_{i,0} = q - 1 - 2(i - 1) = q + 1 - 2i\] \[v_{i,j} = q + 2(\sum_{\ell=1}^{i-1} n_{\ell}) + 2i + 2j - 3 \text{ for } j \neq 0\] \[e_{i,j} = 2(\sum_{\ell=1}^{i-1} n_{\ell}) + 2j - 2\]

Now, the labels of \(S_{n_{a+1}}, \ldots, S_{n_k}\) will depend on \(e_{a+1,1}\), the first edge in \(S_{n_{a+1}}\). Let \(q' = \sum_{\ell=1}^a n_\ell\) be the total number of edges in the first a stars and label \(S_{n_{a+1}}, \ldots, S_{n_k}\) as follows:

Case 1. if q - 1 and q' have the same even/odd parity:

When \(a+1 \le i \le k\), recursively label the center vertices with \(v_{a+1,0}=q'-1\) and \(v_{i,0}=v_{i-1,0}-2\). Then label the leaf vertices recursively with \(v_{a+1,1}=q'+1\), \(v_{i,j}=v_{i,j-1}+2\), and \(v_{i,1}=v_{i-1,n_{i-1}}+4\).

Particularly, the closed form for these labels are

\[v_{i,0} = q' - 1 - 2(i - a - 1) = q' + 1 - 2(i - a)\] \[v_{i,j} = 2\left(\sum_{\ell=a+1}^{i-1} n_{\ell}\right) + q' + 1 + 2(i - a - 1) + 2(j - 1) \text{ for } j \neq 0\] \[e_{i,j} = 2q' + 2\left(\sum_{\ell=a+1}^{i-1} n_{\ell}\right) + 2(j - 1) = 2\left(\sum_{\ell=1}^{i-1} n_{\ell}\right) + 2j - 2\]

Claim. This labeling is properly even harmonious when k is even.

Proof. Considering each parity of vertex labels separately:

(a) Since all edges are of the form ei,j = vi,0vi,j , show f ∗ (ei,j ) = f(vi,0) + f(vi,j ). For Sⁿ¹ . . . , S^na , 1 ≤ i ≤ a and 1 ≤ j ≤ nⁱ . Then, f ∗ (ei,j ) = f(vi,0) + f(vi,j ) mod 2q since:

\[f^*(e_{i,j}) = f(v_{i,0}) + f(v_{i,j})\] \[2(\sum_{\ell=1}^{i-1} n_{\ell}) + 2j - 2 = q + 2(\sum_{\ell=1}^{i-1} n_{\ell}) + 2i + 2j - 3 + q + 1 - 2i\] \[2(\sum_{\ell=1}^{i-1} n_{\ell}) + 2j - 2 = 2q + 2(\sum_{\ell=1}^{i-1} n_{\ell}) + 2j - 2\]

which are equivalent modulo 2q.

For S^na , . . . , S^nk , a + 1 ≤ i ≤ k and 1 ≤ j ≤ nⁱ . Then, f ∗ (ei,j ) = f(vi,0) + f(vi,j ) mod 2q since:

\[f^*(e_{i,j}) = f(v_{i,0}) + f(v_{i,j})\] \[2q' + 2(\sum_{\ell=a+1}^{i-1} n_{\ell}) + 2j - 2 = 2(\sum_{\ell=a+1}^{i-1} n_{\ell}) + q' + 1 + 2(i - a - 1) + 2(j - 1)\] \[+ q' - 1 - 2(i - a - 1)\] \[2q' + 2(\sum_{\ell=a+1}^{i-1} n_{\ell}) + 2j - 2 = 2q' + 2(\sum_{\ell=a+1}^{i-1} n_{\ell}) + 2j - 2\]

which are equal (and hence equivalent modulo 2q). Additionally,

\[f^*: E(G) \to \{0, 2, \dots, 2(q-1)\}\]

is a bijection since all desired edge labels are used exactly once.

(b) Now, in order for f to be injective, we need to make sure no vertex label is duplicated. Since we labeled the centers in decreasing order and the leaves in increasing order, we need to compare the smallest center label with the largest leaf label of

each parity of labels. Specifically, since our computations are modulo 2q and the center labels are smaller than the leaf labels (without the modulus), we need to show \(v_{a,n_a} - 2q < v_{a,0}\) and \(v_{k,n_k} - 2q < v_{k,0}\). For \(S_{n_1}, \ldots S_{n_a}\),

\[v_{a,n_a} - 2q < v_{a,0}\] \[q + 2(\sum_{\ell=1}^{a-1} n_{\ell}) + 2a + 2n_a - 3 - 2q < q + 1 - 2a\] \[2(\sum_{\ell=1}^{a-1} n_{\ell}) + 4a + 2n_a - 4 < 2q\] \[\sum_{\ell=1}^{a-1} (n_{\ell}) + 2a + n_a - 2 < \sum_{\ell=1}^{k} n_{\ell}\] \[2a - 2 < \sum_{\ell=a+1}^{k} n_{\ell}\]

and since \(n_{\ell} \geq 2\) for all \(\ell\) and

• i. if k even, \(a=\frac{k}{2}\), so the sum has k-(a+1)+1=a terms. ii. if k odd, \(a=\frac{k-1}{2}\), so the sum has k-(a+1)+1=a+1 terms. we get that

\[2a - 2 < 2a \le \sum_{\ell=a}^{k} n_{\ell}\]

Hence, no vertex label used in \(S_{n_1}, \ldots, S_{n_n}\) is duplicated. For \(S_{n_{a+1}}, \ldots, S_{n_k}\),

\[v_{k,n_k} - 2q < v_{k,0}\] \[2(\sum_{\ell=a+1}^{k-1} n_{\ell}) + q' + 1 + 2(k-a-1) + 2(n_k-1) - 2q < q' + 1 - 2(k-a)\] \[2(\sum_{\ell=a+1}^{k-1} n_{\ell}) + 4k - 4a + 2n_k - 4 < 2q\] \[\sum_{\ell=a+1}^{k-1} (n_{\ell}) + 2k - 2a + n_k - 2 < \sum_{\ell=1}^{k} n_{\ell}\] \[2k - 2a + n_k - 2 < (\sum_{\ell=1}^{a} n_{\ell}) + n_k\] \[2k - 2a - 2 \le \sum_{\ell=1}^{a} n_{\ell}\]

and since \(n_1, n_2 \ge 3\), \(n_\ell \ge 2\) for all \(\ell\), and

i. if k even, a = k 2 ,

\[2k - 2a - 2 \le \sum_{\ell=1}^{a} n_{\ell}\]\[k - 2 < 2a + 1 \le \sum_{\ell=1}^{a} n_{\ell}\]\[k - 2 < k + 1 \le \sum_{\ell=1}^{a} n_{\ell}\]

where we have a lower bound of 2a + 1 since if a = 1, n² wouldn't be in the sum.

ii. if k odd, a = k−1 2 ,

\[2k - 2a - 2 < \sum_{\ell=1}^{a} n_{\ell}\]\[k - 1 < 2a + 1 \le \sum_{\ell=1}^{a} n_{\ell}\]\[k - 1 < k \le \sum_{\ell=1}^{a} n_{\ell}\]

where we again have a lower bound of 2a + 1 since if a = 1, n² wouldn't be in the sum.

Hence, no vertex label used in Sⁿa+1 , . . . , S^nk is duplicated. Furthermore, since the vertex labels used in Sⁿ¹ , . . . , S^na and Sⁿa+1 , . . . , S^nk are of different parities, there are no duplicate vertex labels. Hence f is injective, f ∗ is bijective, and f ∗ (ei,j ) = f(vi,0) + f(vi,j ), so the given labeling is properly even harmonious.

Figure 1: A properly even harmonious labeling for S⁵ ∪ S⁴ ∪ S³ ∪ S2. q − 1 = 13 and q ′ = 9 have the same parity

Case 2. if q − 1 and q ′ have different even/odd parities:

When a + 1 ≤ i ≤ k, recursively label the center vertices with vi,a+1 = q ′ − 2 and vi,⁰ = vi−1,⁰ − 2. Then label the leaf vertices recursively with va+1,¹ = q ′ + 2, vi,j = vi,j−¹ + 2, and vi,¹ = vi−1,ni−¹ + 4.

Particularly, the closed form for these labels are:

\[v_{i,0} = q' - 2 - 2(i - a - 1) = q' - 2(i - a)\] \[v_{i,j} = 2\left(\sum_{\ell=a+1}^{i-1} n_{\ell}\right) + q' + 2 + 2(i - a - 1) + 2(j - 1) \text{ for } j \neq 0\] \[e_{i,j} = 2q' + 2\left(\sum_{\ell=a+1}^{i-1} n_{\ell}\right) + 2(j - 1) = 2\left(\sum_{\ell=1}^{i-1} n_{\ell}\right) + 2j - 2\]

Claim. This labeling is properly even harmonious.

Proof. The proof for Sⁿ¹ , . . . S^na is the same as the previous proof since the cases didn't affect this labeling. So, consider Sⁿa+1 , . . . S^nk .

(a) For \[a + 1 \le i \le k\], \(f^*(e_{i,j}) = f(v_{i,0}) + f(v_{i,j})\) since

\[f^*(e_{i,j}) = f(v_{i,0}) + f(v_{i,j})\] \[2q' + 2\left(\sum_{\ell=a+1}^{i-1} n_{\ell}\right) + 2j - 2 = 2\left(\sum_{\ell=a+1}^{i-1} n_{\ell}\right) + q' + 2 + 2(i - a - 1) + 2(j - 1)\] \[+ q' - 2(i - a)\] \[2q' + 2\left(\sum_{\ell=a+1}^{i-1} n_{\ell}\right) + 2j - 2 = 2q' + 2\left(\sum_{\ell=a+1}^{i-1} n_{\ell}\right) + 2j - 2\]

which are equal (and hence equivalent mod 2q). Additionally,

\[f^*: E(G) \to \{0, 2, \dots, 2(q-1)\}\]

is a bijection since all desired edge labels are used exactly once.

(b) Now, in the same way as the previous proof, we must check that vk,n^k − 2q < vk,0.

\[v_{k,n_k} - 2q < v_{k,0}\] \[2(\sum_{\ell=a+1}^{k-1} n_{\ell}) + q' + 2 + 2(k-a-1) + 2(n_k-1) - 2q \le q' - 2(k-a)\] \[2(\sum_{\ell=a+1}^{k-1} n_{\ell}) + 4k - 4a + 2n_k - 2 \le 2q\] \[(\sum_{\ell=a+1}^{k-1} n_{\ell}) + 2k - 2a + n_k - 1 \le \sum_{\ell=1}^{k} n_{\ell}\] \[2k - 2a + n_k - 1 \le (\sum_{\ell=1}^{a} n_{\ell}) + n_k\] \[2k - 2a - 1 \le \sum_{\ell=1}^{a} n_{\ell}\]

Then, since n1, n² ≥ 3 and n^ℓ ≥ 2,

i. if k even, a = k 2 ,

\[2k - 2a - 1 < \sum_{\ell=1}^{a} n_{\ell}\]\[k - 1 < 2a + 1 \le \sum_{\ell=1}^{a} n_{\ell}\]\[k - 1 < k + 1 \le \sum_{\ell=1}^{a} n_{\ell}\]

where we have a lower bound of 2a + 1 since if a = 1, n² wouldn't be in the sum.

ii. if k odd, a = k−1 2 , if a ≥ 2, we have

\[2k - 2a - 1 < \sum_{\ell=1}^{a} n_{\ell}\]\[k < 2a + 2 \le \sum_{\ell=1}^{a} n_{\ell}\]\[k < k + 1 \le \sum_{\ell=1}^{a} n_{\ell}\]

and if a = 1, then k = 3 and we have 3 possibilities:

• A. If G = S³ ∪ S³ ∪ S2, then q = 8 so q − 1 = 7 and q ′ = 3 have the same parity so G doesn't belong to this case.
• B. If G = S³ ∪ S³ ∪ S3, this labeling method doesn't work. However, with a slight adjustment, we get that G is properly even harmonious (Figure 2):

Figure 2: A properly even harmonious labeling for 3S3.

C. Otherwise, n¹ ≥ 4, so 2a + 2 ≤ P^{a ℓ}=1 n^ℓ as above, so we get

\[k < k + 1 \le \sum_{\ell=1}^{a} n_{\ell}\]

Hence, no vertex label used in Sⁿa+1 , . . . , S^nk is duplicated. Furthermore, since the vertex labels used in Sⁿ¹ , . . . , S^na and Sⁿa+1 , . . . , S^nk are of different parities, there are no duplicate vertex labels. Hence f is injective, f ∗ is bijective, and f ∗ (ei,j ) = f(vi,0) + f(vi,j ), so the given labeling is properly even harmonious.

Figure 3: A properly even harmonious labeling for S³ ∪ S³ ∪ S² ∪ S² ∪ S2. q − 1 = 11 and q ′ = 6 have different parities.

Lemma 3.2. S³ ∪ S² ∪ · · · ∪ S² is properly even harmonious when there are an odd number of S2.

Proof. Let k be the number of stars in G = S³ ∪ S² ∪ · · · ∪ S2. Since there are an odd number of S2, k is even. Let q = 2k + 1 be the number of edges in G, so calculations are done modulo 2q = 4k + 2.

Figure 4: A properly even harmonious labeling for \(S_3 \cup S_2 \cup \cdots \cup S_2\) for an odd number of \(S_2\)

Label the vertices of the first \(\frac{k}{2}\) copies of \(S_2\) as given in Figure 4:

• 1. Label the centers with 2k + 2 2i for \(1 \le i \le \frac{k}{2}\).
• 2. Label the top vertices with 2k 4 + 6i for \(1 \le i \le \frac{k}{2}\).
• 3. Label the bottom vertices with 2k-2+6i for \(1 \le i \le \frac{k}{2}\).

Since the labels \(k+2, k+4, \ldots, k-4, k-6\) are in ascending order and k-6 < k+2, all even vertex labels are distinct modulo 2q. Additionally, label the edges of these stars with \(\{0, 2, \ldots, 2k-2\}\) as in Figure 4.

Now, consider the remaining \(\frac{k}{2} - 1\) 2-stars and 3 star. Label the vertices of the \(\frac{k}{2} - 1\) 2-stars as given in Figure 4:

• 1. Label the centers with k+1-2i for \(1 \le i \le \frac{k}{2}-1\).
• 2. Label the top vertices with k-5+6i for \(1 \le i \le \frac{k}{2}-1\).
• 3. Label the bottom vertices with k-3+6i for \(1 \le \tilde{i} \le \frac{k}{2} 1\).

and the 3-star as given in Figure 4:

• 1. Label the center with 1.
• 2. Label the vertices with 4k 5, 4k 3, 4k 1.

Since the labels \(1, 3, \ldots, 4k-3, 4k-1\) are in ascending order and 4k-1 < 2q = 4k+2, all odd vertex labels are distinct modulo 2q. Additionally, label the edges with the set \(\{2k, 2k+2, \ldots, 4k\}\) as in Figure 4.

Now, since all vertex labels are distinct, \(f:V(G)\to\{0,1,\ldots,2q-1\}\) is injective. Furthermore, \(f^*:E(G)\to\{0,2,\ldots,2(q-1)\}\) is bijective and, by construction, \(f^*(uv)=f(u)+f(v)\) for edge uv between vertices u and v. Hence, this labeling is properly even harmonious. \(\square\)

Lemma 3.3. \(S_3 \cup S_2 \cup \cdots \cup S_2\) is properly even harmonious when there are an even number of \(S_2\).

Proof. Let k be the number of stars in \(G = S_3 \cup S_2 \cup \cdots \cup S_2\). Since there are an even number of \(S_2\), k is odd and k = 2a + 1 for some integer a. Let q = 2k + 1 = 4a + 3 be the number of edges in G, so calculations are done modulo 2q = 4k + 2 = 8a + 6.

Figure 5: A properly even harmonious labeling for S³ ∪ S² ∪ · · · ∪ S² for an even number of S²

Label the vertices of the first a + 1 copies of S² as given in Figure 5:

• 1. Label the centers with 4a + 4 − 2i for 1 ≤ i ≤ a + 1.
• 2. Label the top vertices with 4a − 2 + 6i for 1 ≤ i ≤ a + 1.
• 3. Label the bottom vertices with 4a + 6i for 1 ≤ i ≤ a + 1.

Since the labels 2a+2, 2a+4, . . . , 2a−4 are in ascending order and 2a−4 < 2a+2, all even vertex labels are distinct modulo 2q. Additionally, label the edges of these stars with {0, 2, . . . , 4a − 2} as in Figure 5.

Now, consider the remaining a − 1 2-stars and 3-star. Label the vertices of the a − 1 2-stars as given in Figure 5:

• 1. Label the centers with 2a + 3 − 2i for 1 ≤ i ≤ a − 1.
• 2. Label the top vertices with 2a − 3 + 6i for 1 ≤ i ≤ a − 1.
• 3. Label the bottom vertices with 2a − 1 + 6i for 1 ≤ i ≤ a − 1.

and the 3-star as given in Figure 5:

• 1. Label the center with 3.
• 2. Label the vertices with 8a − 3, 8a − 1, 8a + 1.

Since the labels 3, 5, . . . , 8a + 4 are in ascending order and 8a + 4 < 2q = 8a + 6, all odd vertex labels are distinct modulo 2q. Additionally, label the edges with the set {4a+4, 4a+6, . . . , 8a+4} as in Figure 5.

Now, since all vertex labels are distinct, f : V (G) → {0, 1, . . . , 2q − 1} = {0, 1, . . . , 8a + 5} is injective. Furthermore, f ∗ : E(G) → {0, 2, . . . , 2(q − 1)} = {0, 2, . . . , 8a + 4} is bijective and, by construction, f ∗ (uv) = f(u) + f(v) for edge uv between vertices u and v. Hence, this labeling is properly even harmonious.

Lemma 3.4. kS² is properly even harmonious.

Proof. This was proved by Gallian and Stewart in [4] as Theorem 3.4: "the graph Pn∪S^t1∪· · ·∪S^tk is properly even harmonious for n > 2 and at least one tⁱ is greater than 1." Here, we use the fact that P³ = S² and let tⁱ = 2 for all i to get the result.

Theorem 3.1. Sⁿ¹ ∪Sⁿ² ∪ · · · ∪ S^nk is properly even harmonious when nⁱ ≥ 2 for all i and k ≥ 2.

Now, if we consider kSⁿ = Sⁿ ∪ Sⁿ ∪ · · · ∪ Sn, we can completely determine which graphs of this type are properly even harmonious. Using Theorem 3.1, we need only look at kS¹ and the graph of a single star Sn.

Lemma 3.5. Sⁿ is not properly even harmonious.

Proof. The result follows from Lemmas 3.1, 3.2, 3.3, and 3.4.

Proof. This was proved by Gallian and Schoenhard in [3] as a case of Theorem 3.1: "A tree cannot have a properly even harmonious labeling." Since Sⁿ is a tree, we get the result.

Lemma 3.6. kS¹ is properly even harmonious if and only if k is even.

Proof. This was proved by Gallian and Schoenhard in [3] as Theorem 4.1: "nP² is properly even harmonious if and only if n is even." Here, we use the fact that P² = S¹ to get the result.

Now, by collecting the results from above, we can prove the following theorem. Theorem 3.2 gives necessary and sufficient condition for the values of n and k that make G = kSⁿ properly even harmonious, which is the solution to our original research question.

Theorem 3.2. kSⁿ is properly even harmonious if and only if:

• 1. k is even and n ≥ 1, or
• 2. k is odd, k > 1, and n ≥ 2.

Proof. This follows from Theorem 3.1, Lemma 3.5, and Lemma 3.6.

Now, we can make an interesting observation from Theorem 3.2. In [1], Barrientos and Youssef cite Youssef's previous result in [7] that if G is harmonious, then nG is also harmonious given that n > 0 is odd. This same relationship is also applicable to the properly even harmoniousness of G = kSⁿ as given in the following observation.

Observation 3.1. If G = kSⁿ is properly even harmonious, then k ′G is also properly even harmonious for any k ′ > 0.

Proof. Using the fact that k ′G = k ′ (kSn) = (k ′k)Sn,

Case 1. if k is even, then k ′k is even and (k ′k)Sⁿ is properly even harmonious.

Case 2. if k is odd, k ′ is even, then k ′k is even and (k ′k)Sⁿ is properly even harmonious.

Case 3. if k is odd, k ′ is odd, then since kSⁿ is properly even harmonious, k > 1 and n ≥ 2. Thus, k ′k is odd and k ′k ≥ k > 1 and n ≥ 2, so (k ′k)Sⁿ is also properly even harmonious.

Additionally, we give a properly even harmonious labeling for B2,k ∪ B2,k where Bn,k is an (n, k)−banana tree. Combining the labeling method from Theorem 3.3 with the method from Theorem 3.1, we're able to produce a properly even harmonious labeling in Theorems 3.4 and 3.5.

Theorem 3.3. \(B_{2,k} \cup B_{2,k}\) is properly even harmonious.

Proof. Since we have two disconnected components, we label the first banana tree, \(B_{2,k}^1\), with even vertex labels and the second banana tree, \(B_{2,k}^2\), with odd vertex labels as given in Figure 6.

Figure 6: A properly even harmonious labeling for \(G = B_{2,k} \cup B_{2,k}\)

Let q=4k+4 be the number of edges in G, so calculations are done modulo 2q=8k+8. Consider \(B_{2,k}^1\). Label the vertices of a path of length 7 in \(B_{2,k}^1\) with the sequence 4, 2q-4, 6, 2q-2, 8, 0, 10, the remaining leaf vertices of the second star with \(12, 14, \ldots, 10+2(k-2)=2k+6\), and the remaining leaf vertices of the first star with \(2k+12, 2k+14, \ldots, 4k+6\). Since the leaf vertices are labeled in increasing order, the largest leaf label is 4k+6 < 8k+4=2q-4 (the "smallest" label of \(B_{2,k}^1\) if considered as -4) for all k>1, so all even vertex labels are distinct modulo 2q. Additionally, label the edges of \(B_{2,k}^1\) with the set \(\{0,2,\ldots,4k+2\}\) as given in Figure 6.

Now, consider \(B_{2,k}^2\). Label the vertices of a path of length 7 in \(B_{2,k}^2\) with the sequence 2k+5, 2k-1, 2k+7, 2k+1, 2k+9, 2k+3, 2k+11, the additional leaf vertices of the second star with \(2k+13, 2k+15, \ldots, 4k+7\), and the additional leaf vertices of the first star with \(4k+13, 4k+15, \ldots, 6k+7\). Since the leaf vertices are labeled in increasing order, the largest leaf label is 6k+7 < 8k+8 = 2q and the smallest label is 2k-1>0, so all odd vertex labels are distinct modulo 2q. Additionally, label the edges of \(B_{2,k}^2\) with the set \(\{4k+4, 4k+6, \ldots, 8k+6\}\) as given in Figure 6.

Now, since all vertex labels are distinct, \(f:V(G)\to\{0,1,\ldots,2q-1\}\) is injective. Furthermore, \(f^*:E(G)\to\{0,2,\ldots,2(q-1)\}\) is bijective and, by construction, \(f^*(uv)=f(u)+f(v)\) for edge uv between vertices u and v. Hence, this labeling is properly even harmonious. \(\square\)

Theorem 3.4. \(B_{2,k_1} \cup S_{k_2}\) is properly even harmonious if \(k_2 > 2\).

Proof. Since we have two disconnected components, label \(B_{2,k_1}\) with even labels and \(S_{k_2}\) with odd vertex labels as given in Figure 7.

Figure 7: A properly even harmonious labeling for G = B2,k¹ ∪ Sk²

Let q = 2k¹ +k² + 2 be the number of edges in G, so calculations are done modulo 2q = 4k¹ + 2k2+4. Label the vertices of a path of length 7 in B2,k¹ with the sequence 3, 2q−3, 5, 2q−1, 7, 1, 9, the remaining leaf vertices of the second star with 11, 13, . . . , 2k¹ + 5, and the remaining leaf vertices of the first star with 2k¹ + 11, 2k¹ + 13, . . . , 4k¹ + 5. Since the leaf vertices are labeled in increasing order, the largest leaf label is 4k¹ + 5 < 2q − 3 (the "smallest" label of B2,k¹ if considered as -3), so all odd vertex labels are distinct modulo 2q. This comes from the inequality

\[4k_1 + 5 < 2q - 3\] \[4k_1 + 5 < 2(2k_1 + k_2 + 2) - 3\] \[2 < k_2\]

since k² > 2. Additionally, label the edges of B2,k¹ with {0, 2, . . . 4k¹ + 2} as given in Figure 7.

Now, consider S^k2 . Label the center vertex with 2k¹ which is even and the leaf vertices with 2k¹ + 2 + 2i for 1 ≤ i ≤ k² as in Figure 7. Since the leaves are labeled in increasing order and 2k¹ + 2k² + 2 < 2q, all of the even vertex labels are distinct. Additionally, label the edges of S^k2 with {4k¹ + 4, 4k¹ + 6, . . . , 4k¹ + 2k² + 2} as in Figure 7.

Now, since all vertex labels are distinct, f : V (G) → {0, 1, . . . , 2q − 1} is injective. Furthermore, f ∗ : E(G) → {0, 2, . . . , 2(q − 1)} is bijective and, by construction, f ∗ (uv) = f(u) + f(v) for edge uv between vertices u and v. Hence, this labeling is properly even harmonious.

Theorem 3.5. B2,k¹ ∪ S^k2 ∪ S^k3 is properly even harmonious if k² > 1.

Proof. Label B2,k¹ with odd vertex labels and label S^k2 , S^k3 with even vertex labels as given in Figure 8

Figure 8: A properly even harmonious labeling for G = B2,k¹ ∪ Sk² ∪ Sk³

Let q = 2k¹ + k² + k³ + 2 be the number of edges in G, so calculations are done modulo 2q = 4k¹ + 2k² + 2k³ + 4. Label the vertices of a path of length 7 in B2,k with the sequence 3, 2q − 3, 5, 2q − 1, 7, 1, 9, the remaining leaf vertices of the second star with 11, 13, . . . , 2k¹ + 5, and the remaining leaf vertices of the first star with 2k¹ + 11, 2k¹ + 13, . . . , 4k¹ + 5. Since the leaf vertices are labeled in increasing order, the largest leaf label is 4k¹ + 5 < 2q − 3 (the "smallest" label of B2,k¹ if considered as -3), so all odd vertex labels are distinct modulo 2q. This comes from the inequality

\[4k_1 + 5 < 2q - 3\] \[4k_1 + 5 < 2(2k_1 + k_2 + k_3 + 2) - 3\] \[2 < k_2 + k_3\]

since k² > 1. Additionally, label the edges of B2,k¹ with {0, 2, . . . 4k¹ + 2} as given in Figure 8. Now, consider S^k2 and S^k3 . Label the center vertex of S^k2 with 2k¹ and the center vertex of S^k3 with 2k¹ − 2, which are both even. Label the leaf vertices of S^k2 with 2k¹ + 2 + 2i for 1 ≤ i ≤ k² and the leaf vertices of S^k3 with 2k¹ + 2k² + 4 + 2i for 1 ≤ i ≤ k³ as in Figure 8. Since the leaves are labeled in increasing order, the largest leaf is 2k¹ + 2k² + 2k³ + 4 <

2q, and the smallest center is 2k¹ − 2 ≥ 0, so all of the even labels are distinct. Additionally, label the edges of S^k2 with {4k¹ + 4, 4k¹ + 6, . . . , 4k¹ + 2k² + 2} and the edges of S^k3 with {4k¹ + 2k² + 4, 4k¹ + 2k² + 6, . . . , 4k¹ + 2k² + 2k³ + 2} as in Figure 8.

Now, since all vertex labels are distinct, f : V (G) → {0, 1, . . . , 2q − 1} is injective. Furthermore, f ∗ : E(G) → {0, 2, . . . , 2(q − 1)} is bijective and, by construction, f ∗ (uv) = f(u) + f(v) for edge uv between vertices u and v. Hence, this labeling is properly even harmonious.

Acknowledgement

The author would like to thank his advisor Dr. Dalibor Froncek for his help and guidance on this project, Dr. Joseph Gallian and Dr. Xuan Li for serving on his committee with their valuable comments and feedback, his professors and classmates who gave him a great experience at UMD, his friends, family, and wife who have supported him, and God for His grace throughout the entire process.

References

• [1] C. Barrientos and M.Z. Youssef, Relaxing the injectivity constraint on arithmetic and harmonious labelings, Electron. J. Graph Theory Appl. 10 (2) (2022), 523–539.
• [2] J.A. Gallian, A dynamic survey of graph labeling (23rd edition), The Electron. J. Combin. (2020), #DS6.
• [3] J.A. Gallian and L.A. Schoenhard, Even harmonious graphs, AKCE Int. J. Graphs Comb. 11 (1) (2014), 27–49.
• [4] J.A. Gallian and D. Stewart, Properly even harmonious labelings of disconnected graphs, AKCE Int. J. Graphs Comb. 12 (2–3) (2015), 193–203.
• [5] R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, SIAM Journal on Algebraic Discrete Methods 1 (4) (1980), 382–404.
• [6] P.B. Sarasija and R. Binthiya, Even harmonious graphs with applications, The International Journal of Computer Science and Information Security 9 (2011), 161–163.
• [7] M.Z. Youssef, Two general results on harmonious labelings, Ars Combinatoria 68 (2003), 225–230.