1 Introduction
In this paper, we consider a graph G as a finite graph (without loop and multiple edges) with the vertex-set V and the edge-set E. In [1], Baca, Jendrol, Miller and Ryan introduced the notion of the total edge irregular k-labeling of a graph G=(V,E) namely the labeling \(\psi:V \cup E \to \{1,2,\ldots,k\}\) such that all edge weights are different. The weight wt(uv) of an edge uv is defined as \(wt_{\psi}(uv) = \psi(u) + \psi(uv) + \psi(v)\). The total edge irregularity strength of G, denoted by tes(G), is the smallest k for which G has a total edge irregular k-labeling.
The basic idea of the total edge irregularity strength came from irregular assignments and the irregularity strength of graphs introduced by Chartrand, Jacobson, Lehel, Oellermann, Ruiz and Saba [2]. An irregular assignment is a k-labeling of the edges such that the sum of the labels of edges incident to a vertex is different for all the vertices of G. The smallest integer k for which G has an irregular assignment is called the irregularity strength of G, and is denoted by s(G).
It is not an easy task to compute the irregularity strength of graphs with simple structures, see [3-6]. Karonski, Luczak and Thomason [7] conjectured that the edges of every connected graph of order at least 3 can be assigned labels from {1, 2, 3} such that for all pairs of adjacent vertices the sums of the labels of the incident edges are distinct. Baca, Jendrol, Miller and Ryan [1] gave a lower bound on the total edge irregularity strength of a graph:
\[tes(G) \ge \max\left\{ \left\lceil \frac{|E(G)| + 2}{3} \right\rceil, \left\lceil \frac{\Delta(G) + 1}{2} \right\rceil \right\}\] (1)
where \(\Delta(G)\) is the maximum degree of G. The authors of [1] determined the exact values of the total edge irregularity strength for paths, cycles, stars, wheels and friendship graphs. Recently, Ivanco and Jendrol [8] posed the following conjecture:
Conjecture 1. Let G be an arbitrary graph different from \(K_{\_}5\). Then
\[tes(G) = \max\left\{ \left\lceil \frac{|E(G)| + 2}{3} \right\rceil, \left\lceil \frac{\Delta(G) + 1}{2} \right\rceil \right\}\] (2)
Conjecture 1 has been verified for all trees in [8], for complete graphs and complete bipartite graphs in [9] and [10], for the Cartesian product of two paths \(P_n \square P_m\) in [11], for the corona product of a path with certain graphs in [12], for large dense graphs with \(\frac{|E(G)|+2}{3} \le \frac{\Delta(G)+1}{2}\) in [13], for hexagonal grids in
[14], for the zigzag graph [15], for the categorical product of two paths \(P_n \times P_m\) [16], for the categorical product of a cycle and a path \(C_n \times P_m\) in [17,18], for a subdivision of stars in [19], for the categorical product of two cycles in [20], and for the strong product of two paths in [21].
Motivated by [22], we investigated the total edge irregularity strength of the disjoint union of helm graphs. A helm graph \(H_n\) is obtained from a wheel on n+1 vertices by adding a pendant edge to every vertex of its cycle \(C_n\). In this study, we determined the total edge irregularity strength of the disjoint union of m copies of a certain helm graph. We also determined the total edge irregularity strength of the disjoint union of non-isomorphic helm graphs.
This paper adds further support to Conjecture 1 by demonstrating that the disjoint union of helm graphs has a total edge irregularity strength equal to
\[\left[\frac{\left|E\left(\bigcup_{j=1}^{m}H_{n+j}\right)\right|+2}{3}\right]\]
2 Main Results
First, we determine the total edge irregularity strength of a disjoint union \(mH_n\) of m copies of a helm graph \(H_n\). Let
\[V(H_n) = \{c^j, x_i^j, y_i^j; 1 \le i \le n, 1 \le j \le m\}\] \[E(H_n) = \{c^j x_i^j, x_i^j y_i^j, x_i^j x_{i+1}^j; 1 \le i \le n, 1 \le j \le m\}\]
Moreover, the subscript n+1 is replaced by 1.
Lemma 1. For \(n \ge 3\) tes \((2H_n) = 2n + 1\).
Proof. From (1) it follows that \(tes(2H_n) \ge 2n+1\). Now the existence of an optimal labeling \(\varphi_1\) proves the converse inequality for \(1 \le i \le n\) as follows:
\[\varphi_{1}(x_{i}^{1}) = \varphi_{1}(y_{i}^{1}) = 1, \quad \varphi_{1}(c^{1}) = \varphi_{1}(c^{2}) = 2n + 1, \varphi_{1}(c^{1}x_{i}^{1}) = \varphi_{1}(x_{i}^{2}x_{i+1}^{2}) = \varphi_{1}(x_{i}^{1}y_{i}^{1}) = \varphi_{1}(x_{i}^{2}y_{i}^{2}) = i, \varphi_{1}(x_{i}^{2}) = 2n + 1, \quad \varphi_{1}(y_{i}^{2}) = n + 1, \quad \varphi_{1}(c^{2}x_{i}^{2}) = \varphi_{1}(x_{i}^{1}x_{i+1}^{1}) = n + i.\]
It is easy to see that the weights of the edges are pair-wise distinct. This concludes the proof.
Theorem 1. Let \(m, n \ge 3\) be two integers. Then, the total edge irregularity strength of a disjoint union \(mH_n\) of m copies of a helm graph \(H_n\) is mn+1.
Proof. As \(|E(mH_n)| = 3mn\) then (1) implies that \(tes(H_n) \ge mn + 1\). Let k = mn + 1. To prove the converse inequality, we define the total edge irregular k-labeling \(\psi_1\) for \(1 \le i \le n\) and \(1 \le j \le m\) as follows:
\[\psi_1(c^j) = \psi_1(x_i^j) = \psi_1(y_i^j) = \min\left\{ \left\lfloor \frac{3n(j-1)+2}{2} \right\rfloor, k \right\}.\]
Case I: For \(1 \le j \le m\) such that \(\left| \frac{3n(j-1)+2}{2} \right| < k\)
(i) When n is even, \(\psi_1(x_i^j y_i^j) = i\), \(\psi_1(x_i^j x_{i+1}^j) = n + i\), \(\psi_1(c^j x_i^j) = 2n + i\),
- (ii) When n is odd,
- (a) If j is odd, then the edges \(c^j x_i^j\), \(x_i^j y_i^j\) and \(x_i^j x_{i+1}^j\) receive the same labels as in Case I (i)
- (b) If j is even, \(\psi_1(x_i^j y_i^j) = 1 + i\), \(\psi_1(x_i^j x_{i+1}^j) = n + 1 + i\), \(\psi_1(c^j x_i^j) = 2n + 1 + i\),
Case II: For \[1 \le j \le m\] such that \(\left\lfloor \frac{3n(j-1)+2}{2} \right\rfloor \ge k\)
Let
\[w = \min \left\{ j; \ 1 \le j \le m \text{ such that } \left\lfloor \frac{3n(j-1)+2}{2} \right\rfloor \ge k \right\}\] \[l = \max \left\{ t_j; \ 1 \le j \le m \text{ such that } \left\lfloor \frac{3n(j-1)+2}{2} \right\rfloor < k \right\}\] \[t_j = \min \left\{ \left\lfloor \frac{3n(j-1)+2}{2} \right\rfloor, \ k \right\} \text{ for } 1 \le j \le m \text{ such that } \left\lfloor \frac{3n(j-1)+2}{2} \right\rfloor < k\]
(i) When n is even, then n is even, \[\psi_{1}\left(x_{i}^{j}y_{i}^{j}\right) = \begin{cases} 3n + 2(l - k) + i, & \text{if } j = w \\ 3n + 2(l - k) + i + (j - w)3n, & \text{if } w + 1 \le j \le m \end{cases}\] \[\psi_{1}\left(x_{i}^{j}x_{i+1}^{j}\right) = \begin{cases} 4n + 2(l - k) + i, & \text{if } j = w \\ 4n + 2(l - k) + i + (j - w)3n, & \text{if } w + 1 \le j \le m \end{cases}\] \[\psi_{1}\left(c^{j}y_{i}^{j}\right) = \begin{cases} 5n + 2(l - k) + i, & \text{if } j = w \\ 5n + 2(l - k) + i + (j - w)3n, & \text{if } w + 1 \le j \le m \end{cases}\]
- (ii) When n is odd,
- (a) If w is odd
\[\psi_1\left(x_i^j\,y_i^j\right) = \begin{cases} 3\,n + 2\,(l-k) + 1 + i, & if \quad j = w \\ 3\,n + 2\,(l-k) + i + 1 + (j-w)3\,n, & if \quad w + 1 \le j \le m \end{cases}\]
\[\psi_1\left(x_i^j x_{i+1}^j\right) = \begin{cases} 4n + 2(l-k) + 1 + i, & \text{if} \quad j = w \\ 4n + 2(l-k) + i + 1 + (j-w)3n, & \text{if} \quad w + 1 \le j \le m \end{cases}\]
\[\psi_1\left(c^j y_i^j\right) = \begin{cases} 5n + 2(l-k) + 1 + i, & \text{if } j = w\\ 5n + 2(l-k) + i + 1 + (j-w)3n, & \text{if } w + 1 \le j \le m \end{cases}\]
(b) If w is even, then the edges \(c^j x_i^j, x_i^j y_i^j\) and \(x_i^j x_{i+1}^j\) receive the same labels as in Case II (i)
Under the labeling \(\psi_1\) the total weights of the edges are described as follows:
- (i) The edges \(x_i^j y_i^j\) for \(1 \le i \le n, 1 \le j \le m\) receive consecutive integers from the interval [3n(j-1)+3, 3n(j-1)+n+2],
- (ii) The edges \(x_i^j x_{i+1}^j\) for \(1 \le i \le n, 1 \le j \le m\) receive consecutive integers from the interval [3n(j-1)+n+3, 3n(j-1)+2n+2],
- (iii) The edges \(c^j x_i^j\) for \(1 \le i \le n, 1 \le j \le m\) receive consecutive integers from the interval [3n(j-1)+2n+3, 3n(j-1)+3n+2].
It is not difficult to see that all vertex and edge labels are at most k and the edge-weights of the edges \(c^j x_i^j, x_i^j y_i^j\) and \(x_i^j x_{i+1}^j\) are pairwise distinct. Thus, the resulting labeling is a total edge irregular k-labeling. This concludes the proof.
For \(m,n \ge 2\), let us consider the disjoint union of m non-isomorphic helm graphs: \(H_{n+1}, H_{n+2}, H_{n+3}, ..., H_{n+m}\), where
\[V\left(\bigcup_{j=1}^{m} H_{n+j}\right) = \left\{c^{j}, x_{i}^{j}, y_{i}^{j}; \ 1 \le i \le n+j, 1 \le j \le m\right\}\] is the corresponding vertex set and
\[E\left(\bigcup_{j=1}^{m} H_{n+j}\right) = \left\{c^{j} x_{i}^{j}, x_{i}^{j} y_{i}^{j}, x_{i}^{j} x_{i+1}^{j} ; 1 \le i \le n+j, 1 \le j \le m\right\}\] is the corresponding edge set. Note that the subscript n+j+1 is replaced by 1.
Now, we determine the exact value of the total edge irregularity strength of the graph \(\bigcup_{i=1}^m H_{n+j}\) .
Theorem 1. Let \(m, n \ge 2\) be two integers and \(G \cong \bigcup_{j=1}^m H_{n+j}\). Then \(tes(G) = mn + 1 + \frac{m(m+1)}{2}\).
Proof. As \(|E(\bigcup_{j=1}^{m} H_{n+j})| = 3\sum_{j=1}^{m} (n+j)\) then from (1) it follows that \(tes(G) \ge mn+1+\frac{m(m+1)}{2}\). Let \(k=mn+1+\frac{m(m+1)}{2}\). To prove the converse inequality, we define the total edge irregular k-labeling \(\psi_2\) for \(1 \le i \le n+j\) and \(1 \le j \le m\) as follows.
For \(1 \le i \le n+1\)
\[\psi_{2}(c^{1}) = \psi_{2}(x_{i}^{1}) = \psi_{2}(y_{i}^{1}) = 1,\] \[\psi_{2}(x_{i}^{1}y_{i}^{1}) = i, \quad \psi_{2}(x_{i}^{1}x_{i+1}^{1}) = n+1+i, \quad \psi_{2}(c^{1}x_{i}^{1}) = 2n+2+i,\]
For \(1 \le i \le n + j\)
\[\psi_2(c^j) = \psi_2(x_i^j) = \psi_2(y_i^j) = \min \left\{ \left[ \frac{3\sum_{s=1}^{j-1} (n+s+2)}{2} \right], k \right\} \text{ for } 2 \le j \le m.\]
• For \[2 \le j \le m\] such that \[\left[ \frac{3\sum_{s=1}^{j-1} (n+s) + 2}{2} \right] < k\]
(i) When \[\sum_{s=1}^{j-1} (n+s) \equiv 0 \pmod{2}\]
\(\psi_2(x_i^j y_i^j) = i, \quad \psi_2(x_i^j x_{i+1}^j) = n+j+i, \quad \psi_2(c^j x_i^j) = 2n+2j+i,\)
(ii) When \[\sum_{s=1}^{j-1} (n+s) \equiv 1 \pmod{2}\]
\(\psi_2\left(x_i^j y_i^j\right) = 1+i, \quad \psi_2\left(x_i^j x_{i+1}^j\right) = 1+n+j+i, \quad \psi_2\left(c^j x_i^j\right) = 1+2n+2j+i,\)
• For \[2 \le j \le m\] such that \(\left| \frac{3\sum_{s=1}^{j-1} (n+s) + 2}{2} \right| \ge k\)
Let
\[w = \min \left\{ j; \ 2 \le j \le m \text{ such that } \left| \frac{3\sum_{s=1}^{j-1} (n+s) + 2}{2} \right| \ge k \right\}\]
\[\psi_{2}\left(x_{i}^{j}y_{i}^{j}\right) = \begin{cases} 3\sum_{s=1}^{w-1}(n+s) - 2k + i, & if \quad j = w\\ 3\sum_{s=1}^{w-1}(n+s) - 2k + i + 3n + 3j - 1, & if \quad w+1 \le j \le m \end{cases}\]
\[\psi_{2}\left(x_{i}^{j}x_{i+1}^{j}\right) = \begin{cases} 3\sum_{s=1}^{w-1}(n+s) - 2k + 2 + n + w + i, & if \quad j = w \\ 3\sum_{s=1}^{w-1}(n+s) - 2k + i + 4n + 2j + w, & if \quad w+1 \le j \le m \end{cases}\] \[\psi_{2}\left(c^{j}x_{i}^{j}\right) = \begin{cases} 3\sum_{s=1}^{w-1}(n+s) - 2k + 2 + 2n + 2w + i, & if \quad j = w \\ 3\sum_{s=1}^{w-1}(n+s) - 2k + i + 5n + j + 2w + 1, & if \quad w+1 \le j \le m \end{cases}\]
\[\psi_{2}\left(c^{j}x_{i}^{j}\right) = \begin{cases} 3\sum_{s=1}^{w-1} (n+s) - 2k + 2 + 2n + 2w + i, & if \quad j = w \\ 3\sum_{s=1}^{w-1} (n+s) - 2k + i + 5n + j + 2w + 1, & if \quad w+1 \le j \le m \end{cases}\]
Under the labeling \(\psi_2\), the total weights of the edges are described as follows:
- The edges \(x_i^1 y_i^1\), \(x_i^1 x_{i+1}^1\) and \(c^1 x_i^1\) for \(1 \le i \le n+1\) receive consecutive integers from the interval [3,3+n], [4+n,2n+4] and [2n+5,3n+5], respectively.
- (ii) The edges \(x_i^j y_i^j\) for \(1 \le i \le n+j, 2 \le j \le m\) receive consecutive integers from the interval \(3\sum_{s=1}^{j-1} (n+s) + 3\), \(3\sum_{s=1}^{j-1} (n+s) + n + j + 2\),
- (iii) The edges \(x_i^j x_{i+1}^j\) for \(1 \le i \le n+j, 2 \le j \le m\) receive consecutive integers from the interval \(\left[ 3 \sum_{s=1}^{j-1} (n+s) + n + j + 3, 3 \sum_{s=1}^{j-1} (n+s) + 2n + 2j + 2 \right]\),
(iv) The edges \(c^j x_i^j\) for \(1 \le i \le n+j\), \(2 \le j \le m\) receive consecutive integers from the interval \(\left[3\sum_{s=1}^{j-1}(n+s)+2n+2j+3, 3\sum_{s=1}^{j}(n+s)+2\right]\),
It is not difficult to see that all vertex and edge labels are at most k and the edge-weights of the edges \(c^i x_i^j\), \(x_i^j y_i^j\) and \(x_i^j x_{i+1}^j\) are pairwise distinct. Thus, the resulting labeling is a total edge irregular k-labeling. This concludes the proof.
3 Conclusion
In this paper, we have determined the exact value of the total edge irregularity strength of the disjoint union of m copies of a helm graph as well as the disjoint union of non-isomorphic helm graphs \(\bigcup_{j=1}^{m} H_{n+j}\). We conclude by stating the following open problem:
Open Problem. For \(m \ge 2\) find the exact value of the total edge irregularity strength of a disjoint union of m arbitrary helm graphs.
Acknowledgements
The authors wish to thank the anonymous referee for his/her valuable comments.