Total irregularity strength for product of two paths

Abstract

In this paper we define a totally irregular total labeling for Cartesian and strong product of two paths, which is at the same time vertex irregular total labeling and also edge irregular total labeling. More preciously, we determine the exact value of the total irregularity strength for Cartesian and strong product of two paths.

Keywords:

• Total edge irregularity strength
• Total vertex irregularity strength
• Total irregularity strength
• Cartesian product
• Strong product

1 Introduction

For a graph $G$ we define a labeling $\zeta :V\cup E\to \{1,2,\dots ,k\}$ to be total $k$-labeling. A total $k$-labeling is defined to be an edge irregular total $k-$labeling of the graph $G$ if for each two distinct edges $rs$ and $r^{\prime }{s}^{\prime }$ their weights $\varphi \left(r\right)+\varphi \left(rs\right)+\varphi \left(s\right)$ and $\varphi \left(r^{\prime }\right)+\varphi \left(r^{\prime }{s}^{\prime }\right)+\varphi \left(s^{\prime }\right)$ are distinct. Also total $k$-labeling is defined to be a vertex irregular total $k$-labeling of the graph $G$ if for each two distinctive vertices $r$ and $s$ their weights $wt\left(r\right)$ and $wt\left(s\right)$ are distinct. Here, the weight of a vertex $r$ in $G$ is the sum of the label of $r$ and the labels of all edges incident with the vertex $r$. The least $k$ for which the graph $G$ has an edge irregular total $k-$labeling is called the total irregularity strength of $G$, represented by $tes\left(G\right)$. Analogously, the minimum $k$ for which the graph $G$ has a vertex irregular total $k-$labeling is called the total vertex irregularity strength of $G$, denoted by $tvs\left(G\right)$. A total labeling $\psi :V\cup E\to \{1,2,\dots ,k\}$ is called totally irregular total $k$-labeling of $G$ if every two distinct vertices $a$ and $b$ satisfy $wt\left(a\right)\ne wt\left(b\right),$ and every two distinct edges $a_1{a}_2$ and $b_1{b}_2$ in $E\left(G\right)$ satisfy $wt\left(a_1{a}_2\right)\ne wt\left(b_1{b}_2\right).$ The minimum $k$ for which a graph $G$ has a totally irregular total $k$-labeling is called the total irregularity strength of $G$, denoted by $ts\left(G\right).$

In [1] Chartrand et al. introduced two graph invariants namely irregular assignments and the irregularity strength. In [2] Baca et al. modified these graph invariants and introduced the concept of total edge irregularity strength, total vertex irregularity strength for a graph $G$ and proved the following theorems.

Theorem 1.1

[2] Let $G$ be a finite graph with $p$ vertices, $q$ edges and having maximum degree $\Delta =\Delta \left(G\right)$. Then $$\mathrm{tes}\left(G\right)\ge max\left\{⌈\frac{q+2}{3}⌉,⌈\frac{\Delta +1}{2}⌉\right\}.$$

Theorem 1.2

[2] Let $G$ be a finite graph with $p$ vertices, $q$ edges, minimum degree $\delta =\delta \left(G\right)$ and maximum degree $\Delta =\Delta \left(G\right)$. Then $$\lceil \frac{p+\delta }{\Delta +1}\rceil \le tvs\left(G\right)\le p+\Delta -2\delta +1.$$

In [3] Ivančo and Jendroľ posed the following conjecture:

Conjecture 1

[3] Let $G$ be a finite graph with $p$ vertices, $q$ edges, minimum degree $\delta =\delta \left(G\right)$, maximum degree $\Delta =\Delta \left(G\right)$ and different from $K_5$. Then $$\mathrm{tes}\left(G\right)=max\left\{⌈\frac{q+2}{3}⌉,⌈\frac{\Delta +1}{2}⌉\right\}.$$In [4] Nurdin et al. posed the following conjecture:

Conjecture 2

[4] Let $G$ be a connected graph having $n_i$ vertices of degree $i(i=\delta ,\delta +1,\delta +2,\dots ,\Delta )$, where $\delta$ and $\Delta$ are the minimum and the maximum degree of $G$ respectively. Then $$tvs\left(G\right)=max\left\{\lceil \frac{\delta +n_{\delta }}{\delta +1}\rceil ,\lceil \frac{\delta +n_{\delta }+n_{\delta +1}}{\delta +2}\rceil ,\dots ,\lceil \frac{\delta +\sum _{i=\delta }^{\Delta }{n}_i}{\Delta +1}\rceil \right\}.$$

Conjecture 1 has been verified for trees [3], for complete graphs and complete bipartite graphs [5,6], for hexagonal grid graphs [7] , for toroidal grid [8], for generalized prism [9], for strong product of cycles and paths [10], for categorical product of two cycles [11], for zigzag graphs [12] and for strong product of two paths [13]. For more results see [14–18].

Conjecture 2 has been verified for trees [4], for Cartesian and strong product of two paths in [19].

Combining both total edge irregularity strength and total vertex irregularity strength notions, Marzuki et al. [20] introduced a new irregular total $k$-labeling of a graph $G$, which is required to be at the same time both vertex and edge irregular. The minimum value of $k$ for which such labeling exist is called total irregularity strength of graph and is denoted by $ts\left(G\right)$. Besides that, they determined the total irregularity strength of cycles and paths. Marzuki, et al. [20] have given a lower bond of $ts\left(G\right)$ as follows. (1) $$\text{For every graph G},ts\left(G\right)\ge max\{tes\left(G\right),tvs\left(G\right)\}.$$(1) Ramdani and Salman [21] showed that the lower bound in (1) for some Cartesian product graphs is tight. In [22], Ahmad et al. found the exact value of total irregularity strength of generalized Petersen graph.

In the present paper, we determine the exact value of the total irregularity strength for Cartesian and strong product of two paths.

2 Total irregularity strength for Cartesian product of two paths

A Cartesian product $H_1\square H_2$ of two graphs $H_1$ and H2 is the graph with the vertex set $V\left(H_1\right)\times V\left(H_2\right)$ and the vertex $(a,b)$ is adjacent to the vertex $(c,d)$ if and only if $a=c$ and $b$ is adjacent to $d$ or $b=d$ and $a$ is adjacent to $c$.

In [21] Ramdani and Salman found the exact value of $ts(P_2\square P_n)$. In the next theorem we determine the exact value of total irregularity strength of $P_3\square P_n$.

Theorem 2.1

Let $n\ge 7$. Then $ts(P_3\square P_n)=\lceil \frac{5n-1}{3}\rceil .$

Proof

Let $P_3=(x_1,x_2,x_3)$ and $P_n=(y_1,y_2,\dots ,y_n)$. Let $G=P_3\square P_n$. Clearly $\left|V\left(G\right)\right|=3n$ and $\left|E\left(G\right)\right|=5n-3$. It follows from Theorems 1.1 and 1.2 that $tes\left(G\right)\ge \lceil \frac{2n-1}{3}\rceil$ and $tvs\left(G\right)\ge \lceil \frac{3n+2}{5}\rceil$. From Eq. (1) we get $ts\left(G\right)\ge \lceil \frac{5n-1}{3}\rceil$. Now let $k=\lceil \frac{5n-1}{3}\rceil$. To prove the reverse inequality we define $\varphi :V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,k\}$ as follows. $$\varphi (x_1,y_i)=1,\varphi (x_3,y_i)=k,\text{for}1\le i\le n,$$For $1\le i\le n-1$ $\varphi \left((x_1,y_i)(x_1,y_{i+1})\right)=i$,

Case 1. $n\equiv 0\left(mod6\right).$

$\varphi (x_2,y_i)=n$, $\varphi \left((x_1,y_i)(x_2,y_i)\right)=n+1-i$, $\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=k-i$, $$\varphi \left((x_2,y_i)(x_3,y_i)\right)=\left\{\begin{array}{cc}\frac{n}{3},\hfill & \mathit{for}i=1\hfill \\ \frac{n}{3}+i,\hfill & \mathit{for}2\le i\le n\hfill \end{array}\right.$$ $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}n+1,\hfill & \mathit{for}i=1\hfill \\ n+1-i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by:

$wt\left((x_1,y_i)(x_2,y_i)\right)=2n+2-i$, $wt\left((x_1,y_i)(x_1,y_{i+1})\right)=2+i$, $wt\left((x_3,y_i)(x_3,y_{i+1})\right)=3k-i$, $$wt\left((x_2,y_i)(x_3,y_i)\right)=\left\{\begin{array}{cc}k+\frac{4n}{3},\hfill & \mathit{for}i=1\hfill \\ k+\frac{4n}{3}+i,\hfill & \mathit{for}2\le i\le n\hfill \end{array}\right.$$ $$wt(x_1,y_i)=\left\{\begin{array}{cc}n+1+i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ n+1,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{10n}{3}+1,\hfill & \mathit{for}i=1\hfill \\ \frac{13n}{3}+1,\hfill & \mathit{for}i=2\hfill \\ \frac{13n}{3}+4-2i,\hfill & \mathit{for}3\le i\le n-1\hfill \\ \frac{7n}{3}+3,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{11n}{3}-1,\hfill & \mathit{for}i=1\hfill \\ \frac{16n}{3}+1-i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{11n}{3}+1,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}3n+1,\hfill & \mathit{for}i=1\hfill \\ 3n+1-i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$

Case 2. $n\equiv 1\left(mod6\right).$

$\varphi (x_2,y_i)=n$, $\varphi \left((x_1,y_i)(x_2,y_i)\right)=n+1-i$, $$\varphi \left((x_2,y_i)(x_3,y_i)\right)=\left\{\begin{array}{cc}\frac{n-1}{3}+i,\hfill & \mathit{for}1\le i\le n-2\hfill \\ \frac{4n-1}{3},\hfill & \mathit{for}i=n-1\hfill \\ \frac{4n-4}{3},\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}n-1,\hfill & \mathit{for}i=1\hfill \\ n,\hfill & \mathit{for}i=2\hfill \\ n+1-i,\hfill & \mathit{for}3\le i\le n-1\hfill \end{array}\right.$$ $$\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=\left\{\begin{array}{cc}k,\hfill & \mathit{for}i=1\hfill \\ k-i,\hfill & \mathit{for}2\le i\le n-3\hfill \\ k-1-i,\hfill & \mathit{for}n-2\le i\le n-1.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by:

$wt\left((x_1,y_i)(x_2,y_i)\right)=2n+2-i$, $wt\left((x_1,y_i)(x_1,y_{i+1})\right)=2+i$, $$wt\left((x_2,y_i)(x_3,y_i)\right)=\left\{\begin{array}{cc}k+\frac{4n-1}{3}+i,\hfill & \mathit{for}1\le i\le n-2\hfill \\ k+\frac{7n-1}{3},\hfill & \mathit{for}i=n-1\hfill \\ k+\frac{7n-4}{3},\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_1,y_i)=\left\{\begin{array}{cc}n+1+i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ n+1,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{10(n-1)}{3}+3,\hfill & \mathit{for}i=1\hfill \\ \frac{13(n-1)}{3}+6-i,\hfill & \mathit{for}2\le i\le 3\hfill \\ \frac{13(n-1)}{3}+8-2i,\hfill & \mathit{for}4\le i\le n-2\hfill \\ \frac{7(n-1)}{3}+9,\hfill & \mathit{for}i=n-1\hfill \\ \frac{7(n-1)}{3}+4,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{11(n-1)}{3}+5,\hfill & \mathit{for}i=1\hfill \\ \frac{16(n-1)}{3}+6,\hfill & \mathit{for}i=2\hfill \\ \frac{16(n-1)}{3}+7-i,\hfill & \mathit{for}3\le i\le n-3\hfill \\ \frac{16n-13}{3}+5-i,\hfill & \mathit{for}n-2\le i\le n-1\hfill \\ \frac{11(n-1)}{3}+3,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}3n-1,\hfill & \mathit{for}i=1\hfill \\ 3n,\hfill & \mathit{for}i=2\hfill \\ 3n+1-i,\hfill & \mathit{for}3\le i\le n-1\hfill \end{array}\right.$$ $$wt\left((x_3,y_i)(x_3,y_{i+1})\right)=\left\{\begin{array}{cc}3k,\hfill & \mathit{for}i=1\hfill \\ 3k-i,\hfill & \mathit{for}2\le i\le n-3\hfill \\ 3k-1-i,\hfill & \mathit{for}n-2\le i\le n-1.\hfill \end{array}\right.$$

Case 3. $n\equiv 2,5\left(mod6\right).$

$\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=k+1-i$, $$\varphi (x_2,y_i)=\left\{\begin{array}{cc}n+2,\hfill & \mathit{for}i=1\hfill \\ n,\hfill & \mathit{for}2\le i\le n-1\hfill \\ n-1,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$\varphi \left((x_1,y_i)(x_2,y_i)\right)=\left\{\begin{array}{cc}n-2,\hfill & \mathit{for}i=1\hfill \\ n+1-i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ 2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$\varphi \left((x_2,y_i)(x_3,y_i)\right)=\left\{\begin{array}{cc}\frac{n-2}{3},\hfill & \mathit{for}i=1\hfill \\ \frac{n-2}{3}+1+i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{4(n-2)}{3}+4,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}n-3,\hfill & \mathit{for}i=1\hfill \\ n,\hfill & \mathit{for}i=2\hfill \\ n+1-i,\hfill & \mathit{for}3\le i\le n-2\hfill \\ 3,\hfill & \mathit{for}i=n-1.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by:

$wt\left((x_1,y_i)(x_2,y_i)\right)=2n+2-i$, $wt\left((x_2,y_i)(x_3,y_i)\right)=3n+i$, $wt\left((x_1,y_i)(x_1,y_{i+1})\right)=2+i$, $wt\left((x_3,y_i)(x_3,y_{i+1})\right)=3k+1-i$, $$wt(x_1,y_i)=\left\{\begin{array}{cc}n,\hfill & \mathit{for}i=1\hfill \\ n+1+i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ n+2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{10(n-2)}{3}+3,\hfill & \mathit{for}i=1\hfill \\ \frac{13(n-2)}{3}+5+i,\hfill & \mathit{for}2\le i\le 3\hfill \\ \frac{13(n-2)}{3}+13-2i,\hfill & \mathit{for}4\le i\le n-2\hfill \\ \frac{13n-20}{3}+12-2i,\hfill & \mathit{for}n-1\le i\le n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{11(n-2)}{3}+6,\hfill & \mathit{for}i=1\hfill \\ \frac{16(n-2)}{3}+13-i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{11(n-2)}{3}+10,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}3n-1,\hfill & \mathit{for}i=1\hfill \\ 3n,\hfill & \mathit{for}i=2\hfill \\ 3n+1-i,\hfill & \mathit{for}3\le i\le n-1.\hfill \end{array}\right.$$

Case 4. $n\equiv 3\left(mod6\right).$

$\varphi (x_2,y_i)=n$, $\varphi \left((x_1,y_i)(x_2,y_i)\right)=n+1-i$, $\varphi \left((x_2,y_i)(x_3,y_i)\right)=\frac{n}{3}+i$, $\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=k+1-i$, $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}n-1,\hfill & \mathit{for}i=1\hfill \\ n,\hfill & \mathit{for}i=2\hfill \\ n+1-i,\hfill & \mathit{for}3\le i\le n-1.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by:

$wt\left((x_1,y_i)(x_2,y_i)\right)=2n+2-i$, $wt\left((x_2,y_i)(x_3,y_i)\right)=k+\frac{4n}{3}+i$, $wt\left((x_1,y_i)(x_1,y_{i+1})\right)=2+i$, $wt\left((x_3,y_i)(x_3,y_{i+1})\right)=3k+1-i$, $$wt(x_1,y_i)=\left\{\begin{array}{cc}n+1+i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ n+1,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{10n}{3},\hfill & \mathit{for}i=1\hfill \\ \frac{13n}{3}+2-i,\hfill & \mathit{for}2\le i\le 3\hfill \\ \frac{13n}{3}+4-2i,\hfill & \mathit{for}4\le i\le n-1\hfill \\ \frac{7n}{3}+3,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{11n}{3}+1,\hfill & \mathit{for}i=1\hfill \\ \frac{16n}{3}+3-i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{11n}{3}+2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}3n-1,\hfill & \mathit{for}i=1\hfill \\ 3n,\hfill & \mathit{for}i=2\hfill \\ 3n+1-i,\hfill & \mathit{for}3\le i\le n-1.\hfill \end{array}\right.$$

Case 5. $n\equiv 4\left(mod6\right).$

$\varphi (x_2,y_i)=n$, $\varphi \left((x_1,y_i)(x_2,y_i)\right)=n+1-i$, $\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=n+1-i$, $$\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=\left\{\begin{array}{cc}k,\hfill & \mathit{for}i=1\hfill \\ k-i,\hfill & \mathit{for}2\le i\le n-3\hfill \\ k-1-i,\hfill & \mathit{for}n-2\le i\le n-1\hfill \end{array}\right.$$ $$\varphi \left((x_2,y_i)(x_3,y_i)\right)=\left\{\begin{array}{cc}\frac{n-1}{3}+i,\hfill & \mathit{for}1\le i\le n-2\hfill \\ \frac{4n-1}{3},\hfill & \mathit{for}i=n-1\hfill \\ \frac{4n-4}{3},\hfill & \mathit{for}i=n.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by:

$wt\left((x_1,y_i)(x_2,y_i)\right)=2n+2-i$, $wt\left((x_2,y_i)(x_2,y_{i+1})\right)=3n+1-i$, $wt\left((x_1,y_i)(x_1,y_{i+1})\right)=2+i$, $$wt\left((x_2,y_i)(x_3,y_i)\right)=\left\{\begin{array}{cc}k+\frac{4n-1}{3}+i,\hfill & \mathit{for}1\le i\le n-2\hfill \\ k+\frac{7n-1}{3},\hfill & \mathit{for}i=n-1\hfill \\ k+\frac{7n-4}{3},\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_1,y_i)=\left\{\begin{array}{cc}n+1+i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ n+1,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{10(n-1)}{3}+4,\hfill & \mathit{for}i=1\hfill \\ \frac{13(n-1)}{3}+8-2i,\hfill & \mathit{for}2\le i\le n-2\hfill \\ \frac{7(n-1)}{3}+9,\hfill & \mathit{for}i=n-1\hfill \\ \frac{7(n-1)}{3}+4,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{11(n-1)}{3}+5,\hfill & \mathit{for}i=1\hfill \\ \frac{16(n-1)}{3}+6,\hfill & \mathit{for}i=2\hfill \\ \frac{16(n-1)}{3}+7-i,\hfill & \mathit{for}3\le i\le n-3\hfill \\ \frac{16n-13}{3}+5-i,\hfill & \mathit{for}n-2\le i\le n-1\hfill \\ \frac{11(n-1)}{3}+3,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_3,y_i)(x_3,y_{i+1})\right)=\left\{\begin{array}{cc}3k,\hfill & \mathit{for}i=1\hfill \\ 3k-i,\hfill & \mathit{for}2\le i\le n-3\hfill \\ 3k-1-i,\hfill & \mathit{for}n-2\le i\le n-1.\hfill \end{array}\right.$$It is easy to check that there are no two edges of the same weight and there are no two vertices of the same weight. So $\varphi$ is a totally irregular total $k-$labeling. We conclude that $ts(P_3\square P_n)=\lceil \frac{7n-1}{3}\rceil$. This completes the proof.

Theorem 2.2

Let $n\ge 6$. Then $ts(P_4\square P_n)=\lceil \frac{7n-2}{3}\rceil .$

Proof

Let $P_4=(x_1,x_2,x_3,x_4)$ and $P_n=(y_1,y_2,\dots ,y_n)$. Let $G=P_4\square P_n$. Clearly $\left|V\left(G\right)\right|=4n$ and $\left|E\left(G\right)\right|=7n-4$. It follows from Theorems 1.1 and 1.2 that $tes\left(G\right)\ge \lceil \frac{7n-2}{3}\rceil$ and $tvs\left(G\right)\ge \lceil \frac{4n+2}{5}\rceil$. From Eq. (1) we get $ts\left(G\right)\ge \lceil \frac{7n-2}{3}\rceil$. Now let $k=\lceil \frac{7n-2}{3}\rceil$. To prove the reverse inequality we define $\varphi :V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,k\}$ as follows.

$\varphi (x_1,y_i)=i$, $wt\left((x_2,y_i)(x_3,y_i)\right)=3n+i$, $wt\left((x_3,y_i)(x_4,y_i)\right)=5n-2+2i$, $$\varphi \left((x_1,y_i)(x_2,y_i)\right)=\left\{\begin{array}{cc}1,\hfill & \mathit{for}1\le i\le n-1\hfill \\ 2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_1,y_i)=\left\{\begin{array}{cc}3,\hfill & \mathit{for}i=1\hfill \\ 3+i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ n+3,\hfill & \mathit{for}i=n.\hfill \end{array}\right.$$For $1\le i\le n-1$ $$\varphi \left((x_1,y_i)(x_1,y_{i+1})\right)=1,wt\left((x_1,y_i)(x_1,y_{i+1})\right)=2+2i,wt\left((x_3,y_i)(x_3,y_{i+1})\right)=4n+i.$$

Case 1. $n\equiv 0\left(mod6\right).$

$\varphi (x_2,y_i)=i$, $\varphi (x_3,y_i)=k-n+i$, $\varphi (x_4,y_i)=k-n+i$, $\varphi \left((x_2,y_i)(x_3,y_i)\right)=\frac{5n}{3}-i$, $\varphi \left((x_3,y_i)(x_4,y_i)\right)=k-2$, $\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=\frac{4n}{3}-1-i$, $\varphi \left((x_4,y_i)(x_4,y_{i+1})\right)=k-2$, $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n-2,\hfill & \mathit{for}i=1\hfill \\ 2n-i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by:

$wt\left((x_4,y_i)(x_4,y_{i+1})\right)=5n-1+2i$, $$wt\left((x_1,y_i)(x_2,y_i)\right)=\left\{\begin{array}{cc}1+2i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ 2n+2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{11n}{3}-1,\hfill & \mathit{for}i=1\hfill \\ \frac{17n}{3}-3,\hfill & \mathit{for}i=2\hfill \\ \frac{17n}{3}+2-2i,\hfill & \mathit{for}3\le i\le n-1\hfill \\ \frac{8n}{3}+3,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{20n}{3}-4,\hfill & \mathit{for}i=1\hfill \\ \frac{24n}{3}-3-2i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{17n}{3}-2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_4,y_i)=\left\{\begin{array}{cc}\frac{18n}{3}-3,\hfill & \mathit{for}i=1\hfill \\ \frac{25n}{3}-6+i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{21n}{3}-4,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n+1,\hfill & \mathit{for}i=1\hfill \\ 2n+1+i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$

Case 2. $n\equiv 1\left(mod6\right).$

$\varphi (x_2,y_i)=i$, $\varphi (x_3,y_i)=k-n+i$, $\varphi (x_4,y_i)=k-n+i$, $\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=\frac{4(n-1)}{3}+1-i$, $\varphi \left((x_3,y_i)(x_4,y_i)\right)=k-1$, $\varphi \left((x_2,y_i)(x_3,y_i)\right)=\frac{5(n-1)}{3}+2-i$, $\varphi \left((x_4,y_i)(x_4,y_{i+1})\right)=k-1$, $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n-2,\hfill & \mathit{for}i=1\hfill \\ 2n-i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by:

$wt\left((x_4,y_i)(x_4,y_{i+1})\right)=5n-1+2i$, $$wt\left((x_1,y_i)(x_2,y_i)\right)=\left\{\begin{array}{cc}1+2i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ 2n+2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{11(n-1)}{3}+3,\hfill & \mathit{for}i=1\hfill \\ \frac{17(n-1)}{3}+3,\hfill & \mathit{for}i=2\hfill \\ \frac{17(n-1)}{3}+8-2i,\hfill & \mathit{for}3\le i\le n-1\hfill \\ \frac{8(n-1)}{3}+6,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{20(n-1)}{3}+4,\hfill & \mathit{for}i=1\hfill \\ \frac{24(n-1)}{3}+7-2i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{17(n-1)}{3}+5,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_4,y_i)=\left\{\begin{array}{cc}\frac{18(n-1)}{3}+4,\hfill & \mathit{for}i=1\hfill \\ \frac{25(n-1)}{3}+4+i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{21(n-1)}{3}+4,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n+1,\hfill & \mathit{for}i=1\hfill \\ 2n+1+i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$

Case 3. $n\equiv 2\left(mod6\right).$

$\varphi (x_2,y_i)=i$, $\varphi (x_3,y_i)=k-n+i$, $\varphi (x_4,y_i)=k-n+i$, $\varphi \left((x_2,y_i)(x_3,y_i)\right)=\frac{5(n-2)}{3}+4-i$, $\varphi \left((x_3,y_i)(x_4,y_i)\right)=k$, $\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=\frac{4(n-2)}{3}+3-i$, $\varphi \left((x_4,y_i)(x_4,y_{i+1})\right)=k$, $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n-2,\hfill & \mathit{for}i=1\hfill \\ 2n-i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by:

$wt\left((x_4,y_i)(x_4,y_{i+1})\right)=5n-1+2i$, $$wt\left((x_1,y_i)(x_2,y_i)\right)=\left\{\begin{array}{cc}1+2i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ 2n+2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{11(n-2)}{3}+7,\hfill & \mathit{for}i=1\hfill \\ \frac{17(n-2)}{3}+9,\hfill & \mathit{for}i=2\hfill \\ \frac{17(n-2)}{3}+14-2i,\hfill & \mathit{for}3\le i\le n-1\hfill \\ \frac{8(n-2)}{3}+9,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{20(n-2)}{3}+12,\hfill & \mathit{for}i=1\hfill \\ \frac{24(n-2)}{3}+17-2i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{17(n-2)}{3}+12,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_4,y_i)=\left\{\begin{array}{cc}\frac{18(n-2)}{3}+11,\hfill & \mathit{for}i=1\hfill \\ \frac{25(n-2)}{3}+14+i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{21(n-2)}{3}+12,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n+1,\hfill & \mathit{for}i=1\hfill \\ 2n+1+i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$

Case 4. $n\equiv 3\left(mod6\right).$

$\varphi (x_2,y_i)=i$, $\varphi (x_3,y_i)=k-n+i$, $\varphi (x_4,y_i)=k-n+i$, $\varphi \left((x_2,y_i)(x_3,y_i)\right)=\frac{5(n-3)}{3}+5-i$, $\varphi \left((x_3,y_i)(x_4,y_i)\right)=k-2$, $\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=\frac{4(n-3)}{3}+3-i$, $$\varphi \left((x_4,y_i)(x_4,y_{i+1})\right)=\left\{\begin{array}{cc}k-2,\hfill & \mathit{for}1\le i\le n-2\hfill \\ k-1,\hfill & \mathit{for}i=n-1\hfill \end{array}\right.$$ $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n-2,\hfill & \mathit{for}i=1\hfill \\ 2n-i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by: $$wt\left((x_1,y_i)(x_2,y_i)\right)=\left\{\begin{array}{cc}1+2i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ 2n+2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{11(n-3)}{3}+10,\hfill & \mathit{for}i=1\hfill \\ \frac{17(n-3)}{3}+14,\hfill & \mathit{for}i=2\hfill \\ \frac{17(n-3)}{3}+19-2i,\hfill & \mathit{for}3\le i\le n-1\hfill \\ \frac{8(n-3)}{3}+10,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{20(n-3)}{3}+16,\hfill & \mathit{for}i=1\hfill \\ \frac{24(n-3)}{3}+21-2i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{17(n-3)}{3}+15,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_4,y_i)=\left\{\begin{array}{cc}\frac{18(n-3)}{3}+15,\hfill & \mathit{for}i=1\hfill \\ \frac{25(n-3)}{3}+19+i,\hfill & \mathit{for}2\le i\le n-2\hfill \\ \frac{28(n-3)}{3}+22,\hfill & \mathit{for}i=n-1\hfill \\ \frac{21(n-3)}{3}+18,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n+1,\hfill & \mathit{for}i=1\hfill \\ 2n+1+i,\hfill & \mathit{for}2\le i\le n-1\hfill \end{array}\right.$$ $$wt\left((x_4,y_i)(x_4,y_{i+1})\right)=\left\{\begin{array}{cc}5n-1+2i,\hfill & \mathit{for}1\le i\le n-2\hfill \\ 3k-2,\hfill & \mathit{for}i=n-1.\hfill \end{array}\right.$$

Case 5. $n\equiv 4\left(mod6\right).$

$\varphi (x_2,y_i)=i$, $\varphi (x_3,y_i)=k-n+i$, $\varphi (x_4,y_i)=k-n+i$, $\varphi \left((x_2,y_i)(x_3,y_i)\right)=\frac{5(n-4)}{3}+7-i$, $\varphi \left((x_3,y_i)(x_4,y_i)\right)=k-1$, $\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=\frac{4(n-4)}{3}+5-i$, $$\varphi \left((x_4,y_i)(x_4,y_{i+1})\right)=\left\{\begin{array}{cc}k-1,\hfill & \mathit{for}1\le i\le n-2\hfill \\ k,\hfill & \mathit{for}i=n-1\hfill \end{array}\right.$$ $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n-2,\hfill & \mathit{for}i=1\hfill \\ 2n-i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$

In this case the weights of the edges and the vertices are given by: $$wt\left((x_1,y_i)(x_2,y_i)\right)=\left\{\begin{array}{cc}1+2i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ 2n+2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{11(n-4)}{3}+14,\hfill & \mathit{for}i=1\hfill \\ \frac{17(n-4)}{3}+20,\hfill & \mathit{for}i=2\hfill \\ \frac{17(n-4)}{3}+25-2i,\hfill & \mathit{for}3\le i\le n-1\hfill \\ \frac{8(n-4)}{3}+14,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{20(n-4)}{3}+24,\hfill & \mathit{for}i=1\hfill \\ \frac{24(n-4)}{3}+31-2i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ \frac{17(n-4)}{3}+22,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_4,y_i)=\left\{\begin{array}{cc}\frac{18(n-4)}{3}+22,\hfill & \mathit{for}i=1\hfill \\ \frac{25(n-4)}{3}+29+i,\hfill & \mathit{for}2\le i\le n-2\hfill \\ \frac{28(n-4)}{3}+33,\hfill & \mathit{for}i=n-1\hfill \\ \frac{21(n-4)}{3}+26,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_4,y_i)(x_4,y_{i+1})\right)=\left\{\begin{array}{cc}5n-1+2i,\hfill & \mathit{for}1\le i\le n-2\hfill \\ 3k-1,\hfill & \mathit{for}i=n-1\hfill \end{array}\right.$$ $$wt\left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n+1,\hfill & \mathit{for}i=1\hfill \\ 2n+1+i,\hfill & \mathit{for}2\le i\le n-1.\hfill \end{array}\right.$$

Case 6. When $n\equiv 5\left(mod6\right).$ $$\varphi (x_2,y_i)=\left\{\begin{array}{cc}i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ n-1,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$\varphi (x_3,y_i)=\left\{\begin{array}{cc}k-n+1+i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ k,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$\varphi (x_4,y_i)=\left\{\begin{array}{cc}k-n+1+i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ k,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$\varphi \left((x_2,y_i)(x_3,y_i)\right)=\left\{\begin{array}{cc}\frac{5(n-5)}{3}+8-i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ \frac{2(n-5)}{3}+5,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$\varphi \left((x_3,y_i)(x_4,y_i)\right)=\left\{\begin{array}{cc}k-2,\hfill & \mathit{for}1\le i\le n-1\hfill \\ k,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=\left\{\begin{array}{cc}\frac{4(n-5)}{3}+5-i,\hfill & \mathit{for}1\le i\le n-2\hfill \\ \frac{n-5}{3}+2,\hfill & \mathit{for}i=n-1\hfill \end{array}\right.$$ $$\varphi \left((x_4,y_i)(x_4,y_{i+1})\right)=\left\{\begin{array}{cc}k-2,\hfill & \mathit{for}1\le i\le n-2\hfill \\ k-1,\hfill & \mathit{for}i=n-1\hfill \end{array}\right.$$ $$\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=\left\{\begin{array}{cc}2n-1,\hfill & \mathit{for}i=1\hfill \\ 2n-i,\hfill & \mathit{for}2\le i\le n-2\hfill \\ n+2,\hfill & \mathit{for}i=n-11.\hfill \end{array}\right.$$ In this case the weights of the edges and the vertices are given by:

$wt\left((x_1,y_i)(x_2,y_i)\right)=1+2i$, $wt\left((x_2,y_i)(x_2,y_{i+1})\right)=2n+1+i$, $wt\left((x_4,y_i)(x_4,y_{i+1})\right)=5n-1+2i$, $$wt(x_2,y_i)=\left\{\begin{array}{cc}\frac{11(n-5)}{3}+18,\hfill & \mathit{for}i=1\hfill \\ \frac{17(n-5)}{3}+30-2i,\hfill & \mathit{for}2\le i\le n-2\hfill \\ \frac{11(n-5)}{3}+23,\hfill & \mathit{for}i=n-1\hfill \\ \frac{8(n-5)}{3}+18,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}\frac{20(n-5)}{3}+28,\hfill & \mathit{for}i=1\hfill \\ \frac{24(n-5)}{3}+35-2i,\hfill & \mathit{for}2\le i\le n-2\hfill \\ \frac{18(n-5)}{3}+28,\hfill & \mathit{for}i=n-1\hfill \\ \frac{17(n-5)}{3}+29,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_4,y_i)=\left\{\begin{array}{cc}\frac{18(n-5)}{3}+26,\hfill & \mathit{for}i=1\hfill \\ \frac{25(n-5)}{3}+34+i,\hfill & \mathit{for}2\le i\le n-2\hfill \\ \frac{28(n-5)}{3}+39,\hfill & \mathit{for}i=n-1\hfill \\ \frac{21(n-5)}{3}+32,\hfill & \mathit{for}i=n.\hfill \end{array}\right.$$

It is easy to check that there are no two edges of the same weight and there are no two vertices of the same weight. So $\varphi$ is a totally irregular total $k-$labeling. We conclude that $ts(P_4\square P_n)=\lceil \frac{7n-2}{3}\rceil$. This completes the proof.

3 Total irregularity strength for strong product of two paths

The strong product $G_1⊠G_2$ of graphs $G_1$ and $G_2$ has as vertices the pairs $(a,b)$ where $a\in V\left(G_1\right)$ and $b\in V\left(G_2\right)$. Moreover vertices $(a_1,b_1)$ and $(a_2,b_2)$ are adjacent if either $a_1{a}_2$ is an edge of $G_1$ and $b_1=b_2$ or if $b_1{b}_2$ is an edge of $G_2$ and $a_1=a_2$ or if $a_1{a}_2$ is an edge of $G_1$ and $b_1{b}_2$ is an edge of $G_2$. In the next theorem we determined the exact value of total irregularity strength of $P_3⊠P_n$.

Theorem 3.1

Let $n\ge 6$. Then $ts(P_3⊠P_n)=\lceil \frac{9n-5}{3}\rceil .$

Proof

Let $P_4=(x_1,x_2,x_3)$ and $P_n=(y_1,y_2,\dots ,y_n)$. Let $G=P_3⊠P_n$. Clearly $\left|V\left(G\right)\right|=3n$ and $\left|E\left(G\right)\right|=9n-7$. It follows from Theorems 1.1 and 1.2 that $tes\left(G\right)\ge \lceil \frac{9n-5}{3}\rceil$ and $tvs\left(G\right)\ge \lceil \frac{2n+5}{6}\rceil$. From Eq. (1) we get $ts\left(G\right)\ge \lceil \frac{9n-5}{3}\rceil$. Now let $k=\lceil \frac{9n-5}{3}\rceil$. To prove the reverse inequality we define $\varphi :V\left(G\right)\cup E\left(G\right)\to \{1,2,\dots ,k\}$ as follows.

$\varphi (x_1,y_i)=1$, $\varphi (x_2,y_i)=n-1+i$, $\varphi (x_3,y_i)=k$, $\varphi \left((x_1,y_i)(x_2,y_i)\right)=1$, $\varphi \left((x_2,y_i)(x_3,y_i)\right)=1$, $\varphi \left((x_2,y_i)(x_1,y_{i+1})\right)=n+1$, $\varphi \left((x_1,y_i)(x_2,y_{i+1})\right)=2n-1$, $\varphi \left((x_2,y_i)(x_2,y_{i+1})\right)=3n-i$, $\varphi \left((x_2,y_i)(x_3,y_{i+1})\right)=2n$, $\varphi \left((x_3,y_i)(x_2,y_{i+1})\right)=3n-2$, $$\varphi \left((x_1,y_i)(x_1,y_{i+1})\right)=\left\{\begin{array}{cc}i,\hfill & \mathit{for}1\le i\le n-3\hfill \\ n-1,\hfill & \mathit{for}i=n-2\hfill \\ n-2,\hfill & \mathit{for}i=n-1\hfill \end{array}\right.$$ $$\varphi \left((x_3,y_i)(x_3,y_{i+1})\right)=\left\{\begin{array}{cc}2n-2+i,\hfill & \mathit{for}1\le i\le n-1\hfill \\ k-1,\hfill & \mathit{for}i=n.\hfill \end{array}\right.$$In this case the weights of the edges and the vertices are given by:

$wt\left((x_1,y_i)(x_2,y_i)\right)=n+1+i$, $wt\left((x_2,y_i)(x_3,y_i)\right)=4n-1+i$, $wt\left((x_1,y_i)(x_2,y_{i+1})\right)=3n+i$, $wt\left((x_2,y_i)(x_1,y_{i+1})\right)=2n+1+i$, $wt\left((x_2,y_i)(x_2,y_{i+1})\right)=5n-1+i$, $wt\left((x_2,y_i)(x_3,y_{i+1})\right)=k+3n-1+i$, $wt\left((x_3,y_i)(x_2,y_{i+1})\right)=k+4n-2+i$, $$wt(x_1,y_i)=\left\{\begin{array}{cc}2n+2,\hfill & \mathit{for}i=1\hfill \\ 3n+1+2i,\hfill & \mathit{for}2\le i\le n-3\hfill \\ 4n+i,\hfill & \mathit{for}i=n-2,n-1\hfill \\ 2n+1,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_2,y_i)=\left\{\begin{array}{cc}7n+2,\hfill & \mathit{for}i=1\hfill \\ 15n-i,\hfill & \mathit{for}2\le i\le n-1\hfill \\ 9n-1,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt(x_3,y_i)=\left\{\begin{array}{cc}8n-3,\hfill & \mathit{for}i=1\hfill \\ 12n-7+2i,\hfill & \mathit{for}2\le i\le n-2\hfill \\ 14n-8,\hfill & \mathit{for}i=n-1\hfill \\ 8n-2,\hfill & \mathit{for}i=n\hfill \end{array}\right.$$ $$wt\left((x_1,y_i)(x_1,y_{i+1})\right)=\left\{\begin{array}{cc}2+i,\hfill & \mathit{for}1\le i\le n-3\hfill \\ n+1,\hfill & \mathit{for}i=n-2\hfill \\ n,\hfill & \mathit{for}i=n-1\hfill \end{array}\right.$$ $$wt\left((x_3,y_i)(x_3,y_{i+1})\right)=\left\{\begin{array}{cc}2k+2n-2+i,\hfill & \mathit{for}1\le i\le n-2\hfill \\ 3k-1,\hfill & \mathit{for}i=n-1.\hfill \end{array}\right.$$It is easy to check that there are no two edges of the same weight and there are no two vertices of the same weight. So $\varphi$ is a totally irregular total $k$-labeling. We conclude that $ts(P_3⊠P_n)=\lceil \frac{9n-5}{3}\rceil$. This completes the proof.

Conclusion:

In this paper we determined the exact value of the totally irregularity strength for $P_3\square P_n$, $P_4\square P_n$ and $P_3⊠P_n$. We conclude the paper with following open problems.

Open Problem 3.2

Determine the exact value of totally irregularity strength for $P_m\square P_n$, $ifn\ge 3\text{and}m\ge 5$.

Open Problem 3.3

Determine the exact value of totally irregularity strength for $P_m⊠P_n$, $ifn\ge 3\text{and}m\ge 4$.

Acknowledgments

The authors are grateful to the anonymous referees for their valuable comments and suggestions that improved this paper.

This research is supported by the Start-Up Research Grant 2016 of United Arab Emirates University (UAEU), Al Ain, United Arab Emirates via Grant No. G00002233, UPAR Grant of UAEU via Grant No. G00002590 and by the Summer Undergraduate Research Experience (SURE) plus 2017 research Grant via Grant No. G00002412.