I Nengah Suparta^a , Made Candiasa^a , Wahyudi A. Prasancika^a , Martin Bacaˇ b

^aDepartment of Mathematics,

Faculty of Mathematics and Natural Sciences, Universitas Pendidikan Ganesha,

Jalan Udayana 11 Singaraja-Bali, Indonesia

^bDepartment of Appl. Mathematics and Informatics, Technical University,

Kosice, Slovak Republic ˇ

nengah.suparta@undiksha.ac.id, made.candiasa@undiksha.ac.id, wahyu.prasancika@undiksha.ac.id, martin.baca@tuke.sk

We solve the open problem posed in Modular irregularity strength of graphs, Electron. J. Graph Theory and Appl. 8 (2020), 435–433, asking about the modular irregularity strength of the complete graph Kⁿ for all n ≥ 3. Furthermore, we establish also the exact values of the modular irregularity strength of complete bipartite graphs Kn,n+^t for any positive integer n and t = 0, 1, 2.

Keywords: complete graph, complete bipartite graph, irregular labeling, modular irregularity strength Mathematics Subject Classification : 05C78

DOI: 10.5614/ejgta.2024.12.1.9

1. Introduction

Let G be a finite simple undirected graph. A mapping from a set of elements of G to a set of numbers is called a labeling for the graph G. The numbers (usually non-negative integers) which are in the range of the mapping are called labels. The name of labelings depend mainly on the domains of the mapping. In this paper we focus on edge labelings, labelings that have edge-set as their domain. Some specific type of edge labelings were introduced by Chartrand, Jacobson, Lehel, Oellerman, Ruiz and Saba in [6], where the label of every edge is a positive integer such that the sum of all edge labels incident to a vertex is different for all vertices. Such labelings are called

Received: 27 April 2021, Revised: 11 February 2024, Accepted: 20 February 2024.

irregular assignments. The irregularity strength of a graph G, denoted by s(G), is the minimum k for which a graph admits an irregular assignment using the number k as the largest edge label. There are a lot of results regarding with irregularity strength of graphs. Among them can be seen in [1, 2, 5, 7, 8, 9, 10, 11].

Irregularity strength of graphs inspired Bača, Muthugurupackiam, Kathiresan, Ramya in [4] to introduce a new graph parameter, so called modular irregularity strength which is explained in the following way.

Consider a graph G(V,E) of order n having no component of order 2. An edge labeling \(\tau: E(G) \to \{1,2,\ldots,k\}\), for some positive integer k, is called k-labeling of the graph G. Let \(Z_n\) be the set of integers modulo n and the function \(\sigma: V(G) \to Z_n\), be defined by

\[\sigma(u) = \sum \tau(uv),\]

over all vertices v adjacent to u. The value of \(\sigma(u)\) is called the modular weight of the vertex u. If \(\sigma\) is a bijective function, then the function \(\tau\) is called modular irregular k-labeling. Furthermore, the minimum k for which the graph G admits a modular irregular k-labeling is named the modular irregularity strength and is denoted by \(\operatorname{ms}(G)\). It is defined as \(\operatorname{ms}(G) = \infty\) in the case when there is no modular irregular labeling of G. As it is noted in [4], we can easily observe that irregularity strength of graph is defined only for graphs containing at most one isolated vertex and no connected component of order 2. Modular irregularity strength of some classes of graph has been established (see e.g. [3, 4, 12]).

For positive integers n and d, n > d, let us denote by \(Z_n^* := Z_n - \{0\}\) and let (n,d) be the greatest common divisor of n and d. From basic number theory we can immediately see that if (n,d) = 1, then \(\{\underline{d}, \underline{2d}, \underline{3d}, \ldots, \underline{(n-1)d}\} = Z_n^*\), where \(\underline{s}\) stands for the least residue of s modulo n. By using this equality, it is easy to see the following theorem.

Theorem 1.1. Let G = (V, E) be a graph of order n with s(G) = k. Assume that there exists an irregular assignment of G with edge values at most k, where weights of vertices form the set \(\{a, a+d, a+2d, \ldots, a+(n-1)d\}\) for some positive integers a and d < n. If (n, d) = 1, then s(G) = ms(G) = k.

If d=1 in the above theorem, we obtain the following corollary which was proposed as Lemma 2.2 in [4].

Corollary 1.1. Let G = (V, E) be a graph with no component of order \(\leq 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.

The modular irregularity strength of some graphs was recently established in [4]. There we can find the following results: For a path \(P_n\) of \(n \geq 3\) vertices, \(\operatorname{ms}(P_n) = \lceil \frac{n}{2} \rceil\) if \(n \not\equiv 2 \pmod 4\) and \(\operatorname{ms}(P_n) = \infty\) otherwise; For a star \(K_{1,n}\) of order n+1 with \(n \geq 2\), \(\operatorname{ms}(K_{1,n}) = n\) if \(n \equiv 0, 2 \pmod 4\), \(\operatorname{ms}(K_{1,n}) = n+1\) if \(n \equiv 3 \pmod 4\), and \(\operatorname{ms}(K_{1,n}) = \infty\) if \(n \equiv 1 \pmod 4\); For a cycle \(C_n\) of order \(n \geq 3\), \(\operatorname{ms}(C_n) = \lceil \frac{n}{2} \rceil\) if \(n \equiv 1 \pmod 4\), \(\operatorname{ms}(C_n) = \lceil \frac{n}{2} \rceil + 1\) if \(n \equiv 0, 3 \pmod 4\), and \(\operatorname{ms}(C_n) = \infty\) if \(n \equiv 2 \pmod 4\); For a gear graph \(G_n\) of order \(n \geq 3\), \(\operatorname{ms}(G_n) = \frac{n+2}{2}\)

if \(n \equiv 0 \pmod 2\), and \(\operatorname{ms}(G_n) = \infty\) if \(n \equiv 1 \pmod 2\); and for a triangular graph \(T_n\) of order 2n-1 with \(n \geq 2\), \(\operatorname{ms}(T_n) = \frac{n+4}{2}\) if \(n \equiv 0 \pmod 2\) and \(\operatorname{ms}(T_n) = \frac{n+3}{2}\) if \(n \equiv 1 \pmod 2\). For \(n \geq 3\) the gear graph \(G_n\) is constructed from the cycle \(C_n\) by replacing each edge of the cycle with a triangle \(C_3\). Whereas, the triangular graph \(T_n\), \(n \geq 2\), is constructed from the path on n vertices by replacing each edge of the path with a triangle \(C_3\).

At the closing discussion in [4], an open research problem is proposed which is about the modular irregularity strength of complete graph \(K_n\), \(n \ge 3\). In this paper we solve this problem. Besides, we also derive the modular irregularity strength of three families of complete bipartite graphs: \(K_{n,n}\), \(K_{n,n+1}\) and \(K_{n,n+2}\).

Before continuing to the discussion of our main results, we recall the following two theorems proved in [4]. The first of them gives a lower bound of the modular irregularity strength and the second of them gives a condition when no modular irregular labeling of a graph exists.

Theorem 1.2. [4] Let G be a graph with no component of order \(\leq 2\). Then

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

Theorem 1.3. [4] If G is a graph of order n, \(n \equiv 2 \pmod{4}\), then G has no modular irregular labeling i.e., \(\operatorname{ms}(G) = \infty\).

2. Main Results

A graph G(V, E) is called dense, if \(\frac{1}{2} < D(G) \le 1\), with

\[D(G) = \frac{2|E|}{|V|(|V|-1)},\tag{1}\]

and it is called sparse graph if \(0 \le D(G) \le \frac{1}{2}\).

For the complete graph \(K_n\), \(n \ge 2\), it is well known that \(|E(K_n)| = \binom{n}{2}\). Therefore, we have \(D(K_n) = 1\), and hence the graph \(K_n\) is dense.

Now, we observe the density of complete bipartite graphs. Let \(K_{n,n+t}\) be the complete bipartite graph of 2n + t vertices, \(0 \le t < n\). It is clear that \(|E(K_{n,n+t})| = n(n+t)\). Then, we have

\[D(K_{n,n+t}) = \frac{2(n(n+t))}{(2n+t)(2n+t-1)}\] \[= \frac{n(2n+t)}{(2n+t)(2n+t-1)} + \frac{nt}{(2n+t)(2n+t-1)}\] \[= \frac{n}{(2n+t-1)} + \frac{nt}{(2n+t)(2n+t-1)}\] \[\geq \frac{n}{2n+t} + \frac{nt}{(2n+t)(2n+t-1)}\] \[= \frac{2n^2 + 2nt - n}{(2n+t)(2n+t-1)}\] \[= \frac{2n^2 + 2nt - n}{4n^2 + 4nt - 2n - t}\] \[\geq \frac{2n^2 + 2nt - n}{4n^2 + 4nt - 2n} = \frac{1}{2}.\]

From the last inequality we conclude that the complete bipartite graph \(K_{n,n+t}\), with \(0 \le t < n\), is a dense graph.

Assume that \(K_{n,n+t}\) is the complete bipartite graph of 2n+t vertices, \(0 \le t < n\), with maximum degree \(\Delta(K_{n,n+t}) = n+t\) and \(\varphi\) is an irregular assignments. Let \(\mathrm{s}(K_{n,n+t}) = k\). Consider the weights of vertices in \(K_{n,n+t}\). The smallest among these weights is at least n. The largest weight must be at least \(n+|V(K_{n,n+t})|-1=3n+t-1\) and at most \(\Delta(K_{n,n+t})k=(n+t)k\). Thus, \(3n+t-1 \le (n+t)k\) and

\[k = s(K_{n,n+t}) \ge \left\lceil \frac{3n+t-1}{n+t} \right\rceil.\]

Evidently, \(s(K_{n,n+t}) \geq 3\) for t = 0, 1, 2.

2.1. The modular irregularity strength of complete graph \(K_n\)

Next theorem gives the precise value of the modular irregularity strength of complete graph \(K_n\), \(n \ge 3\), and presents a solution of the Problem 1 in [4].

Theorem 2.1. Let \(K_n\) be a complete graph on n vertices with \(n \geq 3\). Then

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

Proof. The exact value of the irregularity strength of complete graphs is determined in [6] and it is \(s(K_n) = 3\), \(n \ge 3\). According to Theorem 1.2 we have that \(ms(K_n) \ge 3\) for \(n \ge 3\).

Name the vertices of the complete graph \(K_n\) with \(v_1, v_2, \ldots, v_n\). Consider an edge labeling \(\phi: E(K_n) \to \{1, 2, 3\}\). Moreover, let matrix \(A = [a_{ij}]\) be the \((n \times n)\)-matrix whose entry \(a_{ij} = \phi(v_i v_j)\), and \(A_i\) be the ith row of the matrix A. Let us consider the following four cases, according to the order of the graph \(K_n\).

Case 1. \(n \equiv 0 \pmod{4}\). In this case, we set a function \(\phi\) as follows.

\[\begin{array}{rll} \phi(v_iv_i) &= 0, & \text{if } i=1,2,\ldots,n, \\ \phi(v_iv_j) &= 1, & \text{if } i+j \leq n+1, i \neq j, \\ \phi(v_iv_n) &= \phi(v_nv_i) &= 3, & \text{if } i = \frac{n+2}{2} \\ \phi(v_iv_{i+1}) &= \phi(v_{i+1}v_i) &= 3, & \text{if } \frac{n+4}{2} \leq i \leq n-2; i \text{ even, } n \geq 8, \\ \phi(v_iv_j) &= 2, & \text{otherwise.} \end{array}\]

Using the mapping \(\phi\) we can see the following properties of the matrix A:

(i) For every \(i, 1 \le i \le \frac{n}{2}\), \(A_i\) contains no integer 3, i-1 integers 2, and n-i integers 1. This implies that the weight of vertex \(v_i\), \(w(v_i)\), is equal to

\[w(v_i) = 3(0) + 2(i-1) + 1(n-i) = n+i-2.\]

(ii) For each \(i, \frac{n}{2} + 1 \le i \le n\), \(A_i\) contains exactly one integer 3, i - 3 integers 2, and n - i + 1 integers 1. Therefore the weight of vertex \(v_i, w(v_i)\), is equal to

\[w(v_i) = 3(1) + 2(i-3) + 1(n-i+1) = n+i-2.\]

From (i) and (ii) it follows that the weights of vertices \(v_i\), \(i=1,2,\ldots,n\), constitute the set of consecutive integers \(W=\{n-1,n,n+1,\ldots,\frac{3n}{2}-2,\frac{3n}{2}-1,\ldots,2n-2\}\).

Case 2. \(n \equiv 1 \pmod{4}\). Now, we define a function \(\phi\) in the following way.

\[\begin{array}{rcl} \phi(v_iv_i) &= 0, & \text{if } i=1,2,\ldots,n, \\ \phi(v_iv_j) &= 1, & \text{if } i+j \leq n+1, i \neq j, \\ \phi(v_iv_n) &= \phi(v_nv_i) &= 3, & \text{if } i=\frac{n+3}{2}, \\ \phi(v_iv_{i+1}) &= \phi(v_{i+1}v_i) &= 3, & \text{if } \frac{n+5}{2} \leq i \leq n-2, i \text{ odd, } n \geq 9, \\ \phi(v_iv_j) &= 2, & \text{otherwise.} \end{array}\]

Observe that under the previous labeling \(\phi\) from the matrix A follows:

(i) For every \(i, 1 \le i \le \frac{n+3}{2} - 1\), \(A_i\) has no integer 3, has i-1 integers 2 and n-i integers 1. Based on this condition, we obtain that the weight of vertex \(v_i, w(v_i)\), is equal to

\[w(v_i) = 3(0) + 2(i-1) + 1(n-i) = n+i-2.\]

(ii) For each \(i, \frac{n+3}{2} \le i \le n\), \(A_i\) consists of exactly one integer 3, i-3 integers 2, and n-i+1 integers 1. Hence, the weight of vertex \(v_i, w(v_i)\), is equal to

\[w(v_i) = 3(1) + 2(i-3) + 1(n-i+1) = n+i-2.\]

Again, from (i) and (ii), we can conclude that the set of weights of vertices of \(K_n\), namely \(W = \{n-1, n, n+1, \dots, \frac{3n-1}{2} - 1, \frac{3n-1}{2}, \dots, 2n-2\}\) contains n consecutive integers.

Case 3. \(n \equiv 3 \pmod{4}\). We construct a function \(\phi\) such that

\[\phi(v_i v_i) = 0, \text{ if } i = 1, 2, \dots, n, \phi(v_i v_j) = 1, \text{ if } i + j \le n, i \ne j, \phi(v_i v_j) = \phi(v_j v_i) = 3, \text{ if } \frac{n+1}{2} \le i \le \frac{3n-1}{4}; j = \frac{3(n+1)}{4}, \phi(v_i v_j) = 2, \text{ otherwise.}\]

In this case we describe weights of the vertices \(v_i\) as follows:

(i) For every \(i, 1 \le i \le \frac{n+1}{2} - 1\), \(A_i\) has no integer 3. But it has i integers 2 and n - i - 1 integers 1. This implies that for \(i, 1 \le i \le \frac{n+1}{2} - 1\), the weight of vertex \(v_i, w(v_i)\), is equal to

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

(ii) For all i in the set \(\{\frac{n+1}{2}, \frac{n+3}{2}, \dots, \frac{3n-1}{4}\}\), row \(A_i\) consists of exactly one integer 3, i-2 integers 2 and n-i integers 1. Therefore the weight of vertex \(v_i\) is equal to

\[w(v_i) = 3(1) + 2(i-2) + 1(n-i) = n+i-1.\]

(iii) If i runs over the set \(\{\frac{3n+7}{4}, \frac{3n+11}{4}, \dots, n\}\), row \(A_i\) consists only of n-i integers 1 and i-1 integers 2. This leads to the weight of vertex \(v_i\) as

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

(iv) For \(i = \frac{3n-1}{4} + 1 = \frac{3(n+1)}{4}\), \(A_i\) contains \(n - i = \frac{n-3}{4}\) integers 1, \(\frac{n-1}{2}\) integers 2, and \(\frac{n+1}{4}\) integers 3. This gives the following weight of vertex \(v_i\)

\[w(v_i) = 3(\frac{n+1}{4}) + 2(\frac{n-1}{2}) + 1(\frac{n-3}{4}) = 2n-1.\]

By combining the weight sets expressed in (i) - (iv), we get the set of weights of vertices of \(K_n\)

\[W = \{n, \dots, \frac{3(n-1)}{2}, \frac{3n-1}{2}, \dots, \frac{7n-5}{4}, \frac{7n-1}{4}, 2n-2, 2n-1\},\\]

which contains consecutive integers.

In any of the previous three cases we get a set of consecutive integers as the set of vertex weights of \(K_n\) and by Corollary 1.1 it proves that \(s(K_n) = ms(K_n) = 3\) for \(n \not\equiv 2 \pmod{4}\).

Case 4. \(n \equiv 2 \pmod{4}\). The result follows immediately from Theorem 1.3.

2.2. The modular Irregularity strength of \(K_{n,n}\)

In this section we derive the modular irregularity strength of \(K_{n,n}\) for every positive integer \(n \geq 2\).

Theorem 2.2. Let \(K_{n,n}\) be a complete bipartite graph on 2n vertices with \(n \geq 2\). Then

\[ms(K_{n,n}) = \begin{cases} 3, & \text{if } n \text{ is even,} \\ \infty, & \text{if } n \text{ is odd.} \end{cases}\]

Proof. Let U and V be the partitions of vertices of \(K_{n,n}\), say \(U = \{u_1, u_2, \dots, u_n\}\) and \(V = \{v_1, v_2, \dots, v_n\}\). We discuss the following three cases.

Case 1. Let n be odd, \(n \ge 3\). It is clear that in this case \(|V(K_{n,n})| \equiv 2 \pmod{4}\) and according to Theorem 1.3 the modular irregularity strength of \(K_{n,n}\) is infinity.

Case 2. Let n=2. For j=1,2 define a function \(\tau:E(K_{2,2})\to\{1,2,3\}\) as follows.

\[\tau(u_1v_j) = 1 \text{ and } \tau(u_2v_j) = j + 1.\]

The weights of the vertices \(u_1\), \(u_2\), \(v_1\) and \(v_2\) of the complete bipartite graph \(K_{2,2}\) under the labeling \(\tau\) admit the values

\[w(u_1) = \tau(u_1v_1) + \tau(u_1v_2) = 2,\]
\[w(u_2) = \tau(u_2v_1) + \tau(u_2v_2) = 5,\]
\[w(v_1) = \tau(u_1v_1) + \tau(u_2v_1) = 3,\]
\[w(v_2) = \tau(u_1v_2) + \tau(u_2v_2) = 4.\]

We can see that all edge labels are at most 3 and the vertex weights are consecutive.

Case 3. Let n be even, \(n \ge 4\). For \(1 \le i, j \le n\), we set an edge labeling \(\tau : E(K_{n,n}) \to \{1,2,3\}\) as follows.

\[\begin{array}{ll} \tau(u_2v_n) &= 2,\\ \tau(u_{n-1}v_1) &= 2,\\ \tau(u_iv_j) &= 2, & \text{if } i+j=n+1, i=\frac{n}{2}+1, \frac{n}{2}+2, \ldots, n\\ \tau(u_iv_j) &= 3, & \text{if } i+j>n+1, i=3,4, \ldots, n\\ \tau(u_iv_j) &= 1, & \text{otherwise.} \end{array}\]

We split the vertex set of \(K_{n,n}\) into four mutually disjoint subsets

\[\begin{split} &A = \{u_1, u_2, v_1, v_2\}, \\ &B = \{u_i : i = 3, 4, \dots, \frac{n}{2}\} \cup \{v_j : j = 3, 4, \dots, \frac{n}{2}\}, \\ &C = \{v_j : j = \frac{n}{2} + 1, \frac{n}{2} + 2, \dots, n - 2\} \cup \{u_i : i = \frac{n}{2} + 1, \frac{n}{2} + 2, \dots, n - 2\}, \\ &D = \{v_{n-1}, v_n, u_{n-1}, u_n\}. \\ &\text{Clearly, } A \cup B \cup C \cup D = V(K_{n,n}). \end{split}\]

Observe that under the edge labeling \(\tau\) the weights of the vertices

(i) from the set A are equal to

\[w(u_1) = \sum_{j=1}^{n} \tau(u_1 v_j) = \sum_{j=1}^{n} 1 = n,\] \[w(u_2) = \sum_{j=1}^{n-1} \tau(u_2 v_j) + \tau(u_2 v_n) = \sum_{j=1}^{n-1} 1 + 2 = n + 1,\] \[w(v_1) = \sum_{i=1}^{n-2} \tau(u_i v_1) + \sum_{i=n-1}^{n} \tau(u_i v_1) = \sum_{i=1}^{n-2} 1 + \sum_{i=n-1}^{n} 2 = n + 2,\] \[w(v_2) = \sum_{i=1}^{n-2} \tau(u_i v_2) + \tau(u_{n-1} v_2) + \tau(u_n v_2) = \sum_{i=1}^{n-2} 1 + 2 + 3 = n + 3,\]

and they create the corresponding set of weights \(W_A = \{n, n+1, n+2, n+3\}\).

(ii) from the set B admit the integers

\[w(u_i) = \sum_{j=1}^{n-i+1} \tau(u_i v_j) + \sum_{j=n-i+2}^{n} \tau(u_i v_j) = \sum_{j=1}^{n-i+1} 1 + \sum_{j=n-i+2}^{n} 3 = n + 2i - 2,\] \[w(v_j) = \sum_{i=1}^{n-j} \tau(u_i v_j) + \tau(u_{n-j+1} v_j) + \sum_{i=n-j+2}^{n} \tau(u_i v_j)\] \[= \sum_{i=1}^{n-j} 1 + 2 + \sum_{i=n-j+2}^{n} 3 = n + 2j - 1,\]

and they form the common set of consecutive integers \(W_B = \{n + 4, n + 5, n + 6, n + 7, \dots, 2n - 4, 2n - 3, 2n - 2, 2n - 1\}.\)

(iii) from the set C receive the integers

\[w(v_j) = \sum_{i=1}^{n-j+1} \tau(u_i v_j) + \sum_{i=n-j+2}^{n} \tau(u_i v_j)\] \[= \sum_{i=1}^{n-j+1} 1 + \sum_{i=n-j+2}^{n} 3 = n + 2j - 2,\] \[w(u_i) = \sum_{j=1}^{n-i} \tau(u_i v_j) + \tau(u_i v_{n-i+1}) + \sum_{j=n-i+2}^{n} \tau(u_i v_j)\] \[= \sum_{j=1}^{n-i} 1 + 2 + \sum_{j=n-i+2}^{n} 3 = n + 2i - 1,\]

and they are consecutive elements of the set \(W_C = \{2n, 2n + 1, 2n + 2, 2n + 3, \dots, 3n - 8, 3n - 7, 3n - 6, 3n - 5\}.\)

(iv) from the set D obtain the integers

\[w(v_{n-1}) = \sum_{i=1}^{2} \tau(u_{i}v_{n-1}) + \sum_{i=3}^{n} \tau(u_{i}v_{n-1}) = \sum_{i=1}^{2} 1 + \sum_{i=3}^{n} 3 = 3n - 4,\] \[w(v_{n}) = \tau(u_{1}v_{n}) + \tau(u_{2}v_{n}) + \sum_{i=3}^{n} \tau(u_{i}v_{n}) = 1 + 2 + \sum_{i=3}^{n} 3 = 3n - 3,\] \[w(u_{n-1}) = \sum_{j=1}^{2} \tau(u_{n-1}v_{j}) + \sum_{j=3}^{n} \tau(u_{n-1}v_{j}) = \sum_{j=1}^{2} 2 + \sum_{j=3}^{n} 3 = 3n - 2,\] \[w(u_{n}) = \tau(u_{n}v_{1}) + \sum_{j=2}^{n} \tau(u_{n}v_{j}) = 2 + \sum_{j=2}^{n} 3 = 3(n - 1) + 2 = 3n - 1,\]

and they create the associated set of weights \(W_D = \{3n-4, 3n-3, 3n-2, 3n-1\}\).

Evidently, all edge labels are at most 3 and the weights of the vertices form the resulting set \(W = W_A \cup W_B \cup W_C \cup W_D\) of consecutive integers. Thus the function \(\tau\) is the desired modular irregular 3-labeling.

2.3. The modular irregularity strength of \(K_{n,n+1}\)

We partition the vertex set of \(K_{n,n+1}\) into \(U = \{u_1, u_2, \dots, u_n\}\) and \(V = \{v_1, v_2, \dots, v_n, v_{n+1}\}\). Here we have \(E(K_{n,n+1}) = \{u_i v_j : 1 \le i \le n, 1 \le j \le n+1\}\).

It is clear that for all positive integers \(n \ge 1\) there is \(|V(K_{n,n+1})| = 2n + 1 \not\equiv 2 \pmod{4}\).

Theorem 2.3. Let \(K_{n,n+1}\) be a complete bipartite graph on 2n+1 vertices with \(n \ge 1\). Then

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

Proof. It is evident that \(ms(K_{1,2}) = 2\).

For \(n \ge 2\) define a mapping \(f: E(K_{n,n+1}) \to \{1,2,3\}\) as follows.

\[f(u_i v_j) = f(v_j u_i) = 1\] if \(i + j \le n + 1\),
\(f(u_i v_j) = f(v_j u_i) = 2\) if \(i + j = n + 2\),
\(f(u_i v_j) = f(v_j u_i) = 3\) otherwise.

Since

\[w(u_i) = \sum_{j=1}^{n-i+1} f(u_i v_j) + f(u_i v_{n-i+2}) + \sum_{j=n-i+3}^{n+1} f(u_i v_j) = \sum_{j=1}^{n-i+1} 1 + 2 + \sum_{j=n-i+3}^{n+1} 3 = n + 2i,\]

for \(1 \le i \le n\), so the vertex weights form the arithmetic sequence of difference 2 with the initial weight n + 2 and the last weight 3n.

For the weight of the vertex v¹ we get

\[w(v_1) = \sum_{i=1}^{n} f(u_i v_1) = \sum_{i=1}^{n} 1 = n\]

and for weights of the vertices v^j , j = 2, 3, . . . , n + 1, we have

\[w(v_j) = \sum_{i=1}^{n-j+1} f(u_i v_j) + f(u_{n-j+2} v_j) + \sum_{i=n-j+3}^{n} f(u_i v_j) = \sum_{i=1}^{n-j+1} 1 + 2 + \sum_{i=n-j+3}^{n} 3 = n + 2j - 3.\]

We can see that these vertex weights create the arithmetic sequence of difference 2 with the initial weight n + 1 and the last weight 3n − 1.

By combining both arithmetic sequences of vertex weights of difference 2 with w(v1) = n we obtain the resulting set of consecutive integers from n to 3n and according to Corollary 1.1 the function f is a suitable modular irregular 3-labeling and ms(Kn,n+1) = 3 for n ≥ 2.

2.4. The modular irregularity strength of Kn,n+2

Here, we partition the vertex set of Kn,n+2 into U = {u1, u2, . . . , un} and V = {v1, v2, . . . , vn, vn+1, vn+2}. Then for the edge set we have E(Kn,n+2) = {uiv^j : 1 ≤ i ≤ n, 1 ≤ j ≤ n + 2}.

Theorem 2.4. Let Kn,n+2 be a complete bipartite graph on 2n + 2 vertices with n ≥ 1. Then

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

Proof. In [4] is stated that for the graph K1,³ as a star on 4 vertices and with edge labels 1,2,3, the irregularity strength is 3. But this irregular 3-labeling is not modular. The modular irregularity strength of K1,³ is 4 with edge values 1,2 and 4.

On can see that for even positive integer n, |V (Kn,n+2)| ≡ 2 (mod 4) and according to Theorem 1.3 the modular irregularity strength of Kn,n+2 is infinity.

For n odd, n ≥ 3, we define a function g : E(Kn,n+2) → {1, 2, 3} in the following way

\[\begin{array}{ll} g(u_iv_j) = g(v_ju_i) = 1 & \text{if } i+j \leq n+1, \\ g(u_iv_j) = g(v_ju_i) = 1 & \text{if } i+j = n+2, i \leq n-3, \text{ and } i \text{ even}, \\ g(u_iv_j) = g(v_ju_i) = 2 & \text{if } n+2 \leq i+j \leq n+4, \text{ and } i \text{ odd}, \\ g(u_{n-1}v_j) = g(v_ju_{n-1}) = 2 & \text{if } j = 3,4, \\ g(u_iv_j) = g(v_ju_i) = 3 & \text{otherwise}. \end{array}\]

Let us split the vertex set of Kn,n+2 into five mutually disjoint subsets

\[A = \{u_1, u_{n-1}, v_1, v_2, v_3, v_4, v_{n+2}\},\\] \[B = \{u_i : i = 3, 5, 7, \dots, n-4, n-2, n\},\\] \[C = \{u_i : i = 2, 4, 6, \dots, n-5, n-3\},\\]

\[D = \{v_j : j = 5, 7, 9, \dots, n - 4, n - 2, n\},\\] \[E = \{v_j : j = 6, 8, 10, \dots, n - 3, n - 1, n + 1\}.\] Clearly, \(A \cup B \cup C \cup D \cup E = V(K_{n,n+2}).\)

Observe that under the edge labeling g the weights of the vertices

(i) from the set A are equal to

\[w(u_1) = \sum_{j=1}^{n} g(u_1 v_j) + \sum_{j=n+1}^{n+2} g(u_1 v_j) = n + 4,\] \[w(u_{n-1}) = \sum_{j=1}^{2} g(u_{n-1} v_j) + \sum_{j=3}^{4} g(u_{n-1} v_j) + \sum_{j=5}^{n+2} g(u_{n-1} v_j)\] \[= 1 \cdot (2) + 2 \cdot (2) + 3 \cdot (n - 2) = 3n,\] \[w(v_1) = \sum_{i=1}^{n} g(u_i v_1) = 1 \cdot (n) = n,\] \[w(v_2) = \sum_{i=1}^{n-1} g(u_i v_2) + g(u_n v_2) = 1 \cdot (n - 1) + 2 = n + 1,\] \[w(v_3) = \sum_{i=1}^{n-2} g(u_i v_3) + \sum_{i=n-1}^{n} g(u_i v_3) = 1 \cdot (n - 2) + 2 \cdot (2) = n + 2,\] \[w(v_4) = \sum_{i=1}^{n-3} g(u_i v_4) + \sum_{i=n-2}^{n} g(u_i v_4) = 1 \cdot (n - 3) + 2 \cdot (3) = n + 3,\] \[w(v_{n+2}) = g(u_1 v_{n+2}) + \sum_{i=2}^{n} g(u_i v_{n+2}) = 2 + 3 \cdot (n - 1) = 3n - 1,\]

and they create the corresponding set of weights \(W_A = \{n, n+1, n+2, n+3, n+4, 3n-1, 3n\}\).

(ii) from the set B admit the integers

\[w(u_i) = \sum_{j=1}^{n-i+1} g(u_i v_j) + \sum_{j=n-i+2}^{n-i+4} g(u_i v_j) + \sum_{j=n-i+5}^{n+2} g(u_i v_j)\]
= 1 \cdot (n - i + 1) + 2 \cdot (3) + 3 \cdot (i - 2) = n + 2i + 1,

and they form the set of members of arithmetic sequence of difference 4, \(W_B = \{n+7, n+11, n+15, \ldots, 3n-7, 3n-3, 3n+1\}\).

(iii) from the set C receive the integers

\[w(u_i) = \sum_{j=1}^{n-i+1} g(u_i v_j) + g(u_i v_{n-i+2}) + \sum_{j=n-i+3}^{n+2} g(u_i v_j)\]
= 1 \cdot (n - i + 1) + 1 + 3 \cdot i = n + 2i + 2,

and they create the associated set of members of arithmetic sequence of difference 4, \(W_C = \{n+6, n+10, n+14, \dots, 3n-12, 3n-8, 3n-4\}.\)

(iv) from the set D obtain the integers

\[w(v_j) = \sum_{i=1}^{n-j+1} g(u_i v_j) + g(u_{n-j+2} v_j) + g(u_{n-j+3} v_j) + \sum_{i=n-j+4}^{n} g(u_i v_j)\]
= 1 \cdot (n-j+1) + 1 + 2 + 3 \cdot (j-3) = n + 2j - 5.

and they form the set of members of arithmetic sequence of difference 4, \(W_D = \{n+5, n+9, n+13, \ldots, 3n-13, 3n-9, 3n-5\}\).

(v) from the set E receive the integers

\[w(v_j) = \sum_{i=1}^{n-j+1} g(u_i v_j) + g(u_{n-j+2} v_j) + g(u_{n-j+3} v_j) + g(u_{n-j+4} v_j) + \sum_{i=n-j+5}^{n} g(u_i v_j)\]
= 1 \cdot (n-j+1) + 2 + 3 + 2 + 3 \cdot (j-4) = n + 2j - 4,

and they create the associated set of members of arithmetic sequence of difference 4, \(W_E = \{n+8, n+12, n+16, \dots, 3n-10, 3n-6, 3n-2\}.\)

Indeed, all edge labels are at most 3 and combining the previous sets of weights we obtain the resulting set \(W = W_A \cup W_B \cup W_C \cup W_D \cup W_E\) of consecutive integers. Thus the function g is the desired modular irregular 3-labeling and we are done.

3. Discussion

We solved a very small portion of the modular irregularity strength of complete bipartite graphs. The rest is still unsolved therefore for further investigation we propose the following problem.

Problem 1. For the complete bipartite graphs \(K_{n,n+t}\), \(n \ge 1\), \(3 \le t < n\), determine the exact value of the modular irregularity strength.

It seems to be interesting to investigate the modular irregularity strength of the complete tripartite graphs \(K_{m,n,s}\) for \(m,n,s\geq 1\). We conclude the paper with the following open problem.

Problem 2. For the complete tripartite graphs \(K_{m,n,s}\), \(m,n,s \geq 1\), determine the exact value of the modular irregularity strength.

Acknowledgement

We express our gratitude to anonymous referees who have contributed to the final version of this paper. The first author thanks to Universitas Pendidikan Ganesha for the DIPA grant provided to conduct this research, and the last author thanks to Slovak Research and Development Agency for the grant No. VEGA 1/0243/23.

References

• [1] M. Aigner and E. Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math. 3 (1990), 439–449.
• [2] M. Anholcer and C. Palmer, Irregular labellings of circulant graphs, Discrete Math. 312 (2012), 3461–3466.
• [3] M. Bača, Z. Kimáková, M. Lascsáková, and A. Semaničová-Feňovčíková, The irregularity and modular irregularity strength of fan graphs, Symmetry 13(4) (2021), 605, 13 pages.
• [4] M. Bača, K. Muthugurupackiam, K.M. Kathiresan, and S. Ramya, Modular irregularity strength of graphs, Electron. J. Graph Theory Appl. 8 (2) (2020), 435–433.

• [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] A. Frieze, R.J. Gould, M. Karonski, and F. Pfender, On graph irregularity strength, J. Graph Theory 41 (2002), 120–137.
• [8] 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.
• [9] P. Majerski and J. Przybylo, On the irregularity strength of dense graphs, SIAM J. Discrete Math. 28 (1) (2014), 197–205.
• [10] T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13 (2000), 313–323.
• [11] J. Przybylo, Irregularity strength of regular graphs, Electron. J. Combin. 15 (2008), R82.
• [12] K.A. Sugeng, P. John, M.L. Lawrence, L.F. Anwar, M. Baca, and A. Semani ˇ cov ˇ a-´ Fenov ˇ cˇ´ıkova, Modular irregularity strength on some flower graphs, ´ Electron. J. Graph Theory Appl., 11 (1) (2023), 27–38.