Modular total vertex irregularity strength of graphs

1.   Introduction

All graphs considered in this paper are finite, undirected and simple. If $G$ is a graph, then $V(G)$ and $E(G)$ stand for the vertex set and the edge set of $G$, respectively. Let the order of a graph $G$ be denoted by $n$. For numbers $a$ and $b$, let $[a, b]$ denote the set of all integers $c$ such that $a\le c\le b$. Let $k\ge 1$ be a positive integer. For a graph $G$ a mapping $\varphi: E(G) \to [1, k]$ induces the weight of a vertex $u\in V(G)$ defined by

If all vertices have distinct weights, then we call this mapping an irregular labeling. The irregularity strength of a graph $G$, abbreviated as ${\rm{s}}(G)$, is defined to be the maximal integer $k$, minimized over all irregular labelings. If such $k$ does not exist, then ${\rm{s}}(G) = \infty$. Evidently, the parameter ${\rm{s}}(G)$ is finite if and only if at most one component of $G$ is isomorphic to $K_1$ and no component is isomorphic to $K_2$.

The topic of irregularity strength was first introduced by Chartrand et al. ^[1]. In the same paper the following bound of this parameter is proved

where $n_i$ stands for the number of vertices of degree $i$ and $\Delta(G)$ for the maximum degree of $G$.

Faudree and Lehel ^[2] proved that the irregularity strength of an $r$-regular graph $G$, $r\ge 2$, is bounded above ${\rm{s}}(G) \le \left\lceil \tfrac{n}{2}\right\rceil +9$. Moreover, they proposed a conjecture that for each $r$-regular graph is ${\rm{s}}(G) \le \tfrac{n}{r} + c$, where $c$ is a constant. This upper bound was sequentially improved by Cuckler and Lazebnik ^[3] who exploited probabilistic approach and then by Przybyło ^[4] and Kalkowski, Karonski and Pfender ^[5]. Recently Majerski and Przybyło showed in ^[6] that ${\rm{s}}(G) \le \tfrac{(4+o(1))n}{\delta(G)} +4$ for graphs having the minimum degree $\delta(G) \ge \sqrt{n}\ln n$.

The irregularity strength of paths and complete graphs is investigated in ^[1], of cycles and Turan graphs in ^[7]. The generalized Petersen graphs are studied in ^[8], trees in ^[9] and circulant graphs in ^[10]. Other results on the irregularity strength and its variations can be found in ^[11,12,13].

The modular irregular labeling as a variation of the irregular labeling was introduced in ^[14]. Let $\mathbb Z_n$ be the group of integers modulo $n$. For a graph $G$ of order $n$ a mapping $\varphi: E(G) \to [1, k]$ is said to be a modular irregular $k$-labeling if the induced vertex mapping $\lambda: V(G) \to \mathbb Z_n$ defined such that

is a bijection. The label $\lambda(u)$ is known as the modular weight of the vertex $u$. The modular irregularity strength, ${\rm{ms}}(G)$, of a graph $G$ is defined as the minimum $k$ for which $G$ has a modular irregular labeling using labels at most $k$. If such $k$ does not exist, then ${\rm{ms}}(G) = \infty$.

Obviously, a modular irregular labeling of a given graph is also its irregular labeling. This indicates a correspondence between the irregularity strength and the modular irregularity strength and gives a trivial lower bound of the modular irregularity strength of a graph

The modular irregularity strength for cycles, paths and stars are investigated in ^[14], for fan graphs, wheels and friendship graphs are proved in ^[15,16,17], respectively. An edge version of the modular irregularity strength is studied in ^[18].

For a graph $G$, in ^[19], it introduces a total labeling $\psi: V(G) \cup E(G) \to [1, k]$ called a vertex irregular total $k$-labeling having the property that distinct vertices have distinct total vertex weights, where the total vertex weight of a vertex $u$ is defined as $wt_{\psi}(u) = \psi (u) + \sum\limits_{uv \in E(G)} \psi (uv)$. The minimum $k$ for which $G$ has a vertex irregular total $k$-labeling is called the total vertex irregularity strength of $G$, abbreviated as ${\rm{tvs}}(G)$. This graph invariant is defined for all graphs. Moreover, if we restricted on graphs whose every component had at least 3 vertices, then

If $G$ has maximum degree $\Delta(G)$ and minimum degree $\delta(G)$ then

This result was proved by Bača et al. in ^[19]. Moreover, if we restrict on graphs whose every component has at least 3 vertices they also proved

For general graphs Przybyło ^[4] obtained bound ${\rm{tvs}}(G) < \tfrac{32n}{\delta(G)} +8$ and for $r$-regular graphs he proved ${\rm{tvs}}(G) < \tfrac{8n}r+3$. Anholcer et al. ^[20] improved this result and proved ${\rm{tvs}}(G) \le 3\left\lceil \tfrac{n}{\delta(G)} \right\rceil +1 \le \tfrac{3n}{\delta(G)} +4$. Majerski and Przybyło in ^[21] showed that ${\rm{tvs}}(G) \le \left(2+o(1)\right)\tfrac{n}{\delta(G)} +4$, when $\delta(G) \ge \sqrt{n}\ln n$. The results for circulant graphs are obtained in ^[22] and for unicyclic graphs in ^[23].

Motivated by the concept of the modular irregular labeling and the concept of the vertex irregular total labeling, we study modular vertex irregular total labelings in this paper.

For a graph $G$ of order $n$ a total labeling $\psi: V(G) \cup E(G) \to [1, k]$ is called a modular vertex irregular total $k$-labeling if the induced vertex mapping $\lambda: V(G) \to \mathbb Z_{n}$ defined by

is a bijection. The label $\lambda(u)$ is called as the modular total vertex weight of the vertex $u$. The modular total vertex irregularity strength of a graph $G$, abbreviated as ${\rm{mtvs}}(G)$, is defined as the minimum $k$ for which $G$ has a modular vertex irregular total $k$-labeling.

The rest of this paper is organized in the following way. In Section 2 we study properties of modular vertex irregular total $k$-labelings and we obtain estimations on the modular total vertex irregularity strength. Section 3 is devoted to the investigation of existence of modular vertex irregular total $k$-labelings for certain families of graphs and to determining the precise values of the modular total vertex irregularity strength that prove the sharpness of the lower bound.

2.   Estimations on the modular total vertex irregularity strength

Evidently from the definition it follows that every modular vertex irregular total $k$-labeling of a graph is also its vertex irregular total $k$-labeling. Thus, we have the following lower bound of the modular total vertex irregularity strength

Trivially, the relationship (1.1) is also true for the modular version. This gives an upper bound of the corresponding graph invariant.

Theorem 2.1. Let $G$ be a graph with no component of order at most $2$. Then

Proof. Consider that $\varphi: E(G) \to [1, {\rm{ms}}(G)]$ is a labeling of a graph $G$ of order $n$ whose every component has at least 3 vertices providing the modular irregularity strength ${\rm{ms}}(G)$. If we extend this edge labeling to the total labeling $\psi$ such that $\psi(e) = \varphi(e)$ for every $e\in E(G)$ and $\psi(v) = 1$ for every $v\in V(G)$, then each vertex weight increases by 1 and new total vertex weights of $G$ taken modulo $n$ clearly attain values from $0$ to $n-1$. Thus $\psi$ is a modular vertex irregular total labeling.

In general, the converse of (2.1) does not hold. However, the following statement applies.

Theorem 2.2. Let $G$ be a graph with ${\rm{tvs}}(G) = k$. If total vertex weights under a corresponding vertex irregular total $k$-labeling constitute a set of consecutive integers, then

3.   Precise values of ${{mtvs}}$ for certain families of graphs

Combining (1.2), (2.1) and (2.2) we get

In this section we deal with the existence of modular vertex irregular total labelings for several graphs. We evaluate the precise values of the modular total vertex irregularity strength for paths, cycles, complete graphs and stars. These results prove the sharpness of the lower bound (3.1).

In ^[14] is determined the precise value of the modular irregularity strength for paths $P_n$ of order $n\ge 3$ as follows

Now we present a result on the modular total vertex irregularity strength for a path which proves that the lower bound in (3.1) is tight.

Theorem 3.1. Let $P_n$ be a path on $n\ge 2$ vertices. Then

Proof. For $n\ge 2$, let

The path $P_2$ admits a vertex irregular total $2$-labeling with vertex labels $1, 2$ and the edge label $1$, where the induced vertex weights are $2$ and $3$. Thus this labeling is also modular and ${\rm{mtvs}}(P_2) = 2$.

According to (3.1) we have that ${\rm{mtvs}}(P_n) \ge \left\lceil\tfrac{n+1}{3}\right\rceil$. To prove the equality we show the existence of a modular vertex irregular total $\left\lceil \tfrac{n+1}3\right\rceil$-labeling.

For $n\ge 3$, we define the total labeling $\psi$ in the following way

One can check that when $n$ is even the maximal label of the vertex $v_i$, $i\in[2, \tfrac{n}{2}+1]$ is

of the vertex $v_{n-i}$, $i\in[1, \tfrac{n}{2}-2]$ is

and the maximal label of the edge $e_i$, $i\in[1, \tfrac{n}{2}]$ is

finally for the edge $e_{n-i}$, $i\in[1, \tfrac{n}{2}-1]$ we get

Analogously, when $n$ is odd then the maximal label of the vertex $v_i$, $i\in [2, \tfrac{n-1}{2}]$ is

and of the vertex $v_{n-i}$, $i\in [1, \tfrac{n-1}{2}]$ is

For the edges we get the following. For the edge $e_i$, $i\in [1, \tfrac{n-1}{2}]$ the maximal label is

and for $e_{n-i}$, $i\in[1, \tfrac{n-1}{2}]$ is

It is routine to check that in both cases all vertex labels and edge labels are at most $\left\lceil \tfrac{n+1}{3}\right\rceil$. Thus $\psi$ is a total $\left\lceil \tfrac{n+1}3\right\rceil$-labeling.

For the total vertex weights we obtain

The total vertex weights under the total labeling $\psi$ successively attain values from the set $[2, n+1]$. Thus according to Theorem 2.2 we have that ${\rm{tvs}}(P_n) = {\rm{mtvs}}(P_n) = \left\lceil \tfrac{n+1}{3}\right\rceil$. This completes the proof.

In ^[19] is proved that ${\rm{tvs}}(C_n) = \left\lceil \tfrac{n+2}{3}\right\rceil$ and total vertex weights under the corresponding vertex irregular total $\left\lceil \tfrac{n+2}{3}\right\rceil$-labeling constitute the set of consecutive integers $[3, n+2]$. According to Theorem 2.2 we have the following result:

Theorem 3.2. Let $C_n$ be a cycle with $n\ge 3$ vertices. Then

Chartrand et al. ^[1] showed that for the complete graph $K_n$, $n\ge 3$, ${\rm{s}}(K_n) = 3$. In ^[19] is described a suitable vertex irregular total $2$-labeling of $K_n$ with vertices $v_1, v_2, \dots, v_n$, $n\ge 2$, which for the vertex $v_t$ induces the total weight $wt(v_t) = n+t-1$ for any $t\in[1, n]$. Hence according to Theorem 2.2 we get the next theorem.

Theorem 3.3. Let $K_n$ be a complete graph of order $n\ge 2$. Then

Let $K_{1, n}$ be a star with $n$ pendant vertices, say $v_1, v_2, \dots, v_n$, and the center vertex, say $u$. In ^[19] is proved that

but described vertex irregular total $\left\lceil \tfrac{n+1}{2}\right\rceil$-labeling is not modular. In the next theorem we provide a suitable modular vertex irregular total $\left\lceil \tfrac{n+1}{2} \right\rceil$-labeling.

Theorem 3.4. Let $K_{1, n}$ be a star of order $n+1$, $n\ge 1$. Then

Proof. Since $K_{1, 1}$ is the path on two vertices then ${\rm{mtvs}}(K_{1, 1})$ follows from Theorem 3.1. From (3.2) for $n\ge 2$ we obtain that ${\rm{mtvs}}(K_{1, n}) \ge \left\lceil \tfrac{n+1}{2}\right\rceil$. Let $k = \left\lceil \tfrac{n+1}{2}\right\rceil$. To prove that $k\ge {\rm{mtvs}}(K_{1, n})$ we define a modular vertex irregular total $k$-labelings $\psi_j$, $j\in[1,4]$, where the total weights of vertices $v_i$, $i\in[1, n]$, are the numbers $2, 3, \dots, n+1$, i.e., the corresponding modular total vertex weights are $2, 3, 4, \dots, n, 0 \pmod {n+1}$ and the center vertex $u$ will have the modular total weight congruent 1 $\pmod {n+1}$.

We consider two cases.

Case 1. For $n$ is even, we define total labelings $\psi_1$ and $\psi_2$ in the following way.

It is not difficult to see that

The values $\psi_1(v_iu)$ together with $\psi_1(u) = 1$ give the smallest total weight of the center vertex $u$. On the other side the values $\psi_2(v_iu)$ together with $\psi_2(u) = \tfrac{n}{2}+1$ give the greatest total weight of $u$. Thus

If for the vertex $u$ we take a value from the interval $\left[1, \tfrac{n}{2}+1 \right]$ and we swap the vertex label $\psi(v_i)$ with the edge label $\psi(v_iu)$ for certain values of $i$, $i\in [1, n]$, then for total weight of the center vertex $u$ we are able to get all the values from the interval $\left[\tfrac{n^2+6n}{8} +1, \tfrac{3n^2+10n}{8} +1 \right]$. The process of swapping does not have any effect on the total vertex weights of $v_i$, $i\in [1, n]$.

In the interval $\left[\tfrac{n^2+6n}{8} +1, \tfrac{3n^2+10n}{8} +1 \right]$ we need to find at least one value which is congruent 1 $\pmod {n+1}$. It is easy to prove that the interval $\left[\tfrac{n^2+6n}{8(n+1)}, \tfrac{3n^2+10n}{8(n+1)} \right]$ contains at least one integer. For example, if $n = 2$ then the interval $\left[\tfrac{16}{24}, \tfrac{32}{24} \right]$ contains the integer $t = 1$ and $wt(u) = t(n+1)+1 = 4 \equiv 1 \pmod {3}$. If $n = 4$ then the interval $\left[1, \tfrac{88}{40} \right]$ contains two integers $t = 1$ and $t = 2$. If $t = 1$ then $wt(u) = t(n+1)+1 = 6 \equiv 1 \pmod {5}$ and if $t = 2$ then $wt(u) = t(n+1)+1 = 11 \equiv 1 \pmod {5}$. Figure 1 illustrates the corresponding modular vertex irregular total labelings of $K_{1, 2}$ and $K_{1, 4}$.

Case 2. For $n$ is odd, we define total labelings $\psi_3$ and $\psi_4$ as follows.

We can see that vertices $v_i$, $i\in[1, n]$, attain the total weights

Moreover,

If we swap the vertex label $\psi(v_i)$ with the edge label $\psi(v_iu)$ for certain values of $i$, $i\in[1, n]$ and for the vertex $u$ we take a value from the interval $\left[1, \tfrac{n+1}{2} \right]$ then for total weight of the center vertex $u$ we can get all the values from the interval $\left[\tfrac{n^2+8n-1}{8} +1, \tfrac{3n^2+8n-3}{8} +1 \right]$. Note that swapping of vertex and edge labels will not have any impact on the total weights of vertices $v_i$, $1\le i\le n$.

Similarly to the previous case one can see that the interval $\left[\tfrac{n^2+8n-1}{8(n+1)}, \tfrac{3n^2+8n-3}{8(n+1)} \right]$ contains at least one integer. For example, if $n = 3$ then the interval $\left[1, \tfrac{48}{32} \right]$ contains one integer $t = 1$ and if $n = 5$ then the interval $\left[\tfrac{64}{48}, \tfrac{112}{48} \right]$ contains one integer $t = 2$. If $t = 1$ then $wt(u) = t(n+1)+1 = 5 \equiv 1 \pmod {4}$ and if $t = 2$ then $wt(u) = t(n+1)+1 = 13 \equiv 1 \pmod {6}$. Figure 2 depicts a corresponding modular vertex irregular total $2$-labeling of $K_{1, 3}$ respective a total $3$-labeling of $K_{1, 5}$. Thus, we arrive at the desired result.

4.   Conclusions

In this paper, we define a concept of the modular total vertex irregularity strength, as a variation of the modular irregularity strength and total vertex irregularity strength. We determine a lower bound and an upper bound of this graph characteristic and obtain the precise values for some graphs. The obtained results for cycles, paths, complete graphs and stars prove the sharpness of the presented lower bound.

Acknowledgments

The authors A. ALoqaily and N. Mlaiki would like to thank Prince Sultan University for paying the APC and for the support through the TAS research lab. The research for this article was also supported by the Slovak Research and Development Agency under the contract APVV-19-0153 and by VEGA 1/0243/23.

Conflict of interest

The authors declare that they have no conflicts of interest.