1 Introduction
In 2007, Bača, et al. [1] introduced vertex irregular total k-labelings and edge irregular total k-labelings. A total labeling \(f: V \cup E \to \{1, 2, \dots, k\}\) is called a vertex irregular total k-labeling of G if every two distinct vertices X and Y in Y satisfy \(W_f(X) \neq W_f(Y)\), where \(W_f(X) = f(X) + \sum_{XZ \in E(G)} f(XZ)\). The minimum K for which a graph G has a vertex irregular total K-labeling, denoted by tvs(G), is called the vertex irregularity strength of G.
Bača, et al. [1] proved that for any graph G = (V, E),
\[\left|\frac{|V(G)| + \delta(G)}{\Delta(G) + 1}\right| \le tvs(G) \le |V(G)| + \Delta(G) - 2\delta(G) + 1. \tag{1}\]
Another result about tvs(G) was given by Nurdin, \(et\ al.\) in [2] as follows:
\[tvs(G) \ge \max\left\{ \left[ \frac{\delta + n_{\delta}}{\delta + 1} \right], \left[ \frac{\delta + n_{\delta} + n_{\delta + 1}}{\delta + 2} \right], \cdots, \left[ \frac{\delta + \sum_{i=\delta}^{\Delta} n_i}{\Delta + 1} \right] \right\}, \tag{2}\] where \(n_i\) denotes the number of vertices of degree \(i, i = \delta, \delta + 1, \dots, \Delta\).
In [3], Majerski and Przybylo gave the best result for dense graphs so far. In [4], Anholcer, Kalkowski and Przybylo gave the best known result for general graphs. Some other results about vertex irregular total k-labeling were given by Nurdin, et al. in [5] and [6], and Wijaya, et al. in [7] and [8].
A total labeling \(f: V \cup E \to \{1, 2, \dots, k\}\) is called an edge irregular total k-labeling of G if every two distinct edges \(x_1x_2\) and \(y_1y_2\) in E satisfy \(w_f(x_1x_2) \neq w_f(y_1y_2)\), where \(w_f(x_1x_2) = f(x_1) + f(x_1x_2) + f(x_2)\). The minimum k for which a graph G has an edge irregular total k-labeling, denoted by tes(G), is called the edge irregularity strength of G.
In [1], Bača, et al. derived a lower and an upper bounds on the total edge irregularity strength of any graph G = (V, E) as follows:
\[\left\lceil \frac{|E(G)|+2}{3} \right\rceil \le tes(G) \le |E(G)|. \tag{3}\]
Ivančo and Jendrol in [9] proved that
\[tes(T) = \max\left\{ \left\lceil \frac{|E(T)| + 2}{3} \right\rceil, \left\lceil \frac{\Delta(T) + 1}{2} \right\rceil \right\},\tag{4}\] where T is a tree.
In [10], Nurdin, et al. determined the total edge irregularity strength of the corona product of a path with some graphs, which are a path, a cycle, a star, a gear, a friendship graph, and a wheel.
Some other results about edge irregular total k-labelings were given by Bača and Siddiqui in [11], Jendroľ, Miškuf, and Soták in [12] and [13], and Miškuf and Jendroľ in [14].
Combining vertex irregular total k-labelings and edge irregular total k-labelings, Marzuki, Salman, and Miller, in [15], introduced a new irregular total k-labeling of a graph G. It is called 'totally irregular total k-labelings', which is required to be at the same time both vertex and edge irregular. The minimum k for which a graph G has a totally irregular total k-labeling, denoted by ts(G), is called the total irregularity strength of G.
In the same paper, Marzuki, et al. gave a lower bound on ts(G) and exact values of the total irregularity strength of cycles and paths as follows:
For every graph G,
\[ts(G) \ge \max\{tes(G), tvs(G)\},\tag{5}\]
\[ts(\mathcal{C}_n) = \left[\frac{n+2}{3}\right] \text{ for } n \ge 3,\tag{6}\]
\[ts(P_n) = \begin{cases} \left\lceil \frac{n+2}{3} \right\rceil & \text{for } n = 2 \text{ or } n = 5; \\ \left\lceil \frac{n+1}{3} \right\rceil & \text{otherwise.} \end{cases}\] (7)
In [16], Ramdani and Salman determined the total irregularity strength of some Cartesian product graphs. One of some results in the paper is given as follows:
\[ts(C_n \square P_2) = n + 1 \text{ for } n \ge 3.\] (8)
2 Main Results
A totally irregular total k-labeling f of G is called an optimal labeling of G if ts(G) = k. In the following theorem, we derive an upper bound on the total irregularity strength of m copies of a regular graph.
Theorem 2.1 Let G be an r-regular connected graph with \(r \ge 1\). Then,
\[ts(mG) \le m(ts(G)) - \left| \frac{m-1}{2} \right|.\]
Proof. Let G = (V, E) be an r-regular graph with order n, ts(G) = t, and f be an optimal labeling of G. Then, \(|E| = \frac{nr}{2}\). Let mG be m copies of G where the copies of G are denoted by \(G_i\) for \(1 \le i \le m\). Let \(V(G) = \{v_1, v_2, \cdots, v_n\}\), \(E(G) = \left\{e_1, e_2, \cdots, e_{\frac{nr}{2}}\right\}\), \(V(G_i) = \left\{v_1^i, v_2^i, \cdots, v_n^i\right\}\), and \(E(G_i) = \left\{e_1^i, e_2^i, \cdots, e_{\frac{nr}{2}}^i\right\}\), where \(G_i\) is isomorphic with G with the isomorphism
\[s: V(G) \cup E(G) \rightarrow V(G_i) \cup E(G_i)\] where
\[s(v_a) = v_a^i\] and \(s(e_x) = e_x^i\)
for every \(1 \le i \le m\), \(1 \le a \le n\), and \(1 \le x \le \frac{nr}{2}\).
Define a total labeling g of mG as follows:
• For i odd.
1) \[g(v_a^i) = f(v_a) + (i-1)t - (\frac{i-1}{2});\]
2) \[g(e_x^i) = f(e_x) + (i-1)t - (\frac{i-1}{2});\]
• For i even, 1) \[g(v_a^i) = f(v_a) + (i-1)t - (\frac{i}{2});\]
2) \(g(e_x^i) = f(e_x) + (i-1)t - (\frac{i}{2}) + 1;\)
for every \(1 \le i \le m\), \(1 \le a \le n\), and \(1 \le x \le \frac{nr}{2}\).
Next, it will be shown that in the labeling g, there are no two edges of the same weight and there are no two vertices of the same weight.
1. It will be shown that there are no two edges in \(G_i\) with the same weight for every \(i, 1 \le i \le m\).
Let \(e_x^i = v_a^i v_b^i\) be an edge in \(G_i\) for \(1 \le i \le m\). We consider two cases.
• Case 1: For i odd,
\[\begin{split} w_g \Big( e_x^i \Big) &= g \Big( v_a^i \Big) + g \Big( e_x^i \Big) + g \Big( v_b^i \Big) \\ &= f(v_a) + (i-1)t - \Big( \frac{i-1}{2} \Big) + f(e_x) + (i-1)t - \Big( \frac{i-1}{2} \Big) \\ &+ f(v_b) + (i-1)t - \Big( \frac{i-1}{2} \Big) \\ &= f(v_a) + f(e_x) + f(v_b) + 3 \left( (i-1)t - \Big( \frac{i-1}{2} \Big) \right) \\ &= w_f(e_x) + 3 \left( (i-1)t - \Big( \frac{i-1}{2} \Big) \right). \end{split}\]
• Case 2: For i even,
\(x \neq y, 1 \leq i \leq m\), and \(x, y \in \left\{1, 2, \dots, \frac{nr}{2}\right\}\).
\[\begin{aligned} w_g(e_x^i) &= g(v_a^i) + g(v_x^i) + g(v_b^i) \\ &= f(v_a) + (i-1)t - \left(\frac{i}{2}\right) + f(e_x) + (i-1)t - \left(\frac{i}{2}\right) + 1 \\ &+ f(v_b) + (i-1)t - \left(\frac{i}{2}\right) \\ &= f(v_a) + f(e_x) + f(v_b) + 3\left((i-1)t - \left(\frac{i}{2}\right)\right) + 1 \\ &= w_f(e_x) + 3\left((i-1)t - \left(\frac{i}{2}\right)\right) + 1. \end{aligned}\] Since \(w_f(e_x) \neq w_f(e_y)\) for every \(x \neq y\), \(3\left((i-1)t - \left(\frac{i-1}{2}\right)\right)\) and \(3\left((i-1)t - \left(\frac{i}{2}\right)\right) + 1\) are constants, we get \(w_g(e_x^i) \neq w_g(e_y^i)\) for every
2. Define j = i + 1 for \(1 \le i \le m\). It will be shown that \(w_g(e_x^i) < w_g(e_y^j)\) for all edges \(e_x^i \in G_i\) and \(e_y^j \in G_j\) for \(x, y \in \{1, 2, \dots, \frac{nr}{2}\}\).
Let \(e_x^i = v_a^i v_b^i\) and \(e_y^j = v_c^j v_d^j\). We consider two cases.
• Case 1 : For i odd,
\[w_{g}(e_{x}^{i}) = g(v_{a}^{i}) + g(e_{x}^{i}) + g(v_{b}^{i})\] \[= f(v_{a}) + f(e_{x}) + f(v_{b}) + 3\left((i-1)t - \left(\frac{i-1}{2}\right)\right)\] \[\leq 3t + 3\left((i-1)t - \left(\frac{i-1}{2}\right)\right)\] \[= 3it - 3\left(\frac{i-1}{2}\right).\] (9)
On the other hand,
\[w_{g}(e_{y}^{j}) = f(v_{c}) + f(e_{y}) + f(v_{d}) + 3\left((j-1)t - \left(\frac{j}{2}\right)\right) + 1\] \[\geq 3 + 3\left((j-1)t - \left(\frac{j}{2}\right)\right) + 1\] \[= 3 + 3\left(it - \left(\frac{i+1}{2}\right)\right) + 1\] \[> 3it - 3\left(\frac{i-1}{2}\right).\] (10)
From (9) and (10), it follows \(w_g(e_y^j) > w_g(e_x^i)\).
• Case 2 : For i even,
\[w_{g}(e_{x}^{i}) = g(v_{a}^{i}) + g(e_{x}^{i}) + g(v_{b}^{i})\] \[= f(v_{a}) + f(e_{x}) + f(v_{b}) + 3\left((i-1)t - \left(\frac{i}{2}\right)\right) + 1\] \[\leq 3t + 3\left((i-1)t - \left(\frac{i}{2}\right)\right) + 1\] \[= 3it - 3\left(\frac{i}{2}\right) + 1.\] (11)
On the other hand,
\[w_{g}(e_{y}^{j}) = f(v_{c}) + f(e_{y}) + f(v_{d}) + 3\left((j-1)t - \left(\frac{j-1}{2}\right)\right)\] \[\geq 3 + 3\left((j-1)t - \left(\frac{j-1}{2}\right)\right)\] \[= 3 + 3\left(it - \left(\frac{i}{2}\right)\right)\] \[> 3it - 3\left(\frac{i}{2}\right) + 1.\] (12)
From (11) and (12), we have \(w_g(e_y^j) > w_g(e_x^i)\).
Hence, \(w_g(e_u^p) \neq w_g(e_w^q)\) for all edges \(e_u^p \in G_p\) and \(e_w^q \in G_q\) with \(p \neq q\), \(p,q \in \{1,2,\cdots,m\}\), and \(u,w \in \{1,2,\cdots,\frac{nr}{2}\}\).
1. It will be shown that there are no two vertices in \(G_i\) with the same weight for every \(i, 1 \le i \le m\).
Let \(v_a^i\) be a vertex in \(G_i\) for \(1 \le i \le m\). Let the edges incident with \(v_a^i\) be \(e_{a_1}^i, e_{a_2}^i, \cdots, e_{a_r}^i\). We consider two cases.
• Case 1 : For i odd,
\[\begin{split} w_g \big( v_a^i \big) &= f(v_a) + (i-1)t - \Big( \frac{i-1}{2} \Big) \\ &+ \sum_{s=1}^r \Big( f \Big( e_{a_s} \Big) + (i-1)t - \Big( \frac{i-1}{2} \Big) \Big) \\ &= f(v_a) + \sum_{s=1}^r f \Big( e_{a_s} \Big) + (r+1) \left( (i-1)t - \Big( \frac{i-1}{2} \Big) \right) \\ &= w_f(v_a) + (r+1) \left( (i-1)t - \Big( \frac{i-1}{2} \Big) \right). \end{split}\]
• Case 2 : For i even,
\[\begin{split} w_g \big( v_a^i \big) &= f(v_a) + (i-1)t - \left( \frac{i}{2} \right) \\ &+ \sum_{s=1}^r \left( f \big( e_{a_s} \big) + (i-1)t - \left( \frac{i}{2} \right) + 1 \right) \\ &= f(v_a) + \sum_{s=1}^r f \big( e_{a_s} \big) + (r+1) \left( (i-1)t - \left( \frac{i}{2} \right) \right) + r \\ &= w_f(v_a) + (r+1) \left( (i-1)t - \left( \frac{i}{2} \right) \right) + r. \end{split}\]
Since \(w_f(v_a) \neq w_f(v_b)\) for every \(a \neq b\), \((r+1)\left((i-1)t - \left(\frac{i-1}{2}\right)\right)\) and \((r+1)\left((i-1)t - \left(\frac{i}{2}\right)\right) + r\) are constants, we get \(w_g(v_a^i) \neq w_g(v_b^i)\) for every \(a \neq b, 1 \leq i \leq m\), and \(a, b \in \{1, 2, \dots, n\}\).
2. Define j = i + 1 for \(1 \le i \le m\). It will be shown that \(w_g(v_a^i) < w_g(v_b^j)\) for all vertices \(v_a^i \in G_i\) and \(v_b^j \in G_i\) for \(a, b \in \{1, 2, \dots, n\}\).
Let the edges incident with \(v_a^i\) be \(e_{a_1}^i, e_{a_2}^i, \cdots, e_{a_r}^i\) and the edges incident with \(v_b^j\) be \(e_{b_1}^j, e_{b_2}^j, \cdots, e_{b_r}^j\). We consider two cases.
• Case 1 : For i odd,
\[w_{g}(v_{a}^{i}) = f(v_{a}) + \sum_{s=1}^{r} f(e_{a_{s}}) + (r+1)\left((i-1)t - \left(\frac{i-1}{2}\right)\right)\] \[\leq (r+1)t + (r+1)\left((i-1)t - \left(\frac{i-1}{2}\right)\right)\] \[= (r+1)it - (r+1)\left(\frac{i-1}{2}\right).\] (13)
On the other hand,
\[w_{g}(v_{b}^{j}) = f(v_{b}) + \sum_{s=1}^{r} f(e_{b_{s}}) + (r+1)\left((j-1)t - \left(\frac{j}{2}\right)\right) + r\] \[\geq (r+1) + (r+1)\left((j-1)t - \left(\frac{j}{2}\right)\right) + r\] \[= (r+1) + (r+1)\left(it - \left(\frac{i+1}{2}\right)\right) + r\] \[= (r+1) + (r+1)\left(it - \left(\frac{i-1}{2}\right) - 1\right) + r\] \[> (r+1)it - (r+1)\left(\frac{i-1}{2}\right). \tag{14}\]
From (13) and (14), we obtain \(w_q(v_b^j) > w_q(v_a^i)\).
• Case 2 : For i even,
\[w_{g}(v_{a}^{i}) = f(v_{a}) + \sum_{s=1}^{r} f(e_{a_{s}}) + (r+1)\left((i-1)t - \left(\frac{i}{2}\right)\right) + r\] \[\leq (r+1)t + (r+1)\left((i-1)t - \left(\frac{i}{2}\right)\right) + r\] \[= (r+1)it - (r+1)\left(\frac{i}{2}\right) + r.\] (15)
Moreover,
\[w_{g}(v_{b}^{j}) = f(v_{b}) + \sum_{s=1}^{r} f(e_{b_{s}}) + (r+1)\left((j-1)t - \left(\frac{j-1}{2}\right)\right)\] \[\geq (r+1) + (r+1)\left(it - \left(\frac{i}{2}\right)\right)\] \[> (r+1)it - (r+1)\left(\frac{i}{2}\right) + r.\] (16)
From (15) and (16), we obtain \(w_g(v_b^j) > w_g(v_a^i)\).
Hence, \(w_g(v_u^p) \neq w_g(v_w^q)\) for all vertices \(v_u^p \in G_p\) and \(v_w^q \in G_q\) with \(p \neq q\), \(p, q \in \{1, 2, \dots, m\}\), and \(u, w \in \{1, 2, \dots, n\}\).
It can easily be seen that the maximum label of g is not greater than \(t+(m-1)t-\left|\frac{m-1}{2}\right|=mt-\left|\frac{m-1}{2}\right|\).
Since there are no two edges of the same weight and there are no two vertices of the same weight in mG, g is a totally irregular total \(\left(mt - \left\lfloor \frac{m-1}{2} \right\rfloor\right)\) —labeling of mG. We can conclude that
\[ts(mG) \le m(ts(G)) - \left\lfloor \frac{m-1}{2} \right\rfloor.\]
The upper bound in Theorem 2.1 can be decreased for some graphs.
Theorem 2.2 Let G be an r-regular connected graph with \(r \ge 1\). Let f be an optimal labeling of G such that \(w_f(e) < 3ts(G)\) for every \(e \in E(G)\) and \(w_f(v) < (r+1)ts(G)\) for every \(v \in V(G)\). Then,
\[ts(mG) \le m(ts(G) - 1) + 1.\]
Proof. Let G = (V, E) be an r-regular graph with order n, ts(G) = t, and f be an optimal labeling of G. Then, \(|E| = \frac{nr}{2}\). Let mG be m copies of G where the copies of G are denoted by \(G_i\) for \(1 \le i \le m\). Let \(G(G) = \{v_1, v_2, \cdots, v_n\}\), \(E(G) = \{e_1, e_2, \cdots, e_{\frac{nr}{2}}\}\), \(V(G_i) = \{v_1^i, v_2^i, \cdots, v_n^i\}\), and \(E(G_i) = \{e_1^i, e_2^i, \cdots, e_{\frac{nr}{2}}^i\}\), where \(G_i\) is isomorphic with G with the isomorphism
\[s: V(G) \cup E(G) \rightarrow V(G_i) \cup E(G_i)\], where \(s(v_a) = v_a^i\) and \(s(e_x) = e_x^i\) for every \(1 \le i \le m\), \(1 \le a \le n\), and \(1 \le x \le \frac{nr}{2}\).
Define a total labeling g of mG as follows:
1) \[g(v_a^i) = f(v_a) + (i-1)(t-1);\]
2) \[g(e_x^i) = f(e_x) + (i-1)(t-1);\]
for every \(1 \le i \le m\), \(1 \le a \le n\), and \(1 \le x \le \frac{nr}{2}\).
Next, it will be shown that in the labeling g, there are no two edges of the same weight and there are no two vertices of the same weight.
1. It will be shown that there are no two edges in \(G_i\) with the same weight for every \(i, 1 \le i \le m\).
Let \(e_x^i = v_a^i v_b^i\) be an edge in \(G_i\) for \(1 \le i \le m\). Then,
\[\begin{array}{lll} w_g \big( e_x^i \big) & = & g \big( v_a^i \big) + g \big( e_x^i \big) + g \big( v_b^i \big) \\ & = & f(v_a) + (i-1)(t-1) + f(e_x) + (i-1)(t-1) \\ & & + f(v_b) + (i-1)(t-1) \\ & = & f(v_a) + f(e_x) + f(v_b) + 3(i-1)(t-1) \\ & = & w_f(e_x) + 3(i-1)(t-1). \end{array}\]
Since \(w_f(e_x) \neq w_f(e_y)\) for every \(x \neq y\) and 3(i-1)(t-1) is a constant, \(w_g(e_x^i) \neq w_g(e_y^i)\) for every \(x \neq y\), \(1 \leq i \leq m\), and \(x, y \in \{1, 2, \dots, \frac{nr}{2}\}\).
2. Define j = i + 1 for \(1 \le i \le m\). Let \(e_x^i = v_a^i v_b^i\) and \(e_y^j = v_c^j v_d^j\). Then,
\[w_g(e_x^i) = f(v_a) + f(e_x) + f(v_b) + 3(i-1)(t-1)\] \[< 3t + 3(i-1)(t-1)\] \[= 3i(t-1) + 3.\] (17)
On the other hand,
\[w_g(e_y^j) = f(v_c) + f(e_y) + f(v_d) + 3(j-1)(t-1)\] \[\geq 3 + 3(j-1)(t-1)\] \[= 3 + 3i(t-1)\] (18)
From (17) and (18), \(w_g(e_y^j) > w_g(e_x^i)\).
Hence, \(w_g(e_u^p) \neq w_g(e_w^q)\) for all edges \(e_u^p \in G_p\) and \(e_w^q \in G_q\) with \(p \neq q\), \(p, q \in \{1, 2, \dots, m\}\), and \(u, w \in \{1, 2, \dots, \frac{nr}{2}\}\).
1. It will be shown that there are no two vertices in \(G_i\) with the same weight for every \(i, 1 \le i \le m\).
Let \(v_a^i\) be a vertex in \(G_i\) for \(1 \le i \le m\). Let the edges incident with \(v_a^i\) be \(e_{a_1}^i, e_{a_2}^i, \cdots, e_{a_r}^i\). Then,
\[w_g(v_a^i) = f(v_a) + (i-1)(t-1) + \sum_{s=1}^r (f(e_{a_s}) + (i-1)(t-1)) = f(v_a) + \sum_{s=1}^r f(e_{a_s}) + (r+1)(i-1)(t-1) = w_f(v_a) + (r+1)(i-1)(t-1).\]
Since \(w_f(v_a) \neq w_f(v_b)\) for every \(a \neq b\) and (r+1)(i-1)(t-1) is a constant, \(w_g(v_a^i) \neq w_g(v_b^i)\) for every \(a \neq b\), \(1 \leq i \leq m\), and \(a, b \in \{1, 2, \dots, n\}\).
2. It will be shown that \(w_g(v_u^p) \neq w_g(v_w^q)\) for all vertices \(v_u^p \in G_p\) and \(v_w^q \in G_q\) with \(p \neq q, p, q \in \{1, 2, \cdots, m\}\), and \(u, w \in \{1, 2, \cdots, n\}\).
Define j=i+1 for \(1\leq i\leq m\). Let the edges incident with \(v_a^i\) be \(e_{a_1}^i,e_{a_2}^i,\cdots,e_{a_r}^i\) and the edges incident with \(v_b^j\) be \(e_{b_1}^j,e_{b_2}^j,\cdots,e_{b_r}^j\). Then,
\[w_g(v_a^i) = w_f(v_a) + (r+1)(i-1)(t-1)\] \[< (r+1)t + (r+1)(i-1)(t-1)\] \[= (r+1)(t-1)i + (r+1).\] (19)
Also,
\[w_g(v_b^j) = w_f(v_a) + (r+1)(j-1)(t-1)\] \[\geq (r+1) + (r+1)(t-1)i\] (20)
From (19) and (20), \(w_g(v_b^j) > w_g(v_a^i)\). Hence, the claim follows.
It can easily be seen that the maximum label of g is t + (m-1)(t-1) = m(t-1) + 1.
Since there are no two edges of the same weight and there are no two vertices of the same weight in mG, g is a totally irregular total (m(t-1)+1)-labeling of mG. We can conclude that
\[ts(mG) \leq m(ts(G) - 1) + 1.\]
In the third theorem, we determine a dual labeling of a totally irregular total k-labeling of arbitrary regular graph.
Definition 2.1 Let G be an r-regular graph. Let f be an optimal labeling of G. The dual labeling of f, denoted by \(\hat{f}\), is defined by
\[\hat{f}(v) = ts(G) + 1 - f(v), \forall v \in V(G)\] and
\[\hat{f}(e) = ts(G) + 1 - f(e), \forall e \in E(G).\]
Theorem 2.3. Let be an -regular graph. Let be an optimal labeling of . Then, ̂ is an also optimal labeling of .
Proof. It will be shown that in the labeling ̂, there are no two edges of the same weight and there are no two vertices of the same weight.
Let = and = be different edges in (). Then,
\[\begin{array}{rcl} w_{\hat{f}}(c) & = & \hat{f}(u_i) + \hat{f}(c) + \hat{f}(v_i) \\ & = & ts(G) + 1 - f(u_i) + ts(G) + 1 - f(c) + ts(G) + 1 - f(v_i) \\ & = & 3(ts(G) + 1) - \left(f(u_i) + f(c) + f(v_i)\right) \\ & = & 3(ts(G) + 1) - w_f(c). \end{array}\]
Also,
\[w_{\hat{f}}(d) = \hat{f}(u_{j}) + \hat{f}(d) + \hat{f}(v_{j})\] \[= ts(G) + 1 - f(u_{j}) + ts(G) + 1 - f(d) + ts(G) + 1 - f(v_{j})\] \[= 3(ts(G) + 1) - (f(u_{j}) + f(d) + f(v_{j}))\] \[= 3(ts(G) + 1) - w_{f}(d).\]
Since () ≠ () for every ≠ and 3(() + 1) is a constant, ̂() ≠ ̂().
Let and be different vertices in . Let the edges incident with be 1, 2, ⋯ , and the edges incident with be 1, 2, ⋯ , . Then,
\[\begin{split} w_{\hat{f}}(v_a) &= \hat{f}(v_a) + \sum_{s=1}^r \hat{f}(e_{a_s}) \\ &= ts(G) + 1 - f(v_a) + r(ts(G) + 1) - \sum_{s=1}^r f(e_{a_s}) \\ &= (r+1)(ts(G) + 1) - (f(v_a) + \sum_{s=1}^r f(e_{a_s})) \\ &= (r+1)(ts(G) + 1) - w_f(v_a). \end{split}\]
On the other hand,
\[\begin{split} w_{\hat{f}}(v_b) &= \hat{f}(v_b) + \sum_{s=1}^r \hat{f}(e_{b_s}) \\ &= ts(G) + 1 - f(v_b) + r(ts(G) + 1) - \sum_{s=1}^r f(e_{b_s}) \\ &= (r+1)(ts(G) + 1) - (f(v_b) + \sum_{s=1}^r f(e_{b_s})) \\ &= (r+1)(ts(G) + 1) - w_f(v_b). \end{split}\]
Since \(w_f(v_a) \neq w_f(v_b)\) for every \(v_a \neq v_b\) and (r+1)(ts(G)+1) is a constant, \(w_f(v_a) \neq w_f(v_b)\).
Therefore, in the labeling \(\hat{f}\), there are no two edges of the same weight and there are no two vertices of the same weight. Moreover, the maximum label of \(\hat{f}\) is less than or equal ts(G). We can conclude that \(\hat{f}\) is an optimal labeling of G.
Three last theorems in this paper consider the total irregularity strength of a 1-regular graph, a 2-regular graph, and a 3-regular graph.
Theorem 2.4 Let \(P_2\) be a path with 2 vertices. Then, \(ts(mP_2) = m + 1\) for \(m \ge 1\).
Proof. The graph \(mP_2\) has 2m vertices and m edges and is 1-regular graph. From (1) and (3), we get \(tvs(mP_2) \ge \left\lceil \frac{2m+1}{2} \right\rceil = m+1\) and \(tes(mP_2) \ge \left\lceil \frac{m+2}{3} \right\rceil\). Therefore, from (5), we get \(ts(mP_2) \ge m+1\). Besides that, from (7) we get \(ts(P_2) = 2\).
Let the vertex set of \(P_2\) be \(\{v_1, v_2\}\). Given a totally irregular total 2-labeling f of \(P_2\) as follows:
\[f(v_i) = i \text{ for } 1 \le i \le 2; f(v_1 v_2) = 1.\]
It can be seen that f is an optimal labeling of \(P_2\) such that \(w_f(v_1v_2) < 3(ts(P_2))\) and \(w_f(v) < 2(ts(P_2))\) for every \(v \in V(P_2)\). Therefore, from Theorem 2.2, we get
\[ts(mP_2) \le m(ts(P_2) - 1) + 1\]
= \(m(2 - 1) + 1\)
= \(m + 1\).
We conclude that \(ts(mP_2) = m + 1\).
Theorem 2.5. Let \(C_n\) be a cycle of order n. For \(n \ge 3\) and \(n \equiv 0 \mod 3\), \(ts(mC_n) = \left\lceil \frac{mn+2}{3} \right\rceil\).
Proof. The \(mC_n\) has mn vertices and mn edges and is 2-regular. From (1), (3), and (5), we get
\[ts(mC_n) \ge \left\lceil \frac{mn+2}{3} \right\rceil. \tag{21}\]
Next, we will prove that \(ts(mC_n) \leq \left[\frac{mn+2}{3}\right]\).
Let the disconnected graph \(C_n\) consists of the vertex set and edge set as follows:
- \(V(C_n) = \{v_i | 1 \le i \le n\};\)
- \(E(C_n) = \{e_i = v_i v_{i+1} | 1 \le i \le n\};\)
where the subscript n + 1 is replaced by 1.
From (6), we get \[ts(C_n) = \left[\frac{n+2}{3}\right]\].
Given a totally irregular total \(\left\lceil \frac{n+2}{3} \right\rceil\)-labeling f of \(C_n\) for \(n \equiv 0 \mod 3\) as follows:
\[f(v_i) = \begin{cases} \left\lceil \frac{i}{3} \right\rceil + \left\lfloor \frac{i}{3} \right\rceil & \text{for } 1 \le i \le \left\lceil \frac{n}{2} \right\rceil + 1; \\ \left\lceil \frac{n-i+1}{3} \right\rceil + \left\lfloor \frac{n-i+1}{3} \right\rfloor + 1 & \text{for } \left\lceil \frac{n}{2} \right\rceil + 2 \le i \le n; \end{cases}\] \[f(e_i) = \begin{cases} \left\lceil \frac{i}{3} \right\rceil + \left\lfloor \frac{i+1}{3} \right\rceil & \text{for } 1 \le i \le \left\lfloor \frac{n}{2} \right\rfloor + 1; \\ \left\lceil \frac{n-i}{3} \right\rceil + \left\lfloor \frac{n-i+1}{3} \right\rfloor + 1 & \text{for } \left\lfloor \frac{n}{2} \right\rfloor + 2 \le i \le n. \end{cases}\]
The labeling gives the weight of vertices and the weight of edges of \(C_n\) as follows:
\[w_f(v_i) = \begin{cases} 3 \text{ for } i = 1; \\ 2i \text{ for } 2 \le i \le \left\lfloor \frac{n}{2} \right\rfloor + 1; \\ 2(n-i) + 5 \text{ for } \left\lfloor \frac{n}{2} \right\rfloor + 2 \le i \le n; \end{cases}\] \[w_f(e_i) = \begin{cases} 2i + 1 \text{ for } 1 \le i \le \left\lceil \frac{n}{2} \right\rceil; \\ 2(n-i) + 4 \text{ for } \left\lceil \frac{n}{2} \right\rceil + 1 \le i \le n. \end{cases}\]
Hence, there are no two vertices of the same weight and there are no two edges of the same weight. Moreover, it can be seen \(w_f(e) < 3(ts(C_n))\) for every \(e \in E(C_n)\) and \(w_f(v) < 3(ts(C_n))\) for every \(v \in V(P_2)\). Therefore, from Theorem 2.2, we get
\[ts(mC_n) \leq m(ts(C_n) - 1) + 1\] \[= m\left(\left\lceil \frac{n+2}{3} \right\rceil - 1\right) + 1\] \[= m\left(\frac{n}{3} + 1 - 1\right) + 1\] \[= m\left(\frac{n}{3}\right) + 1\] \[= \left\lceil \frac{mn+2}{3} \right\rceil.\] (22)
From (21) and (22), we conclude that \(ts(mC_n) = \left\lceil \frac{mn+2}{3} \right\rceil\) for \(n \equiv 0 \mod 3\).
Theorem 2.6 For \(n \ge 3\), \(ts(m(C_n \square P_2)) = mn + 1\).
Proof. The graph \(m(C_n \Box P_2)\) has 2mn vertices and 3mn edges and is 3-regular. From (1) and (3), we get \(tvs(m(C_n \Box P_2)) \ge \left\lceil \frac{2mn+3}{4} \right\rceil\) and \(tes(m(C_n \Box P_2)) \ge mn+1\). Therefore, from (5), \(ts(m(C_n \Box P_2)) \ge nm+1\). Moreover, from (8), \(ts(C_n \Box P_2) = n+1\).
In [14], Ramdani and Salman gave an optimal labeling f of \(C_n \square P_2\) such that \(w_f(e) < 3(ts(C_n \square P_2))\) for every \(e \in E(C_n \square P_2)\) and \(w_f(v) < 4(ts(C_n \square P_2))\) for every \(v \in V(C_n \square P_2)\). Therefore, from Theorem 2.2, we get
\[ts(m(C_n \square P_2)) \leq m(ts(C_n \square P_2) - 1) + 1\] \[= m(n+1-1) + 1\] \[= mn+1.\]
We conclude that \(ts(m(C_n \square P_2)) = mn + 1\).