Muhammad Irfan^a , Martin Bacaˇ ∗b , Andrea Semanicov ˇ a-Fe ´ nov ˇ cˇ´ıkova´ b

m.irfan.assms@gmail.com, martin.baca@tuke.sk, andrea.fenovcikova@tuke.sk

Let G be a connected, simple and undirected graph. The assignments {0, 2, . . . , 2kv} to the vertices and {1, 2, . . . , ke} to the edges of graph G are called total k-labelings, where k = max{ke, 2kv}. The total k-labeling is called an reflexive edge irregular k-labeling of the graph G, if for every two different edges xy and x 0 y ⁰ of G, one has

\[wt(xy) = f_v(x) + f_e(xy) + f_v(y) \neq wt(x'y') = f_v(x') + f_e(x'y') + f_v(y').\]

The minimum k for which the graph G has an reflexive edge irregular k-labeling is called the reflexive edge strength of G. In this paper we investigate the exact value of reflexive edge strength for generalized prism graphs.

Keywords: reflexive edge irregular labeling, reflexive edge strength, generalized prism graph

Mathematics Subject Classification: 05C78

DOI: 10.5614/ejgta.2022.10.2.6

1. Introduction

Regular and irregular graphs have an important rule in graph theory. Evidently, no simple graph is completely irregular. That is, no simple graph have distinct degree of every vertex. However, multigraphs can have this property. Chartrand et al. in [10] asked, "In a loopless multigraph, determine the fewest parallel edges required to ensure that all vertices have distinct degree." If we

Received: 21 September 2020, Revised: 6 May 2022, Accepted: 4 July 2022.

^aUniversity of Okara, Okara, Pakistan

^bDepartment of Applied Mathematics and Informatics, Technical University, Kosice, Slovak Republic ˇ

^∗ corresponding author

replace the number of parallel edges by the edge label in the corresponding simple graph then the degree of a vertex is determined by adding the labels of the edges incident to that vertex. Then we can rephrase Chartrand's problem as "Assign positive integer labels to the edges of a simple connected graph of order at least 3 in such a way that the graph becomes completely irregular, i.e., the weights (label sums) at each vertex are distinct. What is the minimum value of the largest label over all such irregular assignments?" This parameter of a graph G is well known as the irregularity strength of the graph G denoted by s(G). An excellent survey on the irregularity strength is given by Lehel [16]. For recent results, see papers by Amar and Togni [2], Dimitz et al. [11], Gyarf ´ as´ [12] and Nierhoff [17].

Motivated by these papers, in [7] was defined an edge irregular total k-labeling as a labeling of the vertices and edges of G, f : V (G) ∪ E(G) → {1, 2, . . . , k}, such that the edge-weights wt(xy) = f(x) + f(xy) + f(y) are different for all edges, i.e., wt(xy) 6= wt(x 0 y 0 ) for all edges xy, x⁰ y ⁰ ∈ E(G) with xy 6= x 0 y 0 . The minimum k for which the graph G has an edge irregular total k-labeling is called the total edge irregularity strength of the graph G, tes(G). Some results on the total edge irregularity strength can be found in [1], [3], [4], [8], [9], [13], [14], [15] and [19].

The concept of reflexive irregular multigraphs proposed in [18] is a natural consequence of irregular multigraphs by allowing for loops. Irregular reflexive labeling includes also vertex labels which represent loops and thus the vertex labels are even numbers representing the fact that each loop contributes 2 to the vertex degree (with 0 for a vertex without loops). The weight of a vertex x, under a total labeling f, denoted by wt^f (x), is now determined by summing the incident edge labels and the label of x.

An edge (vertex, total) k-labeling f of a graph G is a mapping from the edge set (vertex set, both edge set and vertex set) of G to the set of the numbers {1, 2, . . . , k}. For a graph G, in [18], are defined two labelings f^e : E(G) → {1, 2, . . . , ke} and f^v : V (G) → {0, 2, . . . , 2kv}. Then the total k-labeling f of G is defined such that f(x) = fv(x) if x ∈ V (G) and f(x) = fe(x) if x ∈ E(G), where k = max{ke, 2kv}. The total k-labeling f is called an edge irregular reflexive k-labeling if for every two different edges xy and x 0 y ⁰ of G one has

\[wt_f(xy) = f(x) + f(xy) + f(y) \neq wt_f(x'y') = f(x') + f(x'y') + f(y').\]

The smallest value of k for which such labeling exists is called the reflexive edge strength of the graph G and is denoted by res(G).

Some results for reflexive edge strength for cycles, Cartesian product of cycles, prisms, wheels, friendship graphs, and for join graphs of the path and cycle are already proved in [5], [6] and [20].

In this paper, we will give the precise value of the reflexive edge strength of generalized prism graphs. That is, the graphs isomorphic to the Cartesian product of a cycle Cⁿ and P^m where n ≥ 3 and m ≥ 2.

2. Reflexive edge strength of generalized prism graphs

Lemma 2.1. [18] For every graph G,

\[\operatorname{res}(G) \ge \begin{cases} \left\lceil \frac{|E(G)|}{3} \right\rceil & \text{if } |E(G)| \not\equiv 2, 3 \pmod{6}, \\ \left\lceil \frac{|E(G)|}{3} \right\rceil + 1 & \text{if } |E(G)| \equiv 2, 3 \pmod{6}. \end{cases}\]

The graph obtained by the Cartesian product of a cycle on n vertices with a path on m vertices is known as a generalized prism graph Cⁿ × Pm. Let the vertex set and the edge set of Cⁿ × P^m be

\[V(C_n \times P_m) = \{x_i^j : 1 \le i \le n, 1 \le j \le m\},\] \[E(C_n \times P_m) = \{x_i^j x_{i+1}^j : 1 \le i \le n, 1 \le j \le m\} \cup \{x_i^j x_i^{j+1} : 1 \le i \le n, 1 \le j \le m-1\},\]

where the index i is taken modulo n.

Note that the graph Cⁿ × P² is known as a prism. In [20] Tanna et al. proved the following result for the reflexive edge strength of prisms.

Theorem 2.1. [20] For n ≥ 3,

\[res(C_n \times P_2) = \begin{cases} n+1 & \text{if } n \text{ is odd,} \\ n & \text{if } n \text{ is even.} \end{cases}\]

In the present paper, we extend this result for generalized prism graphs.

Theorem 2.2. For n even, n ≥ 4 and m ≥ 2,

\[\operatorname{res}(C_n \times P_m) = \begin{cases} \left\lceil \frac{n(2m-1)}{3} \right\rceil & \text{if } n(2m-1) \not\equiv 2, 3 \pmod{6}, \\ \left\lceil \frac{n(2m-1)}{3} \right\rceil + 1 & \text{if } n(2m-1) \equiv 2, 3 \pmod{6}. \end{cases}\]

Proof. As the number of edges in Cⁿ × P^m is n(2m − 1), immediately from Lemma 2.1 we have

\[\operatorname{res}(C_n \times P_m) \ge \begin{cases} \left\lceil \frac{n(2m-1)}{3} \right\rceil & \text{if } n(2m-1) \not\equiv 2, 3 \pmod{6}, \\ \left\lceil \frac{n(2m-1)}{3} \right\rceil + 1 & \text{if } n(2m-1) \equiv 2, 3 \pmod{6}. \end{cases}\]

Let

\[k = \begin{cases} \lceil \frac{n(2m-1)}{3} \rceil & \text{if } n(2m-1) \not\equiv 2, 3 \pmod{6}, \\ \lceil \frac{n(2m-1)}{3} \rceil + 1 & \text{if } n(2m-1) \equiv 2, 3 \pmod{6}. \end{cases}\]

It is easy to check that k is even for even values of n.

We define a total labeling f of Cⁿ × P^m in the following way

\[f(x_i^j) = \begin{cases} n(j-1) & \text{if } 1 \leq i \leq n, j = 1, 2, \dots, \left\lfloor \frac{k}{n} \right\rfloor + 1, \\ n \left\lfloor \frac{k}{n} \right\rfloor & \text{if } 1 \leq i \leq n, j = \left\lfloor \frac{k}{n} \right\rfloor + 2, \left\lfloor \frac{k}{n} \right\rfloor + 3, \dots, m-1, \\ k & \text{if } 1 \leq i \leq n, j = m, \end{cases}\] \[f(x_i^j x_{i+1}^j) = \begin{cases} i & \text{if } 1 \leq i \leq n, j = 1, 2, \dots, \left\lfloor \frac{k}{n} \right\rfloor + 1, \\ 2n \left(j - \left\lfloor \frac{k}{n} \right\rfloor - 1\right) + i & \text{if } 1 \leq i \leq n, j = \left\lfloor \frac{k}{n-1} \right\rfloor + 2, \left\lfloor \frac{k}{n-1} \right\rfloor + 3, \dots, m-1, \\ 2mn - 2n - 2k + i & \text{if } 1 \leq i \leq n, j = m, \end{cases}\]

On reflexive edge strength of generalized prism graphs M. Irfan et al.

\[f(x_i^j x_i^{j+1}) = \begin{cases} i & \text{if } 1 \leq i \leq n, j = 1, 2, \dots, \lfloor \frac{k}{n-1} \rfloor, \\ n(2j - 2\lfloor \frac{k}{n} \rfloor - 1) + i & \text{if } 1 \leq i \leq n, j = \lfloor \frac{k}{n-1} \rfloor + 1, \lfloor \frac{k}{n-1} \rfloor + 2, \dots, m - 2, \\ 2mn - 3n - k - n\lfloor \frac{k}{n} \rfloor + i & \text{if } 1 \leq i \leq n, j = m - 1. \end{cases}\]

Evidently all vertex labels and edge labels are at most k. Moreover, the vertices are labeled with even numbers

Now we compute the edge-weights. For \(1 \le i \le n\) and \(1 \le j \le \lfloor \frac{k}{n} \rfloor + 1\), we have

\[wt_f(x_i^j x_{i+1}^j) = f(x_i^j) + f(x_i^j x_{i+1}^j) + f(x_{i+1}^j) = n(j-1) + i + n(j-1) = n(2j-2) + i.\]

For \(1 \le i \le n\) and \(\lfloor \frac{k}{n} \rfloor + 2 \le j \le m - 1\), we get

\[wt_f(x_i^j x_{i+1}^j) = f(x_i^j) + f(x_i^j x_{i+1}^j) + f(x_{i+1}^j) = n \lfloor \frac{k}{n} \rfloor + (2n(j - \lfloor \frac{k}{n} \rfloor - 1) + i) + n \lfloor \frac{k}{n} \rfloor\]
= \(n(2j - 2) + i\).

For \(1 \le i \le n\) and j = m, we obtain

\[wt_f(x_i^m x_{i+1}^m) = f(x_i^m) + f(x_i^m x_{i+1}^m) + f(x_{i+1}^m) = k + (2mn - 2n - 2k + i) + k\]
= \(n(2m - 2) + i = n(2j - 2) + i\).

Thus for \(1 \le i \le n\) and \(1 \le j \le m\) the edge-weights form the set \(\{1, 2, \dots, n, 2n+1, 2n+2, \dots, 3n, 4n+1, 4n+2, \dots, 2mn-2n+1, 2mn-2n+2, \dots, 2mn-n\}\).

Now for \(1 \le i \le n\) and \(1 \le j \le \lfloor \frac{k}{n} \rfloor\), we have

\[wt_f(x_i^j x_i^{j+1}) = f(x_i^j) + f(x_i^j x_i^{j+1}) + f(x_i^{j+1}) = n(j-1) + i + nj = n(2j-1) + i.\]

For \(1 \le i \le n\) and \(j = \lfloor \frac{k}{n} \rfloor + 1\), we get

\[wt_f\left(x_i^{\lfloor \frac{k}{n} \rfloor + 1} x_i^{\lfloor \frac{k}{n} \rfloor + 2}\right) = f\left(x_i^{\lfloor \frac{k}{n} \rfloor + 1}\right) + f\left(x_i^{\lfloor \frac{k}{n} \rfloor + 1} x_i^{\lfloor \frac{k}{n} \rfloor + 2}\right) + f\left(x_i^{\lfloor \frac{k}{n} \rfloor + 2}\right)\] \[= n\left(\lfloor \frac{k}{n} \rfloor + 1 - 1\right) + \left(n\left(2\lfloor \frac{k}{n} \rfloor + 2 - 2\lfloor \frac{k}{n} \rfloor - 1\right) + i\right) + n\lfloor \frac{k}{n} \rfloor\] \[= n\left(2\lfloor \frac{k}{n} \rfloor + 1\right) + i = n\left(2j - 1\right) + i.\]

For \(1 \le i \le n\) and \(\lfloor \frac{k}{n} \rfloor + 2 \le j \le m-2\), we have

\[wt_f(x_i^j x_i^{j+1}) = f(x_i^j) + f(x_i^j x_i^{j+1}) + f(x_i^{j+1}) = n \lfloor \frac{k}{n} \rfloor + (n(2j - 2\lfloor \frac{k}{n} \rfloor - 1) + i) + n \lfloor \frac{k}{n} \rfloor\] \[= n(2j - 1) + i.\]

For \(1 \le i \le n\) and j = m - 1, we obtain

\[wt_f(x_i^{m-1}x_i^m) = n\left|\frac{k}{n}\right| + (2mn - 3n - k - n\left|\frac{k}{n}\right| + i) + k = 2mn - 3n + i = n(2j-1) + i.\]

This means that for \(1 \le i \le n\) and \(1 \le j \le m-1\), the edge-weights are numbers from the set \(\{n+1, n+2, \ldots, 2n, 3n+1, 3n+2, \ldots, 4n, 5n+1, 5n+2, \ldots, 2mn-3n+1, 2mn-3n+2, \ldots, 2mn-2n\}\).

Combining the previous we get that the edge-weights are distinct numbers from the set \(\{1, 2, \dots, 2mn-2n\}\). This shows that all edges have different weights. So f is a reflexive edge irregular k-labeling of the graph \(C_n \times P_m\) for n even, \(n \ge 4\) and \(m \ge 2\). This completes the proof.

Theorem 2.3. For n odd, n ≥ 3 and m ≥ 2,

\[\operatorname{res}(C_n \times P_m) = \begin{cases} \left\lceil \frac{n(2m-1)}{3} \right\rceil & \text{if } n(2m-1) \not\equiv 2, 3 \pmod{6}, \\ \left\lceil \frac{n(2m-1)}{3} \right\rceil + 1 & \text{if } n(2m-1) \equiv 2, 3 \pmod{6}. \end{cases}\]

Proof. Let n, n ≥ 3, be an odd integer. Using Lemma 2.1 we have the lower bound for the reflexive edge strength of a generalized prism graph Cⁿ × P^m also for n odd as follows

\[\operatorname{res}(C_n \times P_m) \ge \begin{cases} \left\lceil \frac{n(2m-1)}{3} \right\rceil & \text{if } n(2m-1) \not\equiv 2, 3 \pmod{6}, \\ \left\lceil \frac{n(2m-1)}{3} \right\rceil + 1 & \text{if } n(2m-1) \equiv 2, 3 \pmod{6}. \end{cases}\]

Let us define the parameter k in the following way

\[k = \begin{cases} \lceil \frac{n(2m-1)}{3} \rceil & \text{if } n(2m-1) \not\equiv 2, 3 \pmod{6}, \\ \lceil \frac{n(2m-1)}{3} \rceil + 1 & \text{if } n(2m-1) \equiv 2, 3 \pmod{6}. \end{cases}\]

According to the parity of k we distinguish two cases. Note, that k is odd if and only if n ≡ 1 (mod 6) and m ≡ 1 (mod 3) or if n ≡ 5 (mod 6) and m ≡ 0 (mod 3). Case 1. When k is even.

We define a total labeling f of Cⁿ × P^m such that

\[f(x_i^j) = \begin{cases} (n-1)(j-1) & \text{if } 1 \le i \le n, j = 1, 2, \dots, \left\lfloor \frac{k}{n-1} \right\rfloor + 1, \\ (n-1)\left\lfloor \frac{k}{n-1} \right\rfloor & \text{if } 1 \le i \le n, j = \left\lfloor \frac{k}{n-1} \right\rfloor + 2, \left\lfloor \frac{k}{n-1} \right\rfloor + 3, \dots, m-1, \\ k & \text{if } 1 \le i \le n, j = m, \end{cases}\] \[f(x_i^j x_{i+1}^j) = \begin{cases} 2(j-1) + i & \text{if } 1 \le i \le n, j = 1, 2, \dots, \left\lfloor \frac{k}{n-1} \right\rfloor + 1, \\ 2(j-1) + 2(n-1)\left(j - \left\lfloor \frac{k}{n-1} \right\rfloor - 1\right) + i & \text{if } 1 \le i \le n, j = \left\lfloor \frac{k}{n-1} \right\rfloor + 2, \\ 2mn - 2n - 2k + i & \text{if } 1 \le i \le n, j = m, \end{cases}\] \[f(x_i^j x_i^{j+1}) = \begin{cases} 2j - 1 + i & \text{if } 1 \le i \le n, j = m, \\ 2j - 1 + (n-1)\left(2j - 2\left\lfloor \frac{k}{n-1} \right\rfloor - 1\right) + i & \text{if } 1 \le i \le n, j = \left\lfloor \frac{k}{n-1} \right\rfloor + 1, \\ \left\lfloor \frac{k}{n-1} \right\rfloor + 2, \dots, m-2, \\ 2mn - 3n - k - (n-1)\left\lfloor \frac{k}{n-1} \right\rfloor + i & \text{if } 1 \le i \le n, j = m-1. \end{cases}\]

The vertices are labeled with even numbers and all vertex labels and all edge labels are at most k.

For the edge-weights we get the following. For 1 ≤ i ≤ n and 1 ≤ j ≤ b ^k n−1 c + 1, we obtain

\[wt_f(x_i^j x_{i+1}^j) = f(x_i^j) + f(x_i^j x_{i+1}^j) + f(x_{i+1}^j) = (n-1)(j-1) + (2(j-1)+i) + (n-1)(j-1) = n(2j-2) + i.\]

For \(1 \le i \le n\) and \(\lfloor \frac{k}{n-1} \rfloor + 2 \le j \le m-1\), we have

\[wt_f(x_i^j x_{i+1}^j) = f(x_i^j) + f(x_i^j x_{i+1}^j) + f(x_{i+1}^j)\] \[= (n-1) \left\lfloor \frac{k}{n-1} \right\rfloor + \left( 2(j-1) + 2(n-1) \left( j - \left\lfloor \frac{k}{n-1} \right\rfloor - 1 \right) + i \right) + (n-1) \left\lfloor \frac{k}{n-1} \right\rfloor\] \[= n(2j-2) + i.\]

For \(1 \le i \le n\) and j = m, we get

\[wt_f(x_i^m x_{i+1}^m) = f(x_i^m) + f(x_i^m x_{i+1}^m) + f(x_{i+1}^m) = k + (2mn - 2n - 2k + i) + k\]\[= n(2m - 2) + i.\]

Thus for \(1 \le i \le n\) and \(1 \le j \le m\) the edge-weights are 1, 2, ..., n, 2n + 1, 2n + 2, ..., 3n, 4n + 1, 4n + 2, ..., 2mn - 2n + 1, 2mn - 2n + 2, ..., 2mn - n.

For \(1 \le i \le n\) and \(1 \le j \le \lfloor \frac{k}{n-1} \rfloor\), we have

\[wt_f(x_i^j x_i^{j+1}) = f(x_i^j) + f(x_i^j x_i^{j+1}) + f(x_i^{j+1}) = (n-1)(j-1) + (2j-1+i) + (n-1)j\]\[= n(2j-1) + i.\]

For \(1 \le i \le n\) and \(j = \lfloor \frac{k}{n-1} \rfloor + 1\), we get

\[wt_f\left(x_i^{\lfloor \frac{k}{n}\rfloor + 1} x_i^{\lfloor \frac{k}{n}\rfloor + 2}\right) = f\left(x_i^{\lfloor \frac{k}{n}\rfloor + 1}\right) + f\left(x_i^{\lfloor \frac{k}{n}\rfloor + 1} x_i^{\lfloor \frac{k}{n}\rfloor + 2}\right) + f\left(x_i^{\lfloor \frac{k}{n}\rfloor + 2}\right)\] \[= (n-1)\lfloor \frac{k}{n-1}\rfloor + \left(2\lfloor \frac{k}{n-1}\rfloor + 1 + (n-1)\left(2\lfloor \frac{k}{n-1}\rfloor + 2 - 2\lfloor \frac{k}{n-1}\rfloor - 1\right) + i\right)\] \[+ (n-1)\lfloor \frac{k}{n-1}\rfloor = n(2j-1) + i.\]

For \(1 \le i \le n\) and \(\lfloor \frac{m-2}{3} \rfloor + 1 \le j \le m-2\), we have

\[wt_f(x_i^j x_i^{j+1}) = f(x_i^j) + f(x_i^j x_i^{j+1}) + f(x_i^{j+1})\] \[= (n-1) \left\lfloor \frac{k}{n-1} \right\rfloor + \left(2j-1 + (n-1)\left(2j-2\left\lfloor \frac{k}{n-1} \right\rfloor - 1\right) + i\right) + (n-1) \left\lfloor \frac{k}{n-1} \right\rfloor\] \[= n(2j-1) + i.\]

For \(1 \le i \le n\) and j = m - 1, we obtain

\[wt_f(x_i^{m-1}x_i^m) = (n-1)\lfloor \frac{k}{n-1} \rfloor + (2mn - 3n - k - (n-1)\lfloor \frac{k}{n-1} \rfloor + i) + k = n(2m-3) + i.\]

This means that for \(1 \le i \le n\) and \(1 \le j \le m-1\), the edge-weights form the set \(\{n+1, n+2, n+3, \ldots, 2n, 3n+1, 3n+2, \ldots, 4n, 5n+1, 5n+2, \ldots, 6n, \ldots, 2mn-3n+1, 2mn-3n+2, \ldots, 2mn-2n\}\).

Thus the set of edge-weights is \(\{1, 2, \dots, n(2m-1)\}\). This shows that all edges have different weights. This means that the labeling f is reflexive edge irregular.

Case 2. When k is odd.

In this case we define a total labeling f of \(C_n \times P_m\) in the following way

\[f(x_i^j) = \begin{cases} (n-1)(j-1) & \text{if } 1 \leq i \leq n, j = 1, 2, \dots, \left\lfloor \frac{k-1}{n-1} \right\rfloor + 1, \\ (n-1) \left\lfloor \frac{k-1}{n-1} \right\rfloor & \text{if } 1 \leq i \leq n, j = \left\lfloor \frac{k-1}{n-1} \right\rfloor + 2, \left\lfloor \frac{k-1}{n-1} \right\rfloor + 3, \dots, m-1, \\ k-1 & \text{if } 1 \leq i \leq n, j = m, \end{cases}\] \[f(x_i^j x_{i+1}^j) = \begin{cases} 2(j-1) + i & \text{if } 1 \leq i \leq n, j = 1, 2, \dots, \left\lfloor \frac{k-1}{n-1} \right\rfloor + 1, \\ 2(j-1) + 2(n-1)\left(j - \left\lfloor \frac{k-1}{n-1} \right\rfloor - 1\right) + i & \text{if } 1 \leq i \leq n, j = \left\lfloor \frac{k-1}{n-1} \right\rfloor + 2, \\ \left\lfloor \frac{k-1}{n-1} \right\rfloor + 3, \dots, m-1, \\ 2mn - 2n - 2k + 2 + i & \text{if } 1 \leq i \leq n, j = m, \end{cases}\] \[f(x_i^j x_i^{j+1}) = \begin{cases} 2j - 1 + i & \text{if } 1 \leq i \leq n, j = 1, 2, \dots, \left\lfloor \frac{k-1}{n-1} \right\rfloor + 1, \\ 2j - 1 + (n-1)\left(2j - 2\left\lfloor \frac{k-1}{n-1} \right\rfloor - 1\right) + i & \text{if } 1 \leq i \leq n, j = \left\lfloor \frac{k-1}{n-1} \right\rfloor + 1, \\ \left\lfloor \frac{k-1}{n-1} \right\rfloor + 2, \dots, m-2, \\ 2mn - 3n - k + 1 - (n-1)\left\lfloor \frac{k-1}{n-1} \right\rfloor + i & \text{if } 1 \leq i \leq n, j = m-1. \end{cases}\]

The vertex labels are all even numbers not greater than k and also the edge labels are at most k.

First we compute the weights of the edges of the form \(x_i^j x_{i+1}^j, i=1,2,\ldots,n, j=1,2,\ldots,m\), where the index i is taken modulo n. For \(1 \le i \le n\) and \(1 \le j \le \lfloor \frac{k-1}{n-1} \rfloor + 1\), we get

\[wt_f(x_i^j x_{i+1}^j) = f(x_i^j) + f(x_i^j x_{i+1}^j) + f(x_{i+1}^j) = (n-1)(j-1) + (2(j-1)+i) + (n-1)(j-1) = n(2j-2) + i.\]

For \(1 \le i \le n\) and \(\lfloor \frac{k-1}{n-1} \rfloor + 2 \le j \le m-1\), we obtain

\[wt_{f}(x_{i}^{j}x_{i+1}^{j}) = f(x_{i}^{j}) + f(x_{i}^{j}x_{i+1}^{j}) + f(x_{i+1}^{j})\] \[= (n-1) \lfloor \frac{k-1}{n-1} \rfloor + (2(j-1) + 2(n-1)(j - \lfloor \frac{k-1}{n-1} \rfloor - 1) + i) + (n-1) \lfloor \frac{k-1}{n-1} \rfloor\] \[= n(2j-2) + i.\]

For \(1 \le i \le n\) and j = m, we have

\[wt_f(x_i^m x_{i+1}^m) = f(x_i^m) + f(x_i^m x_{i+1}^m) + f(x_{i+1}^m) = (k-1) + (2mn - 2n - 2k + 2 + i) + (k-1)\]\[= n(2m-2) + i.\]

Thus for \(1 \le i \le n\) and \(1 \le j \le m\) the edge-weights are distinct numbers from the set \(\{1, 2, \ldots, n, 2n + 1, 2n + 2, \ldots, 3n, 4n + 1, 4n + 2, \ldots, 5n, \ldots, 2mn - 2n + 1, 2mn - 2n + 2, \ldots, 2mn - n\}.\)

Now we compute the weights of the edges of the form \(x_i^j x_i^{j+1}\), \(i=1,2,\ldots,n, j=1,2,\ldots,m-1\). For \(1 \le i \le n\) and \(1 \le j \le \lfloor \frac{k-1}{n-1} \rfloor\), we get

\[wt_f(x_i^j x_i^{j+1}) = f(x_i^j) + f(x_i^j x_i^{j+1}) + f(x_i^{j+1}) = (n-1)(j-1) + (2j-1+i) + (n-1)j\]

On reflexive edge strength of generalized prism graphs M. Irfan et al.

\[=n(2j-1)+i.\]

For \(1 \le i \le n\) and \(j = \lfloor \frac{k-1}{n-1} \rfloor + 1\), we have

\[wt_{f}\left(x_{i}^{\lfloor\frac{k-1}{n-1}\rfloor+1}x_{i}^{\lfloor\frac{k-1}{n-1}\rfloor+2}\right) = f\left(x_{i}^{\lfloor\frac{k-1}{n-1}+1}\right) + f\left(x_{i}^{\lfloor\frac{k-1}{n-1}\rfloor+1}x_{i}^{\lfloor\frac{k-1}{n-1}\rfloor+2}\right) + f\left(x_{i}^{\lfloor\frac{k-1}{n-1}\rfloor+2}\right)\] \[= (n-1)\lfloor\frac{k-1}{n-1}\rfloor + \left(2\lfloor\frac{k-1}{n-1}\rfloor + 1 + (n-1)\left(2\lfloor\frac{k-1}{n-1}\rfloor + 2 - 2\lfloor\frac{k-1}{n-1}\rfloor - 1\right) + i\right) + (n-1)\lfloor\frac{k-1}{n-1}\rfloor = n(2j-1) + i.\]

For \(1 \le i \le n\) and \(\lfloor \frac{k-1}{n-1} \rfloor + 1 \le j \le m-2\), we obtain

\[wt_f(x_i^j x_i^{j+1}) = f(x_i^j) + f(x_i^j x_i^{j+1}) + f(x_i^{j+1})\] \[= (n-1) \left\lfloor \frac{k-1}{n-1} \right\rfloor + \left(2j-1+(n-1)\left(2j-2\left\lfloor \frac{k-1}{n-1} \right\rfloor - 1\right) + i\right) + (n-1) \left\lfloor \frac{k-1}{n-1} \right\rfloor\] \[= n(2j-1) + i.\]

For \(1 \le i \le n\) and j = m - 1, we obtain

\[wt_f(x_i^{m-1}x_i^m) = (n-1)\lfloor \frac{k-1}{n-1} \rfloor + (2mn - 3n - k + 1 - (n-1)\lfloor \frac{k-1}{n-1} \rfloor + i) + k - 1\]\[= n(2m-3) + i.\]

This means that for \(1 \le i \le n\) and \(1 \le j \le m-1\), the edge-weights are \(\{n+1,n+2,n+3,\ldots,2n,3n+1,3n+2,\ldots,4n,5n+1,5n+2,\ldots,6n,\ldots,2mn-3n+1,2mn-3n+2,\ldots,2mn-2n\}\). Thus also if k is odd we get that edge-weights are distinct numbers from the set \(\{1,2,\ldots,2mn-2n\}\). This concludes the proof.

Immediately from Theorems 2.2 and 2.3 we obtain the following result for the reflexive edge strength of generalized prism graphs

Theorem 2.4. For \(n \geq 3\) and \(m \geq 2\),

\[\operatorname{res}(C_n \times P_m) = \begin{cases} \left\lceil \frac{n(2m-1)}{3} \right\rceil & \text{if } n(2m-1) \not\equiv 2, 3 \pmod{6}, \\ \left\lceil \frac{n(2m-1)}{3} \right\rceil + 1 & \text{if } n(2m-1) \equiv 2, 3 \pmod{6}. \end{cases}\]

3. Conclusion

In this paper we proved the precise values of the reflexive edge strength for the generalized prism graphs \(C_n \times P_m\) for \(n \geq 3\), \(m \geq 2\).

Acknowledgement

This work was supported by the Slovak Science and Technology Assistance Agency under the contract No. APVV-19-0153 and by VEGA 1/0243/23.

References

• [1] A. Ahmad, M. Baca and M. Numan, On irregularity strength of disjoint union of friendship ˇ graphs, Electron. J. Graph Theory Appl. 1 (2) (2013), 100–108.
• [2] D. Amar and O. Togni, Irregularity strength of trees, Discrete Math. 190 (1998), 15–38.
• [3] M. Anholcer and C. Palmer, Irregular labelings of circulant graphs, Discrete Math. 312(23) (2012), 3461–3466.
• [4] F. Ashraf, M. Baca, A. Semani ˇ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova and S.W. Saputro, On cycle-irregularity ´ strength of ladders and fan graphs, Electron. J. Graph Theory Appl. 8 (1) (2020), 181–194.
• [5] M. Baca, M. Irfan, J. Ryan, A. Semani ˇ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova and D. Tanna, Note on edge irreg- ´ ular reflexive labelings of graphs, AKCE J. Graphs. Combin. 16(2) (2019), 145–157.
• [6] M. Baca, M. Irfan, J. Ryan, A. Semani ˇ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova and D. Tanna, On edge irregular ´ reflexive labellings for the generalized friendship graphs, Mathematics 5(4) (2017), 67.
• [7] M. Baca, S. Jendrol ˇ ', M. Miller and J. Ryan, Total irregular labelings, Discrete Math. 307 (2007), 1378–1388.
• [8] M. Baca, and M.K. Siddiqui, Total edge irregularity strength of generalized prism, ˇ Appl. Math. Comput. 235 (2014), 168–173.
• [9] S. Brandt, J. Miskuf and D. Rautenbach, On a conjecture about edge irregular total labellings, ˇ J. Graph Theory 57 (2008), 333–343.
• [10] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Cong. numer. 64 (1988), 187–192.
• [11] J.H. Dimitz, D.K. Garnick and A. Gyarf ´ as, On the irregularity strength of the ´ m × n grid, J. Graph Theory 16 (1992), 355–374.
• [12] A. Gyarf ´ as, The irregularity strength of ´ Km,m is 4 for odd m, Discrete Math. 71 (1998), 273–274.
• [13] D. Indriati, Widodo, I.E. Wijayanti, K.A. Sugeng and I. Rosyida, Totally irregular total labeling of some caterpillar graphs, Electron. J. Graph Theory Appl. 8 (2) (2020), 247–254.
• [14] J. Ivanco and S. Jendrol ˇ ', Total edge irregularity strength of trees, Discuss. Math. Graph Theory 26 (2006), 449–456.
• [15] S. Jendrol', J. Miskuf and R. Sot ˇ ak, Total edge irregularity strength of complete and complete ´ bipartite graphs, Electron. Notes Discrete Math. 28 (2007), 281–285.
• [16] J. Lehel, Facts and quests on degree irregular assignment, Graph Theory, Combin. Appl., Wiley, New York, 1991, p.p. 765–782.

• [17] T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13 (2000), 313–323.
• [18] J. Ryan, B. Munasinghe, A. Semanicov ˇ a-Fe ´ nov ˇ cˇ´ıkova and D. Tanna, Reflexive irregular la- ´ belings, submitted.
• [19] M.K. Siddiqui, On the total edge irregularity strength of a categorical product of a cycle and a path, AKCE J. Graphs. Combin. 9(1) (2012), 43–52.
• [20] D. Tanna, J. Ryan and A. Semanicov ˇ a-Fe ´ nov ˇ cˇ´ıkova, Edge irregular reflexive labeling of ´ prisms and wheels, Australas. J. Comb. 69(3) (2017), 394–401.