Modular edge irregularity strength of graphs

1.   Introduction

Throughout this paper, $G = (V, E)$ is a simple graph with the vertex set $V(G)$ and the edge set $E(G)$. Chartrand et al. in ^[1] introduced an edge $k$-labeling $\psi: E(G) \to \{1, 2, \dots, k\}$ of a graph $G$ such that the sum of the labels of edges incident with a vertex is different for all the vertices of $G$. Such labelings were called irregular assignments and the irregularity strength ${{\rm{s}}}(G)$ of a graph $G$ is known as the maximal integer $k$, minimized over all irregular assignments. If no such assignment exists then ${{\rm{s}}}(G) = \infty$. Obviously, ${{\rm{s}}}(G) < \infty$ if and only if $G$ contains no isolated edge and has at most one isolated vertex. The irregularity strength has attracted much attention ^{[2,3,4,5,6,7,8]}.

Motivated by these papers, Ahmad et al. in ^[9] defined an edge irregular $k$-labeling of a graph $G$ to be a vertex labeling $\varphi: V(G) \to \{1, 2, \dots, k\}$ such that the edge-weights $wt_{\varphi}(uv) = \varphi(u) + \varphi(v)$ are different for all edges, that is $wt_{\varphi}(uv) \neq wt_{\varphi}(u'v')$ for all different edges $uv, u'v' \in E(G)$. Furthermore, they defined the edge irregularity strength, ${{\rm{es}}}(G)$, of $G$ as the minimum $k$ for which the graph $G$ has an edge irregular $k$-labeling.

For a simple graph with maximum degree $\Delta(G)$ in ^[9] is estimated a lower bound of the edge irregularity strength in the form

For several families of graphs, the exact value of the edge irregularity strength has been determined, namely for paths, stars, double stars and cartesian product of two paths in ^[9], for Toeplitz graphs in ^[10] and for complete $m$-ary trees in ^[11]. Other results on the edge irregularity strength and its variations can be found in ^{[12,13,14,15]}.

The modular irregular labeling as a modification of the irregular assignment was introduced in ^[16]. A function $\psi: E(G) \to \{1, 2, \dots, k\}$ of a graph $G$ of order $n$ is called a modular irregular labeling if the weight function $\lambda: V(G) \to \mathbb Z_n$ defined by $\lambda(u) = wt_{\psi}(u) = \sum \psi(uv)$ is bijective and is called as the modular weight of the vertex $u$, where $\mathbb Z_n$ is the group of integers modulo $n$ and the sum is over all vertices $v$ adjacent to $u$. The modular irregularity strength, ${{\rm{ms}}}(G)$, is defined as the minimum $k$ for which $G$ has a modular irregular labeling using labels at most $k$. If there is no such labeling for the graph $G$ then the value of ${{\rm{ms}}}(G)$ is defined as $\infty$.

Clearly, every modular irregular labeling of a graph with no component of order at most two is also its irregular labeling. This gives a lower bound of the modular irregularity strength, i.e., if $G$ is a graph with no component of order at most two then

The exact values of the modular irregularity strength have been determined for certain families of graphs, namely for paths, cycles and stars ^[16], for fan graphs ^[17], wheels ^[18] and friendship graphs ^[19].

Motivated by the modular irregular labeling and the edge irregular labeling, in this paper we study modular edge irregular $k$-labelings.

For a graph $G = (V, E)$ of size $m$ we define a vertex labeling $\varphi: V(G) \to \{1, 2, \dots, k\}$ to be a modular edge irregular $k$-labeling if the edge-weight function $\rho: E(G) \to \mathbb Z_{m}$ defined by $\rho(uv) = wt_{\varphi}(uv) = \varphi(u) + \varphi(v)$ is bijective and is called as the modular edge-weight of the edge $uv$, where $\mathbb Z_{m}$ is the group of integers modulo $m$. The modular edge irregularity strength, ${{\rm{mes}}}(G)$, is defined as the minimum $k$ for which $G$ has a modular edge irregular $k$-labeling. If there is no such labeling for the graph $G$, then the value of ${{\rm{mes}}}(G)$ is defined as $\infty$.

Note that Muthugurupackiam and Ramya in ^[20,21] introduced a definition on even (odd) modular edge irregular labeling, where the set of modular edge-weights contains only even or odd integers.

The main aim of the paper is to show some estimations on the modular edge irregularity strength, investigate the existence of modular edge irregular $k$-labelings for several families of graphs and determine the precise values of the modular edge irregularity strength that prove the sharpness of the presented lower bound.

2.   Results

Directly from the definition it follows that every modular edge irregular $k$-labeling of a graph is also its edge irregular $k$-labeling. Thus, for any simple graph $G$ holds

In general, the converse of (2.1) does not hold. However, the validity of the following claim is obvious.

Theorem 2.1. Let $G$ be a simple graph with ${{\rm{es}}}(G) = k$. If edge-weights under the corresponding edge irregular $k$-labeling constitute a set of consecutive integers, then

In ^[9], the precise value of the edge irregularity strength for paths and stars are determined as follows:

Theorem 2.2. ^[9] Let $P_n$ be a path on $n$ vertices, $n\ge 2$. Then ${{\rm{es}}}(P_n) = \left\lceil \tfrac{n}{2}\right\rceil$.

Theorem 2.3. ^[9] Let $K_{1, n}$ be a star on $n+1$ vertices, $n\ge 1$. Then ${{\rm{es}}}(K_{1, n}) = n$.

The previous two theorems prove that the lower bound of the edge irregularity strength in (1.1) is tight. There is described the existence of the edge irregular $\left\lceil \tfrac{n}{2}\right\rceil$-labeling (for paths) and the existence of the edge irregular $n$-labeling (for stars), where the corresponding edge-weights in both cases constitute the set of consecutive integers. According to Theorem 2.1 we have:

Corollary 2.1. Let $P_n$ be a path on $n\ge 2$ vertices. Then ${{\rm{mes}}}(P_n) = \left\lceil \tfrac{n}{2}\right\rceil$.

Corollary 2.2. Let $K_{1, n}$ be a star on $n+1$ vertices, $n\ge 1$. Then ${{\rm{mes}}}(K_{1, n}) = n$.

These corollaries prove the tightness of the lower bound of the modular edge irregularity strength given in (2.1).

In the next theorem we characterize the modular edge irregularity strength of cycles.

Theorem 2.4. Let $C_n$ be a cycle on $n$ vertices, $n\ge 3$. Then

Proof. Let $V(C_n) = \{v_i: 1\le i\le n\}$ and $E(C_n) = \{v_iv_{i+1}:1\le i\le n\}$, where $v_{n+1} = v_1$. Faudree et al. in ^[22] described irregular assignments $f$ for cycles and proved that

We define a vertex labeling $\psi$ of $C_n$ such that for $1\le i\le n$

Thus each edge label becomes the vertex label and we get an edge irregular labeling of the cycle. Since for every $n\not\equiv 2\pmod 4$ in Faudree's irregular assignments of $C_n$ the vertex-weights constitute a set of consecutive integers then according to Theorem 2.1 it implies that

For the remaining case when $n\equiv 2\pmod 4$, i.e., $n = 4h+2$ for some positive integer $h\ge 1$, let us suppose that the cycle $C_{4h+2}$ admits a modular edge irregular labeling $\varphi$. It means that the sum of all vertex labels used to calculate the edge-weights of $C_{4h+2}$ is congruent to the sum of modular edge-weights. Hence

A contradiction as $2h+1$ is odd.

A caterpillar is a graph derived from a path by hanging any number of leaves from the vertices of the path. The caterpillar can be seen as a sequence of stars $K_{1, n_1} \cup K_{1, n_2} \cup \dots \cup K_{1, n_r}$, where each $K_{1, n_i}$ is a star with central vertex $c_i$ and $n_i$ leaves for $i = 1, 2, \dots, r$, and the leaves of $K_{1, n_i}$ include $c_{i-1}$ and $c_{i+1}$, for $i = 2, 3, \dots, r-1$. In ^[23] the authors denote the caterpillar as $S_{n_1, n_2, \dots, n_r}$, where the vertex set is $V(S_{n_1, n_2, \dots, n_r})$ = $\{ c_i: 1\le i\le r \} \cup \bigcup\limits_{i = 2}^{r-1} \{v_i^j: 2\le j\le n_i-1 \}$ $\cup \{v_1^j: 1\le j\le n_1-1 \} \cup \{v_r^j: 2\le j\le n_r \}$, and the edge set is $E(S_{n_1, n_2, \dots n_r}) = \{ c_ic_{i+1}: 1\le i\le r-1 \} \cup \bigcup\limits_{i = 2}^{r-1} \{c_iv_i^j: 2\le j\le n_i-1 \}$ $\cup \{c_1v_1^j:\; 1\le j\le n_1-1 \} \cup \{c_rv_r^j:\; 2\le j\le n_r \}$, see Figure 1. Thus $|V(S_{n_1, n_2, \dots, n_r})| = \sum\limits_{i = 1}^r n_i -r+2$ and $|E(S_{n_1, n_2, \dots, n_r})| = \sum\limits_{i = 1}^r n_i -r+1$.

Let $S_{n_1, n_2, \dots, n_r}$ be a caterpillar and $N_o = \sum\limits_{i = 1}^{\left\lceil \tfrac{r}{2}\right\rceil}n_{2i-1}$ and $N_e = \sum\limits_{i = 1}^{\left\lfloor \tfrac{r}{2}\right\rfloor}n_{2i}$.

Theorem 2.5. Let $k = \max\left\{N_o-\left\lceil \tfrac{r}{2}\right\rceil+1, N_e-\left\lfloor \tfrac{r}{2}\right\rfloor+1 \right\}$. The caterpillar $S_{n_1, n_2, \dots, n_r}$ admits a modular edge irregular $k$-labeling.

Proof. We are using an idea of Kotzig and Rosa ^[24] that any caterpillar can be realized in the plane so that its vertices are displaced in two rows, the edges joining these vertices from different rows and no two edges cross. Let $\{A, B\}$ be a bipartition of the vertex set of the caterpillar $S_{n_1, n_2, \dots, n_r}$. Let $a_1, a_2, \dots, a_{N_o-\left\lceil \frac{r}{2}\right\rceil +1}$ be the vertices in the partition $A$, ordered from left to right, and let $b_1, b_2, \dots, b_{N_e-\left\lfloor \frac{r}{2}\right\rfloor +1}$ be the vertices in the partition $B$, ordered from left to right.

Define a vertex labeling $\varphi$ of $S_{n_1, n_2, \dots, n_r}$ in the following way.

It is not complicated to see that the maximal vertex label is $k = \max\left\{N_o-\left\lceil \tfrac{r}{2}\right\rceil+1, N_e-\left\lfloor \tfrac{r}{2}\right\rfloor+1 \right\}$ and the edge-weights create the integer interval from $2$ to $|E(S_{n_1, n_2, \dots, n_r})| +1 = N_o+N_e -r+2$. Thus, the vertex labeling $\varphi$ is a modular edge irregular $k$-labeling.

Immediately from (1.1) and Theorem 2.5 we obtain the next theorem.

Theorem 2.6. Let $S_{n_1, n_2, \dots, n_r}$ be a caterpillar. Then

Note that if $r$ is even and $N_o = N_e+\alpha$, where $\alpha \in \{-1, 0, 1\}$, or if $r$ is odd and $N_o = N_e+\beta$, where $\beta\in \{0, 1, 2\}$ then

Thus we get the following result.

Corollary 2.3. Let $S_{n_1, n_2, \dots, n_r}$ be a caterpillar. If $r$ is even and $N_o = N_e+\alpha$, where $\alpha \in \{-1, 0, 1\}$, or if $r$ is odd and $N_o = N_e+\beta$, where $\beta\in \{0, 1, 2\}$ then

In compliance with (2.1) the previous corollary proves the sharpness of the lower bound of the modular edge irregularity strength of caterpillars.

Marr and Wallis in their book ^[25] define an $n$-sun $S_n$ as a cycle $C_n$ with an edge terminating in a vertex of degree $1$ attached to each vertex.

Theorem 2.7. Let $S_n$ be an $n$-sun on $2n$ vertices, $n\ge 3$. Then

Proof. Let $V(S_n) = \{v_i, u_i: 1\le i\le n\}$ and $E(S_n) = \{ v_iv_{i+1}, v_iu_i: 1\le i\le n\}$, where $v_{n+1} = v_1$. According to (1.1) and (2.1) we have the following lower bound $n+1\le {{\rm{es}}}(S_n)\le{{\rm{mes}}}(S_n)$. To prove that $n+1$ is also the upper bound we distinguish two cases according to the parity of $n$.

Case 1. For $n\ge 3$ odd, we construct a vertex labeling $\varphi$ as follows

The labels of vertices receive the integers from $1$ to $n+1$ and for the weights of edges we get

One can easily check that under the vertex labeling $\varphi$ the edges of the $n$-sun admit the consecutive weights from $2$ to $2n+1$. Thus, the vertex labeling $\varphi$ is a modular edge irregular $(n+1)$-labeling of $S_n$ for $n$ odd.

Case 2. For $n\ge 4$ even, we consider a vertex labeling $\psi$ defined such that

The maximal vertex labels is $n+1$ and the edge-weights are the following

Thus the weights of edges are consecutive numbers from $2$ to $2n+1$. This means that the vertex labeling $\psi$ is a modular edge irregular $(n+1)$-labeling of $S_n$ for $n$ even.

Thus

for every $n\ge 3.$

A friendship graph $f_n$, $n\ge 1$, is a set of $n$ triangles having a common central vertex, and otherwise disjoint. Let $w$ denote the central vertex. For the $i$th triangle, $1\le i\le n$, let $u_i$ and $v_i$ denote the other two vertices. Thus $f_n$ contains $2n+1$ vertices $w, u_i, v_i$, $1\le i\le n$ and $3n$ edges $wu_i$, $wv_i$, $u_iv_i$, $1\le i\le n$.

As $|E(f_n)| = 3n$ and the maximum degree $\Delta(f_n) = 2n$ then (1.1) implies that ${{\rm{es}}}(f_n) \ge 2n$. However, if under a vertex labeling $\varphi$ of $f_n$ there exist two vertices $u, v\in V(f_n)$ such that $\varphi(u) = \varphi(v)$ then using the fact that $u$ and $v$ have just one common neighbor, say $z\in V(f_n)$, we obtain $wt_{\varphi}(uz) = \varphi(u) + \varphi(z) = \varphi(v) + \varphi(z) = wt_{\varphi}(vz)$. It means that under any edge irregular labeling of the friendship graph $f_n$ all the vertex values must be different. That way

and according to (2.1) we also have a lower bound of the modular edge irregularity strength for $f_n$.

The following theorem shows that the lower bound of the edge irregularity strength of $f_n$ in (2.3) is acquired just for a few values of $n$. A similar idea of the proving was used in ^[26] for showing the edge-antimagicness of friendship graphs with difference $d = 1$.

Theorem 2.8. The friendship graph $f_n$ of order $2n+1$ admits an edge irregular $(2n+1)$-labeling with consecutive edge-weights if and only if $n\in \{1, 3, 4, 5, 7\}$.

Proof. Suppose that there exists a vertex labeling $\varphi: V(G) \to \{1, 2, \dots, 2n+1\}$ such that the edge-weights of $f_n$ successively attain consecutive values $x, x+1, \dots, x+3n-1$. If $\varphi(w) = t$, $1\le t\le\; 2n+1$, then the set of vertex labels under the vertex labeling $\varphi$ can be partitioned into three subsets $A = \{ 1, 2, \dots, t-1 \}$, $B = \{ t\}$ and $C = \{ t+1, t+2, \dots, 2n+1 \}$. Thus $\varphi(V(f_n)) = A\cup B\cup C$.

We are able to see that weights of edges $wu_i$ and $wv_i$, $1\le i\le n$, constitute the set $W$ = $\{t+1,$ $t+2, \dots, 2t-1, 2t+1, 2t+2, \dots, 2n+t+1\}$. It is not difficult to see that the set of edge-weights $W_A$ = $\{\; x, x+1, \dots, t \}$ can only be created as sums of two distinct values in the set $A$ and the set of edge-weights $W_B = \{ 2n+t+2, 2n+t+3, \dots, x+3n-1 \}$ can only be created as sums of two distinct values in the set $B$. The sets $W_A$ and $W_B$ contain consecutive integers each while the set $W$ has a gap. The missing edge-weight $2t$ can be obtained only as sum of a value from the set $A$, say $a$, and a value from the set $B$, say $b$. Thus in the set $A-\{a\}$ we have $t-2$ numbers and the corresponding set of edge-weights $W_A = \{ x, x+1, \dots, t \}$ has the cardinality $|W_A| = \frac{t-2}{2}$, i.e., $t$ must be even. This also implies that $x = \tfrac{t}{2}+2$.

Since the sum of all the values in the set $A-\{a\}$ is equal to the sum of all the edge-weights in the set $W_A = \{ \tfrac{t}{2}+2, \tfrac{t}{2}+3, \dots, t \}$, then

As $a\in A$ then $1\le a\le t-1$ and from (2.4) we get

which is equivalent to

As $t$ must be even the previous inequalities give

In the computation of the edge-weights of $f_n$, the label $t$ of the vertex $w$ is used $2n$ times and the labels of the vertices $u_i$ and $v_i$, $1\le i\le n$, are used twice each and the sum of the all edge-weights of $f_n$ is equal to the sum of all the vertex labels, used to calculate the edge-weights. Then we get the following equation

which gives

and it immediately follows that

According to (2.5) from the Eq (2.6) we receive all the possible integer values of the parameters $n$, $x$ and $t$ as follows:

For the converse, it is not difficult to find the corresponding edge irregular $(2n+1)$-labelings of $f_n$ for parameters $(n, x, t)$ from (2.7). Figures 2–4 illustrate searched $(2n+1)$-labelings of $f_n$, where integers in italic font represent the edge-weights. This concludes the proof.

Applying Theorem 2.1 to Theorem 2.8 we achieve the following corollary.

Corollary 2.4. Let $f_n$ be a friendship graph on $2n+1$ vertices. If $n\in \{1, 3, 4, 5, 7\}$ then ${{\rm{mes}}}(f_n) = 2n+1$.

The next theorem gives a condition when no modular edge irregular labeling of $f_n$ exists.

Theorem 2.9. If $f_n$ is a friendship graph on $2n+1$ vertices and $n \equiv 2 \pmod 4$, then $f_n$ has no modular edge irregular labeling and ${{\rm{mes}}}(f_n) = \infty$.

Proof. Assume that the friendship graph $f_n$ on $2n+1$ vertices admits a modular edge irregular labeling $\varphi$. Then the sum of all vertex labels used to calculate the edge-weights of $f_n$ is congruent to the sum of modular edge-weights. It means if $D = 2\sum\limits_{i = 1}^{n} \left(\varphi(u_i) + \varphi(v_i)\right) + 2n\varphi(w)$ then

where $\sum\limits_{s = 0}^{3n-1} s = \tfrac{3n(3n-1)}2$.

If $n \equiv 2 \pmod 4$, i.e., $n = 4h+2$ for some positive integer $h\ge 1$, then using properties of congruence we get

This contradicts the fact that $D$ is even.

The next theorem provides lower and upper bounds on the parameter ${{\rm{mes}}}(f_n)$ for $n$ odd.

Theorem 2.10. For the friendship graph $f_n$ of order $2n+1$, $n\ge 9$ odd, we have

Proof. The lower bound follows from (2.1) and (2.3). To see the upper bound let us define a vertex labeling $\varphi$ of $f_n$, for $n\ge 9$ odd, in the following way

Thus the labels of vertices $u_i, v_i$, $1\le i\le n$ are the consecutive integers from $1$ to $2n$ and the vertex $w$ receives the maximum label $\frac{5n+1}{2}$. Then for the weights of the edges $u_iv_i$, $1\le i\le n$, we have

and for the weights of the edges $wu_i$ and $wv_i$, $1\le i\le n$, we get

We can observe that the edge-weights of $f_n$, under the vertex labeling $\varphi$, form the sequence of consecutive integers $\frac{3n+3}{2}, \frac{3n+5}{2}, \dots, \frac{9n+1}{2}$.

In the light of Theorem 2.1, it follows that the vertex labeling $\varphi$ is a modular edge irregular $\frac{5n+1}{2}$-labeling of $f_n$ and it proves that ${{\rm{mes}}}(f_n) \le \frac{5n+1}{2}$ for $n\ge 9$ odd. Thus, we arrive at the desired result.

3.   Conclusions

In this paper is introduced a new graph invariant, namely the modular edge irregularity strength and estimated its lower bound. For several families of graphs (paths, stars, cycles and $n$-suns) are determined the precise values of the modular edge irregularity strength that prove the sharpness of this lower bound. For caterpillars $S_{n_1, n_2, \dots, n_r}$ realized in the plane as a balanced (respectively almost balanced) bipartite graph we proved that if $r$ is even and $N_o = N_e+\alpha$, where $\alpha \in \{-1, 0, 1\}$, or if $r$ is odd and $N_o = N_e+\beta$, where $\beta\in \{0, 1, 2\}$ then ${{\rm{mes}}}(S_{n_1, n_2, \dots, n_r}) = \left\lceil \tfrac{N_o+N_e-r+2}{2}\right\rceil$. For the other cases we proved only an upper bound for the modular edge irregularity strength. Therefore we propose the following open problem.

Open Problem 3.1. For the caterpillar $S_{n_1, n_2, \dots, n_r}$ determine the exact value of the modular edge irregularity strength for $N_o = N_e+\gamma$ for every integer $\gamma$.

For the friendship graph $f_n$ of order $2n+1$ was proved that

For further research, we suggest the following open problems.

Open Problem 3.2. For the friendship graph $f_n$ of order $2n+1$ and $n\ge 9$ odd, determine the exact value of the modular edge irregularity strength.

It is a matter of algebraic argumentation to show that there does not exist a modular edge irregular $17$-labeling of $f_8$. Thus according to Figure 5 we get that ${{\rm{mes}}}(f_8) = 18$. The remaining open case for the existence of a modular edge irregular labeling of $f_n$ is $n \equiv 0 \pmod 4$ for $n\ge 12$. Therefore we propose

Open Problem 3.3. For the friendship graph $f_n$ of order $2n+1$, $n\ge 12$ and $n \equiv 0 \pmod 4$, determine the exact value of the modular edge irregularity strength.

Acknowledgments

The research for this article was supported by the Slovak Research and Development Agency under the contract APVV-19-0153 and by VEGA 1/0243/23.

Conflict of interest

In this article, all authors disclaim any conflict of interest.