Martin Bacaˇ a , K. Muthugurupackiam^b , KM. Kathiresan^c , S. Ramya^d

martin.baca@tuke.sk, gurupackiam@yahoo.com, kathir2esan@yahoo.com, manoramya.8036@gmail.com

We introduce a modular irregularity strength of graphs as modification of the well-known irregularity strength. We obtain some estimation on modular irregularity strength and determine the exact values of this parameter for five families of graphs.

Keywords: irregular labeling, modular irregular labeling, irregularity strength, modular irregularity strength.

Mathematics Subject Classification : 05C78

DOI: 10.5614/ejgta.2020.8.2.19

1. Introduction

By a labeling we mean any mapping that maps a set of graph elements to a set of numbers (usually positive integers), called labels. If the domain is the vertex-set or the edge-set, the labelings are called respectively vertex labelings or edge labelings. Other domains are possible. Graph theory terminology not included here can be found in [15] and recent survey of graph labeling is [10].

A graph or multigraph is called irregular if no two of its vertices have the same degree. It is well-known (see [4]) that no simple graph can have each vertex bearing a distinct degree. Multigraphs however can display this property. In [6], it is shown that for every graph G, having at most one isolate and no component isomorphic to K2, there exists an irregular multigraph H containing G as its underlying graph. Then the strength of irregular multigraph H is the maximum number of

Received: 17 June 2016, Revised: 27 March 2020, Accepted: 14 June 2020.

^aDepartment of Appl. Mathematics and Informatics, Technical University, Kosice, Slovak Republic ˇ

^bDepartment of Mathematics, Rajah Serfoji Government College, Thanjavur, India

^cDepartment of Mathematics, Ayya Nadar Janaki Ammal College, Sivakasi, India

^dDepartments of Mathematics, Bharathidasan University Constituent College, Orathanadu, India

edges that join some pair of vertices. In many research papers is investigated the minimum strength of an irregular multigraph that contains a given graph G as the underlying graph.

Chartrand, Jacobson, Lehel, Oellermann, Ruiz and Saba in [6] introduced labelings of the edges of a graph G with positive integers such that the sum of the labels of edges incident with a vertex is different for all the vertices. Such labelings were called irregular assignments and the irregularity strength of a graph G, denoted by s(G), is known as the minimum k for which G has an irregular assignment using labels at most k.

Thus the irregularity strength s(G) can be interpreted as the smallest integer k for which graph G can be turned into a multigraph H by replacing each edge by a set of at most k parallel edges, such that the degrees of the vertices in multigraph H are all different.

It is easy to see that irregularity strength s(G) of a graph G is defined only for graphs containing at most one isolated vertex and no connected component of order 2.

The lower bound of the parameter s(G) is given in [6] by the following inequality

\[s(G) \ge \max_{1 \le i \le \Delta} \left\{ \frac{n_i + i - 1}{i} \right\},\tag{1}\]

where \(n_i\) denotes the number of vertices of degree i and \(\Delta\) is the maximum degree of graph G. In the case of d-regular graphs of order n it reduces to

\[s(G) \ge \frac{n+d-1}{d}\].

The conjecture stated in [6] says that the value of s(G) is for every graph equal to the above lower bound plus some constant not depending on G.

In [1] is proved that if G is a connected graph of order n then \(s(G) \le n-1\), and \(s(G) \le n+1\) otherwise. Later Nierhoff [13] showed that for all graphs different from \(K_3\) with finite irregularity strength, \(s(G) \le n-1\). This bound is tight. It can be seen e.g. for stars.

For upper bound of the irregularity strength Faudree and Lehel [8] showed that if G is d-regular, \(d \geq 2\), then \(\mathrm{s}(G) \leq \left\lceil \frac{n}{2} \right\rceil + 9\), and they conjectured that \(\mathrm{s}(G) \leq \left\lceil \frac{n}{d} \right\rceil + c\) for some constant c. Przybylo in [14] proved that \(\mathrm{s}(G) \leq 16\frac{\mathrm{n}}{\mathrm{d}} + 6\). Kalkowski, Karonski and Pfender [11] showed that \(\mathrm{s}(G) \leq 6\frac{n}{\delta} + 6\), where \(\delta\) is the minimum degree of graph G. Currently Majerski and Przybylo [12] proved that \(\mathrm{s}(G) \leq (4+o(1))\frac{n}{\delta} + 4\) for graphs with minimum degree \(\delta \geq \sqrt{n} \ln n\). Other interesting results on the irregularity strength can be found in [3, 5, 9].

Inspired by the irregularity strength of the graph we introduce a new graph parameter, a modular irregularity strength. The modular irregularity strength of graph naturally arise in the study of modular version of irregularity strength.

Let G = (V, E) be a graph of order n with no component of order n. An edge k-labeling \(\psi : E(G) \to \{1, 2, \ldots, k\}\) is called modular irregular k-labeling of the graph n if there exists a bijective weight function n: n: n: n: n: n: n: n

\[\sigma(x) = \sum \psi(xy)\]

called modular weight of the vertex x, where \(Z_n\) is the group of integers modulo n and the sum is over all vertices y adjacent to x.

The minimum k for which the graph G admits a modular irregular k-labeling is called the modular irregularity strength of a graph G and denoted by ms(G). If there does not exist a modular irregular k-labeling for G, we define ms(G) = ∞.

In this paper we establish a lower bound of the modular irregularity strength and determine the exact values of this parameter for five families of graphs.

2. Results

Directly from the definition of modular irregular k-labeling it follows:

Lemma 2.1. Let G = (V, E) be a graph with no component of order 2. Every modular irregular k-labeling of G is also its irregular assignment.

In general, the converse of Lemma 2.1 does not hold. Moreover, it is easy to see the following:

Lemma 2.2. Let G = (V, E) be a graph with no component of order ≤ 2 and let s(G) = k. If there exists an irregular assignment of G with edge values at most k, where weights of vertices constitute a set of consecutive integers, then

\[s(G) = ms(G) = k.\]

For the star on 4 vertices, the irregularity strength is 3. On the other hand, the modular irregularity strength of K1,³ is 4 with edge values 1,2 and 4. Thus s(K1,3) = 3 < ms(K1,3) = 4. For the path P³ the irregularity strength is equal to the modular irregularity strength with edge values 1 and 2.

According to Lemmas 2.1 and 2.2 we get a lower bound on the modular irregularity strength.

Theorem 2.1. Let G = (V, E) be a graph with no component of order ≤ 2. Then

\[s(G) \le ms(G)\].

Theorem 2.2. If G is a graph of order n, n ≡ 2 (mod 4), then G has no modular irregular k-labeling i.e., ms(G) = ∞.

Proof. Let G be a graph of order n. Suppose n ≡ 2 (mod 4), then n = 4k + 2 for some integer k. Assume that G has a modular irregular k-labeling and let e1, e2, e3, ..., e^m be the edge labels of G. Now

\[\sum \sigma(x) \equiv 0 + 1 + 2 + \dots + (n - 1) \pmod{n}\] \[\equiv \frac{n(n - 1)}{2} \pmod{n}\] \[\equiv \frac{(4k + 2)(4k + 1)}{2} \pmod{n}\] \[\equiv (2k + 1)(4k + 2 - 1) \pmod{4k + 2}\] \[\equiv (2k + 1)(-1) \pmod{4k + 2}.\] \[\equiv (2k + 1) \pmod{4k + 2}.\] (2)

Further more,

\[\sum \sigma(x) \equiv 2(e_1 + e_2 + e_3 + \dots + e_m) \pmod{n}\] Which is a contraction to equation (2).

In [6] it is shown that if Pⁿ is the path of order n then

\[s(P_n) = \begin{cases} \frac{n}{2}, & \text{if } n \equiv 0 \pmod{4}, \\ \frac{n+1}{2}, & \text{if } n \equiv 1, 3 \pmod{4}, \\ \frac{n+2}{2}, & \text{if } n \equiv 2 \pmod{4}. \end{cases}\] (3)

The next theorem gives the precise value of the modular irregularity strength for paths Pn.

Theorem 2.3. Let Pⁿ be a path of order n ≥ 3. Then

\[\operatorname{ms}(P_n) = \begin{cases} \left\lceil \frac{n}{2} \right\rceil, & \text{if } n \not\equiv 2 \pmod{4}, \\ \infty, & \text{if } n \equiv 2 \pmod{4}. \end{cases}\]

Proof. Let V (Pn) = {vⁱ : i = 1, 2, . . . , n} be the vertex set and E(Pn) = {eⁱ = vivi+1 : i = 1, 2, . . . , n − 1} be the edge set of the path Pn.

Case (i). Suppose that n ≡ 0, 3 (mod 4) and construct the edge labeling ψ¹ : E(Pn) → {1, 2, . . . , dn/2e} such that

\[\psi_1(e_i) = i, \text{ if } 1 \le i \le \left\lceil \frac{n}{2} \right\rceil,\]

\[\psi_1(e_{n-i}) = \begin{cases} i+1, & \text{if } i \text{ is odd}, \ 1 \le i \le \left\lfloor \frac{n}{2} \right\rfloor - 1, \\ i, & \text{if } i \text{ is even}, \ 2 \le i \le \left\lfloor \frac{n}{2} \right\rfloor - 1. \end{cases}\]

It is easy to check that the edge values under the labeling ψ¹ are at most dn/2e and the weights of vertices constitute the set of consecutive integers {1, 2, . . . , n}. With respect to (3) and Lemma 2.2, s(Pn) = ms(Pn) = dn/2e.

Case (ii). Let n ≡ 1 (mod 4). Define the edge labeling ψ² : E(Pn) → {1, 2, . . . , dn/2e} such that

\[\psi_2(e_i) = \begin{cases} 2, & \text{if } i = 1, \\ i, & \text{if } 2 \le i \le \left\lceil \frac{n}{2} \right\rceil, \end{cases}\]

\[\psi_2(e_{n-i}) = \begin{cases} i+2, & \text{if } i \text{ is odd, } 1 \le i \le \left\lfloor \frac{n}{2} \right\rfloor - 1, \\ i+1, & \text{if } i \text{ is even, } 2 \le i \le \left\lfloor \frac{n}{2} \right\rfloor - 1. \end{cases}\]

By direct computation, we obtain that the weights of vertices constitute the sequence of consecutive integers {2, 3, . . . , n + 1}. Again according to (3) and Lemma 2.2, s(Pn) = ms(Pn) = dn/2e. By theorem 2, ms(Pn) = ∞, n ≡ 2 (mod 4).

Amar and Togni [2] proved that the irregularity strength s(T) of any tree T with no vertex of degree 2 is equal to its number of leaves. Thus for stars \(K_{1,n}\) on n+1 vertices we have that \(s(K_{1,n})=n\). The next theorem gives the modular irregularity strength for \(K_{1,n}\), \(n \geq 2\).

Theorem 2.4. Let \(K_{1,n}\) be a star of order n+1, \(n \geq 2\). Then

\[\operatorname{ms}(K_{1,n}) = \begin{cases} n, & \text{if } n \equiv 0, 2 \pmod{4}, \\ n+1, & \text{if } n \equiv 3 \pmod{4}, \\ \infty, & \text{if } n \equiv 1 \pmod{4}. \end{cases}\]

Proof. Let \(V(K_{1,n}) = \{u, v_1, v_2, \dots, v_n\}\) and \(E(K_{1,n}) = \{uv_1, uv_2, \dots, uv_n\}\) be the vertex set and edge set of the star \(K_{1,n}\) respectively.

Case (i). If \(n \equiv 0, 2 \pmod 4\) then we define the edge labeling \(\varphi_1 : E(K_{1,n}) \to \{1, 2, \dots, n\}\) such that

\[\varphi_1(uv_i) = i\], for \(1 \le i \le n\).

Then under the labeling \(\varphi_1\) the weights of vertices \(v_i\) successively attain the values \(1, 2, 3, \ldots, n\) and weight of the vertex u is \(w_{\varphi_1}(u) = \frac{n(n+1)}{2} \equiv 0 \pmod{n+1}\). Thus modular weights are \(0, 1, 2, \ldots, n\) which implies that \(\operatorname{ms}(K_{1,n}) = n, n \geq 2\).

Case (ii). If \(n \equiv 3 \pmod 4\) then we construct the edge labeling \(\varphi_2 : E(K_{1,n}) \to \{1, 2, \dots, n+1\}\) such that

\[\varphi_2(uv_i) = \begin{cases} i, & \text{if } 1 \le i \le n \text{ and } i \ne \frac{n+1}{4}, \\ n+1, & \text{if } i = \frac{n+1}{4}. \end{cases}\]

It is true that \(w_{\varphi_2}(v_i)=i\) for \(1\leq i\leq n\) and \(i\neq\frac{n+1}{4},\) \(w_{\varphi_2}(v_{(n+1)/4})=n+1\) and \(w_{\varphi_2}(u)=\frac{(n+1)(2n+3)}{4}\equiv\frac{n+1}{4}\pmod{n+1}.\) Hence modular weights are \(0,1,2,\ldots,n\) and this implies that \(\operatorname{ms}(K_{1,n})=n+1,\) \(n\geq 3.\) By theorem 2, \(\operatorname{ms}(K_{1,n})=\infty,\) when \(n\equiv 1\pmod{4}.\)

A triangular graph \(T_n\), \(n \ge 2\), is a graph constructed from the path on n vertices by replacing each edge of the path by a triangle \(C_3\). Let \(V(T_n) = \{v_i : 1 \le i \le n\} \cup \{u_i : 1 \le i \le n-1\}\) and \(E(T_n) = \{v_i v_{i+1} : 1 \le i \le n-1\} \cup \{u_i v_i, u_i v_{i+1} : 1 \le i \le n-1\}\) be the vertex set and edge set of \(T_n\) respectively. The next theorem gives the exact values of the modular irregularity strength for the triangular graph.

Theorem 2.5. Let \(T_n\) be a triangular graph of order 2n-1, \(n \geq 2\). Then

\[ms(T_n) = \begin{cases} \frac{n+4}{2}, & \text{if } n \text{ is even,} \\ \frac{n+3}{2}, & \text{if } n \text{ is odd.} \end{cases}\]

Proof. Let us distinguish two cases.

Case (i). Assume that n is odd. For n = 3 define an edge labeling µ¹ in the following way:

\[\mu_1(u_iv_i)=1, \quad \text{for } i=1,2,\] \[\mu_1(u_iv_{i+1})=2i-1, \quad \text{for } i=1,2,\] \[\mu_1(v_iv_{i+1})=2, \quad \text{for } i=1,2.\]

One can see that the edge values under the labeling µ¹ are 1, 2 and 3 and the weights of vertices are 2, 3, 4, 5 and 6. According to Lemma 2.2, s(T3) = ms(T3) = 3.

For n ≥ 5 we construct the following edge labeling µ2:

\[\mu_2(v_iv_{i+1}) = \begin{cases} \frac{n+3}{2}, & \text{if } i \text{ is odd } 1 \leq i \leq n, \\ \frac{n-3}{2}, & \text{if } i = 2, \\ \frac{n-1}{2}, & \text{if } i \text{ is even } 4 \leq i \leq n-3, \\ \frac{n+1}{2}, & \text{if } i = n-1, \end{cases}\]

\[\mu_2(u_i v_i) = \begin{cases} \frac{n+3-2i}{2}, & \text{if } 1 \le i \le \frac{n+1}{2}, \\ \frac{2i-n-1}{2}, & \text{if } \frac{n+3}{2} \le i \le n-1, \end{cases}\]

\[\mu_2(u_i v_{i+1}) = \begin{cases} \frac{n+3-2i}{2}, & \text{if } 1 \le i \le \frac{n+1}{2}, \\ \frac{2i-n+1}{2}, & \text{if } \frac{n+3}{2} \le i \le n-1. \end{cases}\]

The weights of vertices are all distinct and constitute the set of consecutive integers {2, 3, 4, . . . , 2n}. Since 2n − 1 ≡ 0 (mod 2n − 1) and 2n ≡ 1 (mod 2n − 1) then the modular weights are 0, 1, 2, . . . , 2n − 2. One can observe that the labeling µ² is the requested modular irregular (n + 3)/2-labeling.

Case (ii). Suppose that n is even. Define an edge labeling µ³ such that

\[\mu_3(v_i v_{i+1}) = \begin{cases} \frac{n+4}{2}, & \text{if } i \text{ is odd } 1 \le i \le n-1, \\ \frac{n-2}{2}, & \text{if } i \text{ is even } 2 \le i \le n, \end{cases}\]

\[\mu_3(u_i v_i) = \begin{cases} \frac{n+2-2i}{2}, & \text{if } 1 \le i \le \frac{n}{2}, \\ \frac{2i-n+2}{2}, & \text{if } \frac{n+2}{2} \le i \le n-1, \end{cases}\]

\[\mu_3(u_iv_{i+1}) = \begin{cases} \frac{n+2-2i}{2}, & \text{if } 1 \le i \le \frac{n-2}{2}, \\ \frac{2i-n+4}{2}, & \text{if } \frac{n}{2} \le i \le n-1. \end{cases}\]

The edge labels under the labeling µ³ are at most (n + 4)/2 and weights of vertices successively attain the values 3, 4, 5, . . . , 2n + 1. Thus modular weights are 0, 1, 2, . . . , 2n − 2 and µ³ is a modular irregular labeling having the required property.

In [7] Faudree et. al., determined the irregularity strength of cycle Cⁿ of order n as follows:

\[s(C_n) = \begin{cases} \left\lceil \frac{n}{2} \right\rceil, & \text{if } n \equiv 1 \pmod{4}, \\ \left\lceil \frac{n}{2} \right\rceil + 1, & \text{otherwise.} \end{cases}\] (4)

The next theorem gives the exact value of the modular irregularity strength for cycle Cn.

Theorem 2.6. Let Cⁿ be a cycle of order n, n ≥ 3. Then

\[\operatorname{ms}(C_n) = \begin{cases} \left\lceil \frac{n}{2} \right\rceil, & \text{if } n \equiv 1 \pmod{4}, \\ \left\lceil \frac{n}{2} \right\rceil + 1, & \text{if } n \equiv 0, 3 \pmod{4}, \\ \infty, & \text{if } n \equiv 2 \pmod{4}. \end{cases}\]

Proof. Let V (Cn) = {vⁱ : 1 ≤ i ≤ n} and E(Cn) = {vivi+1 : 1 ≤ i ≤ n} where vn+1 = v1, be the vertex set and edge set of the cycle Cⁿ respectively.

Then we define the edge labeling α : E(Cn) → {1, 2, . . . , k} where k = n 2 when n ≡ 1 (mod 4) and k = n 2 + 1 when n ≡ 0, 3 (mod 4), such that

\[\alpha(v_i v_{i+1}) = i, \text{ for } 1 \le i \le \left\lceil \frac{n}{2} \right\rceil.\]

\[\alpha(v_{n-i+1}v_{n-i+2}) = \begin{cases} 2\left\lfloor\frac{i}{2}\right\rfloor + 1, & \text{if } n \equiv 0,1 \pmod{4}, \\ 2\left\lceil\frac{i}{2}\right\rceil + 1, & \text{if } n \equiv 3 \pmod{4}, \end{cases} \text{ for } 1 \leq i \leq \left\lfloor\frac{n}{2}\right\rfloor.\]

Under the labeling α, we obtain that the weights of vertices of Cⁿ are consecutive integers {2, 3, . . . , n + 1} when n ≡ 0, 1 (mod 4) and {3, 4, . . . , n + 2} when n ≡ 3 (mod 4). Again according to (4) and Lemma 2.2, s(Cn) = ms(Cn), n 6≡ 2 (mod 4). By theorem 2, ms(Cn) = ∞, when n ≡ 2 (mod 4).

For n ≥ 3, a gear graph Gn, is a graph constructed from the cycle Cⁿ by replacing each edge of the cycle by a triangle C3. Let V (Gn) = {uⁱ , vⁱ : 1 ≤ i ≤ n} and E(Gn) = {vivi+1 : 1 ≤ i ≤ n − 1} ∪ {uivⁱ , uivi+1 : 1 ≤ i ≤ n − 1} ∪ {unvn, vnv1, unv1} be the vertex set and edge set of Gⁿ respectively . The following theorem gives the exact values of the modular irregularity strength for the gear graph.

Theorem 2.7. Let Gⁿ be a gear graph of order 2n, n ≥ 3. Then

\[ms(G_n) = \begin{cases} \frac{n+2}{2}, & \text{if } n \text{ is even,} \\ \infty, & \text{if } n \text{ is odd.} \end{cases}\]

Proof. Assume that n is even, n ≥ 4. We define the edge labeling β : E(Gn) → {1, 2, . . . , n ² + 1}, such that

\[\beta(v_i u_i) = \begin{cases} 1, & \text{for } i = 1, \\ i - 1, & \text{for } 2 \le i \le \frac{n}{2} + 1. \end{cases}\]

Modular irregularity strength of graphs | Martin Bača et al.

\[\beta(u_i v_{i+1}) = i\], for \(1 \le i \le \frac{n}{2} + 1\).

\[\beta(u_{n+1-i}v_{n+1-i}) = i+1\], for \(1 \le i \le \frac{n}{2} - 1\).

\[\beta(u_{n-i}v_{n+1-i}) = i+2\], for \(1 \le i \le \frac{n}{2} - 2\).

\[\beta(u_n v_1) = 2.\]

\[\beta(v_i v_{i+1}) = \frac{n}{2}\], for \(1 \le i \le n\).

Under the labeling \(\beta\) the weights of vertices \(u_i, \ 1 \leq i \leq n\) are \(2, 3, \ldots, n+1\) and weights of the vertices \(v_i, \ 1 \leq i \leq n\) are \(n+2, n+3, \ldots, 2n+1\), here \(w_\beta(v_{\frac{n}{2}+1}) = 2n \equiv 0 \pmod{2n}\), \(w_\beta(v_{\frac{n}{2}+2}) = 2n+1 \equiv 1 \pmod{2n}\). Thus \(\beta\) is a desired modular irregular \((\frac{n}{2}+1)\)-labeling of \(G_n\). By theorem 2, \(\operatorname{ms}(G_n) = \infty\), when n is odd.

There are many families of graphs for which modular irregularity strength is not known. We conclude with the following open problems for further investigation.

Problem 1. Determine the modular irregularity of complete graph \(K_n\), \(n \geq 3\).

Problem 2. Characterize the graph for which modular irregularity strength is strictly greater than the irregularity strength.

Acknowledgement

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

References

• [1] M. Aigner and E. Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math. 3 (1990), 439–449.
• [2] D. Amar and O. Togni, Irregularity strength of trees, Discrete Math. 190 (1998), 15–38.
• [3] M. Anholcer, and C. Palmer, Irregular labellings of circulant graphs, Discrete Math. 312 (2012), 3461–3466.
• [4] M. Behzad and G. Chartrand, No graph is perfect, Amer. Math. Monthly 74 (1967), 962–963.
• [5] T. Bohman and D. Kravitz, On the irregularity strength of trees, J. Graph Theory 45 (2004), 241–254.

• [6] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz, and F. Saba, Irregular networks, Congr. Numer. 64 (1988), 187–192.
• [7] R.J. Faudree, M.S. Jacobson, J. Lehel, and R.H. Schlep, Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete Math. 76 (1988), 223–240.
• [8] R.J. Faudree, and J. Lehel, Bound on the irregularity strength of regular graphs, Combinatorica 52 (1987), 247–256.
• [9] A. Frieze, R.J. Gould, M. Karonski, and F. Pfender, On graph irregularity strength, J. Graph Theory 41 (2002), 120–137.
• [10] J. Gallian, A dynamic survey of graph labeling, The Electronic J. Combin. 19 (2012), #DS6.
• [11] M. Kalkowski, M. Karonski, and F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math. 25(3) (2011), 1319–1321.
• [12] P. Majerski and J. Przybylo, On the irregularity strength of dense graphs, SIAM J. Discrete Math. 28(1) (2014), 197–205.
• [13] T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13 (2000), 313–323.
• [14] J. Przybylo, Irregularity strength of regular graphs, Electron. J. Combin. 15 (2008), R82.
• [15] D.B. West, An Introduction to Graph Theory, Prentice-Hall, 1996.