Non-inclusive and inclusive distance irregularity strength for the join product of graphs

Faisal Susanto^∗a , Kristiana Wijaya^a , I Wayan Sudarsana^b , Slamin^c

^aGraph Combinatorics and Algebra Research Group, Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Jember, Indonesia ^bAlgebra and Combinatorics Research Group, Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Tadulako, Indonesia ^cDepartment of Informatics, Faculty of Computer Sciences, Universitas Jember, Indonesia

faisalsusanto16@gmail.com, kristiana.fmipa@unej.ac.id, sudarsanaiw1972@gmail.com, slamin@unej.ac.id

A function φ : V (G) → {1, 2, . . . , k} of a simple graph G is said to be a non-inclusive distance vertex irregular k-labeling of G if the sums of labels of vertices in the open neighborhood of every vertex are distinct and is said to be an inclusive distance vertex irregular k-labeling of G if the sums of labels of vertices in the closed neighborhood of each vertex are different. The minimum k for which G has a non-inclusive (resp. an inclusive) distance vertex irregular k-labeling is called a non-inclusive (resp. an inclusive) distance irregularity strength and is denoted by dis(G) (resp. by dis( ^{c G})). In this paper, the non-inclusive and inclusive distance irregularity strength for the join product graphs are investigated.

Keywords: vertex k-labeling, non-inclusive distance irregularity strength, inclusive distance irregularity strength, join product Mathematics Subject Classification : 05C78

DOI: 10.5614/ejgta.2022.10.1.1

Received: 8 February 2021, Revised: 19 June 2021, Accepted: 15 August 2021.

^∗ corresponding author

1. Introduction

All graphs considered here are assumed to be simple, finite and undirected. Let G be a graph with vertex-set V(G) = V and edge-set E(G) = E. For a vertex \(v \in V\), the degree of v, denoted by \(\deg_G(v)\), is the number of vertices adjacent to v. The open and closed neighborhood of v is defined as \(N_G(v) = \{u : uv \in E\}\) and \(N_G[v] = \{v\} \cup N_G(v)\), respectively. The maximum degree of vertices in G is denoted by \(\Delta(G)\). By graph labeling we mean any mapping that carries some sets of graph elements to a set of non-negative integers, called labels. There are many types of graph labelings that have been developed. A survey of recent results on graph labelings is provided by Gallian [8].

Let k be a positive integer and let a graph G be given. A function \(\phi: V \to \{1, 2, \dots, k\}\) is said to be a non-inclusive distance vertex irregular k-labeling of G if the weights are distinct for every pair of two distinct vertices, where the weight of a vertex v is defined as the sum of labels of vertices in the open neighborhood of v in G. The non-inclusive distance irregularity strength of G, denoted by dis(G), is the minimum integer k for which G has a non-inclusive distance vertex irregular klabeling. Furthermore, the labeling \(\phi\) is called an inclusive distance vertex irregular k-labeling of G if for each two vertices u and v, there is \(wt_{\phi}(u) = \sum_{x \in N_G[u]} \phi(x) \neq \sum_{y \in N_G[v]} \phi(y) = wt_{\phi}(v)\). The least integer k for which G has an inclusive distance vertex irregular k-labeling is called the inclusive distance irregularity strength, \(\operatorname{dis}(G)\). We will say that \(\operatorname{dis}(G) = \infty\) and \(\operatorname{dis}(G) = \infty\)whenever such a non-inclusive and an inclusive distance vertex irregular labeling does not exist, respectively.

The notion of non-inclusive distance vertex irregular labelings was intoduced in 2017 by Slamin [13]. Meanwhile, Bača et al. [3] developed inclusive distance vertex irregular labelings one year later as a variation of the non-inclusive irregularity strength of graphs. These graph invariants are then generalized by Bong et al. [5] to non-inclusive and inclusive d-distance irregularity strength of graphs where d is an integer arbitrarily taken from 1 up to diameter of the graph. Thus, a non-inclusive 1-distance vertex irregular labeling is called a non-inclusive distance vertex irregular labeling. Similarly, we call an inclusive 1-distance vertex irregular labeling as an inclusive distance vertex irregular labeling.

A number of research results on non-inclusive and inclusive d-distance irregularity strengths have been found as seen in [3, 4, 11, 13, 14, 15, 16, 17] when d = 1 and in [5, 18] when d > 1. In the literature, it was investigated the total version of this concept, see [19, 20]. Furthermore, related topics on the subjects can also be found in, for example, [1, 6, 9], and for some new results, see [2, 10, 12].

The following lemmas give the necessary and sufficient condition for a graph G to have finite dis(G) and dis(G).

Lemma 1.1. [7] Let G be a graph. Then \(\operatorname{dis}(G) < \infty\) if and only if \(N_G(u) \neq N_G(v)\) for every two vertices \(u, v \in V\).

Lemma 1.2. [3] Let G be a graph. Then \(\widehat{\operatorname{dis}}(G) < \infty\) if and only if \(N_G[u] \neq N_G[v]\) for every two vertices \(u, v \in V\).

In the present paper, we deal with a so-called product of graphs namely a join product. The join product of two graphs G and H, denoted by \(G \oplus H\), is a graph obtained from G and H by

joining an edge from each vertex of G to each vertex of H. We represent the vertex-set of \(G \oplus H\) with \(V(G \oplus H) = V(G) \cup V(H)\) and the edge-set with \(E(G \oplus H) = E(G) \cup E(H) \cup \{uv : u \in V(G), v \in V(H)\}\). We here consider the following problems.

Problem 1. Given two graphs G and H with dis(G) and dis(H), respectively, what is the value of \(dis(G \oplus H)\) going to be?

Problem 2. Similarly, if two graphs G and H with \(\widehat{dis}(G)\) and \(\widehat{dis}(H)\), respectively, are given, what is the value of \(\widehat{dis}(G \oplus H)\) going to be?

Using Lemma 1.1, it is easy to show that \(\operatorname{dis}(G \oplus H) = \infty\) if and only if either \(\operatorname{dis}(G)\) or \(\operatorname{dis}(H)\) is infinite. Also, it is not hard to show, by Lemma 1.2, that \(\widehat{\operatorname{dis}}(G \oplus H) = \infty\) if and only if one of the following statements holds:

• (i) either \(\widehat{\mathrm{dis}}(G)\) or \(\widehat{\mathrm{dis}}(H)\) is infinite; or
• (ii) both \(\Delta(G) = |V(G)| 1\) and \(\Delta(H) = |V(H)| 1\).

Thus, in the rest of the paper, we will only deal with the case when \(\operatorname{dis}(G \oplus H) < \infty\) and \(\widehat{\operatorname{dis}}(G \oplus H) < \infty\).

We need to define some notations related to the non-inclusive distance irregularity strength of graphs as follows. Let G and H be graphs with \(\operatorname{dis}(G) < \infty\) and \(\operatorname{dis}(H) < \infty\). Let \(\phi_G\) and \(\phi_H\) be a non-inclusive distance vertex irregular \(\operatorname{dis}(G)\)-labeling of G and a non-inclusive distance vertex irregular \(\operatorname{dis}(H)\)-labeling of H, respectively. For a vertex \(v \in V(G)\) and a non-negative integer \(\alpha\), we define an \(\alpha\)-weight of v under a labeling \(\phi_G\) of a graph G as

\[wt^{\alpha}_{\phi_G}(v) = wt_{\phi_G}(v) + \alpha \deg_G(v).\]

We denote by \(v_{\max}^{\alpha}\) a vertex of G in such away that \(wt_{\phi_G}^{\alpha}(v_{\max}^{\alpha}) = \max \left\{ wt_{\phi_G}^{\alpha}(v) : v \in V(G) \right\}\). Analogously, we write \(v_{\min}^{\alpha}\) to mean a vertex of G for which \(wt_{\phi_G}^{\alpha}(v_{\min}^{\alpha}) = \min \left\{ wt_{\phi_G}^{\alpha}(v) : v \in V(G) \right\}\). For a special \(\alpha = 0\), we will use \(wt_{\phi_G}(v)\), \(wt_{\phi_G}(v_{\max})\) and \(wt_{\phi_G}(v_{\min})\) instead of \(wt_{\phi_G}^{0}(v)\), \(wt_{\phi_G}^{0}(v_{\max}^{0})\) and \(wt_{\phi_G}^{0}(v_{\min}^{0})\), respectively. Further, we also consider positive integers \(\beta_G\) and \(\gamma_{G,H}\) such that

\[\beta_G = \max\left\{1, \max\left\{\left\lfloor \frac{wt_{\phi_G}(u_i) - wt_{\phi_G}(u_j)}{\deg_G(u_j) - \deg_G(u_i)}\right\rfloor + 1 : u_i, u_j \in V(G)\right\}\right\}\](1)

and

\[\gamma_{G,H} = \max \left\{ \beta_G, \left[ \frac{wt_{\phi_G}(u_{\max}^{\beta_G}) - wt_{\phi_H}(v_{\min}) + \sum_{v \in V(H)} \phi_H(v) - \sum_{u \in V(G)} \phi_G(u)}{|V(G)| - \Delta(G)} \right] + 1 \right\}, \tag{2}\]

respectively.

With respect to the inclusive distance irregularity strength, we shall also define some notations as follows. Given two graphs G and H with \(\widehat{\mathrm{dis}}(G) < \infty\) and \(\widehat{\mathrm{dis}}(H) < \infty\), let \(\widehat{\phi}_G\) and \(\widehat{\phi}_H\) be an inclusive distance vertex irregular \(\widehat{\mathrm{dis}}(G)\)-labeling of G and an inclusive distance vertex irregular \(\widehat{\mathrm{dis}}(H)\)-labeling of G, respectively. Let \(\widehat{\alpha}\) be a non-negative integer. We define an \(\widehat{\alpha}\)-weight of a vertex G of G under a labeling G of a graph G as

\[wt_{\widehat{\phi}_G}^{\widehat{\alpha}}(v) = wt_{\widehat{\phi}_G}(v) + (\deg_G(v) + 1)\widehat{\alpha}.\]

Then we denote by \(v_{\max}^{\widehat{\alpha}}\) a vertex of G in such away that \(wt_{\widehat{\phi}_G}^{\widehat{\alpha}}(v_{\max}^{\widehat{\alpha}}) = \max \left\{ wt_{\widehat{\phi}_G}^{\widehat{\alpha}}(v) : v \in V(G) \right\}\). Similarly, we also write \(v_{\min}^{\widehat{\alpha}}\) to stand for a vertex of G in which \(wt_{\widehat{\phi}_G}^{\widehat{\alpha}}(v_{\min}^{\widehat{\alpha}}) = \min \left\{ wt_{\widehat{\phi}_G}^{\widehat{\alpha}}(v) : v \in V(G) \right\}\). In particular, when \(\widehat{\alpha} = 0\), we will use, respectively, \(wt_{\widehat{\phi}_G}(v)\), \(wt_{\widehat{\phi}_G}(v_{\max})\) and \(wt_{\widehat{\phi}_G}(v_{\min})\) instead of \(wt_{\widehat{\phi}_G}^0(v)\), \(wt_{\widehat{\phi}_G}^0(v_{\max}^0)\) and \(wt_{\widehat{\phi}_G}^0(v_{\min}^0)\). Moreover, we also define positive integers \(\widehat{\beta}_G\) and \(\widehat{\gamma}_{G,H}\) such that

\[\widehat{\beta}_G = \max\left\{1, \max\left\{\left\lfloor \frac{wt_{\widehat{\phi}_G}(u_i) - wt_{\widehat{\phi}_G}(u_j)}{\deg_G(u_j) - \deg_G(u_i)}\right\rfloor + 1 : u_i, u_j \in V(G)\right\}\right\}\] (3)

and

\[\widehat{\gamma}_{G,H} = \max \left\{ \widehat{\beta}_G, \left\lfloor \frac{wt_{\widehat{\phi}_G}(u_{\max}^{\widehat{\beta}_G}) - wt_{\widehat{\phi}_H}(v_{\min}) + \sum_{v \in V(H)} \widehat{\phi}_H(v) - \sum_{u \in V(G)} \widehat{\phi}_G(u)}{|V(G)| - (\Delta(G) + 1)} \right\rfloor + 1 \right\}, \tag{4}\]

respectively.

Let x and y be two given integers. Then we define

\[\frac{x}{y} = \begin{cases} \frac{x}{y}, & \text{if } y \neq 0, \\ 0, & \text{otherwise.} \end{cases}\]

2. \(\operatorname{dis}(G \oplus H)\) and \(\widehat{\operatorname{dis}}(G \oplus H)\)

In this section, we give the construction of the non-inclusive and inclusive distance vertex irregular labeling for the join product graphs. Our basic idea is to construct a new non-inclusive distance vertex irregular labeling for the join product graphs \(G \oplus H\) from the described non-inclusive distance vertex irregular labeling of G and G. Similar ideas are then used to construct the inclusive distance vertex irregular labeling of the join product graphs \(G \oplus H\).

Our first result below provides the lower bound of the non-inclusive distance irregularity strength for the join product of two graphs in terms of dis(G) and dis(H).

Lemma 2.1. Let G and H be graphs such that \(dis(G \oplus H) < \infty\). Then

\[dis(G \oplus H) \ge max\{dis(G), dis(H)\}.\]

Proof. We first show that there is no non-inclusive distance vertex irregular k-labeling of a graph \(G \oplus H\) such that \(k < \operatorname{dis}(G)\). Suppose to the contrary that such labeling \(\phi\) exists, that is, a labeling \(\phi : V(G \oplus H) \to \{1, 2, \dots, k\}\) is a non-inclusive distance vertex irregular k-labeling of \(G \oplus H\). Since each vertex of G is adjacent to all the vertices of G and since all the vertices of G have distinct weights then if we subtract from all these weights the sum of labels of all vertices of G, it gives us a restriction of the labeling G on the graph G which is a non-inclusive distance vertex irregular G-labeling of G for some G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-labeling of G-lab

Next we prove that there is no non-inclusive distance vertex irregular k-labeling \(\phi\) of a graph \(G \oplus H\) such that \(k < \operatorname{dis}(H)\). Using similar arguments with the previous case we can obtain a restriction of the labeling \(\phi\) on the graph H which is a non-inclusive distance vertex irregular k''-labeling of H with \(k'' \le k\), giving a contradiction as \(k'' \le k < \operatorname{dis}(H)\).

The following lemma gives the sufficient condition for \(\alpha\)-weights of all vertices in a graph to be different.

Lemma 2.2. Let G be a graph with \(\operatorname{dis}(G) < \infty\) and let \(\phi\) be a non-inclusive distance vertex irregular \(\operatorname{dis}(G)\)-labeling of G. Let \(\beta_G\) be an integer defined in (1). Then for any integer \(\alpha \geq \beta_G\) and every two distinct vertices \(u, v \in V(G)\), \(wt^{\alpha}_{\phi}(u) \neq wt^{\alpha}_{\phi}(v)\). Moreover, if \(\deg_G(u) < \deg_G(v)\) then \(wt^{\alpha}_{\phi}(u) < wt^{\alpha}_{\phi}(v)\).

Proof. For some \(\alpha'\) and some \(u', v' \in V(G)\), \(u' \neq v'\), if \(wt_{\phi}^{\alpha'}(u') = wt_{\phi}(u') + \alpha' \deg_G(u') = wt_{\phi}(v') + \alpha' \deg_G(v') = wt_{\phi}^{\alpha'}(v')\) then

\[\alpha' = \frac{wt_{\phi}(u') - wt_{\phi}(v')}{\deg_G(v') - \deg_G(u')}.\]

However, on the other hand, as \(\alpha' \geq \beta_G\), we have

\[\alpha' \ge \max \left\{ \left\lfloor \frac{wt_{\phi}(u) - wt_{\phi}(v)}{\deg_G(v) - \deg_G(u)} \right\rfloor + 1 : u, v \in V(G) \right\}\] \[\ge \left\lfloor \frac{wt_{\phi}(u') - wt_{\phi}(v')}{\deg_G(v') - \deg_G(u')} \right\rfloor + 1 > \frac{wt_{\phi}(u') - wt_{\phi}(v')}{\deg_G(v') - \deg_G(u')},\]

which gives us a contradiction. This proves the first part of the statement.

Next we prove the second part of the statement. Here we use the similar technique as the first part. Thus we suppose to the contrary that for some \(\alpha'\) and some \(u', v' \in V(G)\), \(u' \neq v'\), with \(\deg_G(u') < \deg_G(v')\), there is \(wt_{\phi}^{\alpha'}(u') = wt_{\phi}(u') + \alpha' \deg_G(u') > wt_{\phi}(v') + \alpha' \deg_G(v') = wt_{\phi}^{\alpha'}(v')\). Then \(wt_{\phi}(u') > wt_{\phi}(v')\) and

\[\alpha' < \frac{wt_{\phi}(u') - wt_{\phi}(v')}{\deg_G(v') - \deg_G(u')}.\]

However, on the other hand, as \(\alpha' \geq \beta_G\), we obtain

\[\alpha' \ge \left| \frac{wt_{\phi_G}(u') - wt_{\phi_G}(v')}{\deg_G(v') - \deg_G(u')} \right| + 1 > \frac{wt_{\phi_G}(u') - wt_{\phi_G}(v')}{\deg_G(v') - \deg_G(u')},\]

again a contradiction.

Notice that the property in Lemma 2.2 implies that for any integer \(\alpha \geq \beta_G\), \(wt_{\phi}(v_{\max}^{\alpha}) = wt_{\phi}(v_{\max}^{\beta_G})\). Next, as \(\gamma_{G,H} \geq \beta_G\), the following property is satisfied according to Lemma 2.2.

Corollary 2.1. Let G and H be graphs such that \(\operatorname{dis}(G \oplus H) < \infty\), and let \(\phi_G\) and \(\phi_H\) be a non-inclusive distance vertex irregular \(\operatorname{dis}(G)\)-labeling of G and a non-inclusive distance vertex irregular \(\operatorname{dis}(H)\)-labeling of G, respectively. Let \(\beta_G\) and \(\gamma_{G,H}\) be integers defined in (1) and (2), respectively. Then for any two distinct vertices \(u, v \in V(G)\), \(wt_{\phi_G}^{\gamma_{G,H}}(u) \neq wt_{\phi_G}^{\gamma_{G,H}}(v)\).

The value of the non-inclusive distance irregularity strength for \(G \oplus H\) is given in the following theorem.

Theorem 2.1. Let G and H be graphs such that dis(G ⊕ H) < ∞, and let φ^G and φ^H be a non-inclusive distance vertex irregular dis(G)-labeling of G and a non-inclusive distance vertex irregular dis(H)-labeling of H, respectively. If either

(i) \[\sum_{u \in V(G)} \phi_G(u) - \sum_{v \in V(H)} \phi_H(v) < wt_{\phi_G}(u_{\min}) - wt_{\phi_H}(v_{\max})\] or

(ii) \[\sum_{u \in V(G)} \phi_G(u) - \sum_{v \in V(H)} \phi_H(v) > wt_{\phi_G}(u_{\text{max}}) - wt_{\phi_H}(v_{\text{min}}),\]

then

\[\operatorname{dis}(G \oplus H) = \max\{\operatorname{dis}(G), \operatorname{dis}(H)\}.\]

Otherwise,

\[\operatorname{dis}(G \oplus H) \leq \min\{\max\{\operatorname{dis}(G),\operatorname{dis}(H) + \gamma_{H,G}\},\max\{\operatorname{dis}(H),\operatorname{dis}(G) + \gamma_{G,H}\}\}.\]

Proof. We distinguish our proof into two cases.

Case 1. \[\sum_{u \in V(G)} \phi_G(u) - \sum_{v \in V(H)} \phi_H(v) < wt_{\phi_G}(u_{\min}) - wt_{\phi_H}(v_{\max})\] or \(\sum_{u \in V(G)} \phi_G(u) - \sum_{v \in V(H)} \phi_H(v) > wt_{\phi_G}(u_{\max}) - wt_{\phi_H}(v_{\min})\).

Put k = max{dis(G), dis(H)}. Due to Lemma 2.1 it is enough to show that there exists a non-inclusive distance vertex irregular k-labeling of G ⊕ H. Let ϕ be a labeling on the vertices of G ⊕ H defined as follows.

\[\varphi(v) = \phi_G(v)\] if \(v \in V(G)\),

\[\varphi(v) = \phi_H(v)\] if \(v \in V(H)\).

Obviously the largest label appearing on the vertices under the labeling ϕ is k and the weights of the vertices are given by

\[wt_{\varphi}(v) = wt_{\phi_G}(v) + \sum_{u \in V(H)} \phi_H(u) \quad \text{if } v \in V(G),\]
\[wt_{\varphi}(v) = wt_{\phi_H}(v) + \sum_{u \in V(G)} \phi_G(u) \quad \text{if } v \in V(H).\]

We show that the vertex weights are distinct for every two vertices u, v ∈ V (G ⊕ H). If both u and v are in V (G) (resp. V (H)) then wtϕ(u) 6= wtϕ(v) as wt^φG (u) 6= wt^φG (v) (resp. wt^φH (u) 6= wt^φH (v)).

We now suppose that u ∈ V (G) and v ∈ V (H). The condition (i) implies that wtϕ(vmax) < wtϕ(umin) which means that wtϕ(u) 6= wtϕ(v). Similarly, the restriction (ii) implies that wtϕ(umax) < wtϕ(vmin) meaning that wtϕ(u) 6= wtϕ(v).

Case 2. wt^φG (umin) − wt^φH (vmax) ≤ P u∈V (G) φG(u) − P v∈V (H) φH(v) ≤ wt^φG (umax) − wt^φH (vmin).

Put k = min{k1, k2} where k¹ = max{dis(G), dis(H)+γH,G} and k² = max{dis(H), dis(G)+ γG,H}. We define a vertex k1-labeling ϕ¹ of G ⊕ H as follows.

\[\varphi_1(v) = \phi_G(v)\] if \(v \in V(G)\),

\[\varphi_1(v) = \phi_H(v) + \gamma_{H,G}\] if \(v \in V(H)\).

Clearly the labels used on the labeling \(\varphi_1\) are at most \(k_1\). For the vertex weights we have

\[wt_{\varphi_1}(v) = wt_{\phi_G}(v) + \sum_{u \in V(H)} \phi_H(u) + |V(H)|\gamma_{H,G} \qquad \text{if } v \in V(G),\]
\[wt_{\varphi_1}(v) = wt_{\phi_H}(v) + \sum_{u \in V(G)} \phi_G(u) + \gamma_{H,G} \deg_H(v) \qquad \text{if } v \in V(H).\]

We show that for every two distinct vertices u and v of \(G \oplus H\), \(wt_{\varphi_1}(u) \neq wt_{\varphi_1}(v)\). If \(u,v \in V(G)\), clearly, \(wt_{\varphi_1}(u) \neq wt_{\varphi_1}(v)\) as \(wt_{\varphi_G}(u) \neq wt_{\varphi_G}(v)\). Assume \(u,v \in V(H)\). Applying \(\beta_H\) and \(\gamma_{H,G}\) to Corollary 2.1, we can obtain that \(wt_{\varphi_H}(u) + \gamma_{H,G} \deg_H(u) \neq wt_{\varphi_H}(v) + \gamma_{H,G} \deg_H(v)\) meaning that \(wt_{\varphi_1}(u) \neq wt_{\varphi_1}(v)\). We now consider \(u \in V(G)\) and \(v \in V(H)\). It suffices for us to show that \(wt_{\varphi_1}(u_{\min}) > wt_{\varphi_1}(v_{\max})\). As \(\gamma_{H,G} \geq \beta_H\), by Lemma 2.2, \(wt_{\varphi_H}(v_{\max}^{\gamma_{H,G}}) = wt_{\varphi_H}(v_{\max}^{\beta_H})\). Using these informations together with the facts that

\[\gamma_{H,G} \ge \left| \frac{wt_{\phi_H}(v_{\max}^{\beta_H}) - wt_{\phi_G}(u_{\min}) + \sum_{u \in V(G)} \phi_G(u) - \sum_{v \in V(H)} \phi_H(v)}{|V(H)| - \Delta(H)} \right| + 1\]

and \(y(\lfloor \frac{x}{y} \rfloor + 1) > x\), we get

\[\begin{split} wt_{\varphi_{1}}(u_{\min}) - wt_{\varphi_{1}}(v_{\max}) &= \left(wt_{\phi_{G}}(u_{\min}) + \sum_{v \in V(H)} \phi_{H}(v) + |V(H)| \gamma_{H,G}\right) \\ &- \left(wt_{\phi_{H}}(v_{\max}^{\gamma_{H,G}}) + \sum_{u \in V(G)} \phi_{G}(u) + \gamma_{H,G} \Delta(H)\right) \\ &= wt_{\phi_{G}}(u_{\min}) - wt_{\phi_{H}}(v_{\max}^{\beta_{H}}) + \sum_{v \in V(H)} \phi_{H}(v) - \sum_{u \in V(G)} \phi_{G}(u) + (|V(H)| - \Delta(H)) \gamma_{H,G} \\ &\geq wt_{\phi_{G}}(u_{\min}) - wt_{\phi_{H}}(v_{\max}^{\beta_{H}}) + \sum_{v \in V(H)} \phi_{H}(v) - \sum_{u \in V(G)} \phi_{G}(u) \\ &+ (|V(H)| - \Delta(H)) \left( \left\lfloor \frac{wt_{\phi_{H}}(v_{\max}^{\beta_{H}}) - wt_{\phi_{G}}(u_{\min}) + \sum_{u \in V(G)} \phi_{G}(u) - \sum_{v \in V(H)} \phi_{H}(v)}{|V(H)| - \Delta(H)} \right\rfloor + 1 \right) \\ &> wt_{\phi_{G}}(u_{\min}) - wt_{\phi_{H}}(v_{\max}^{\beta_{H}}) + \sum_{v \in V(H)} \phi_{H}(v) - \sum_{u \in V(G)} \phi_{G}(u) \\ &+ \left(wt_{\phi_{H}}(v_{\max}^{\beta_{H}}) - wt_{\phi_{G}}(u_{\min}) + \sum_{v \in V(H)} \phi_{G}(u) - \sum_{v \in V(H)} \phi_{H}(v) \right) = 0, \end{split}\]

or equivalently \(wt_{\varphi_1}(u_{\min}) > wt_{\varphi_1}(v_{\max})\). Thus \(\varphi_1\) is a non-inclusive distance vertex irregular \(k_1\)-labeling of \(G \oplus H\) and hence \(\operatorname{dis}(G \oplus H) \leq k_1\).

Analogously, we define another vertex \(k_2\)-labeling \(\varphi_2\) of \(G \oplus H\) as follows.

\[\varphi_2(v) = \phi_H(v)\] if \(v \in V(H)\),

Non-inclusive and inclusive distance irregularity strength for the join product | F. Susanto et al.

\[\varphi_2(v) = \phi_G(v) + \gamma_{G,H}\] if \(v \in V(G)\).

Using similar arguments with the previous one we can obtain that \(\varphi_2\) is a non-inclusive distance vertex irregular \(k_2\)-labeling of \(G \oplus H\) and hence \(\operatorname{dis}(G \oplus H) \leq k_2\). Taking the minimum from both \(k_1\) and \(k_2\), it brings us to the desired result.

The following results related to the inclusive distance irregularity strength are presented. The proofs are omitted since ideas similar with Lemmas 2.1 and 2.2, Corollary 2.1 and Theorem 2.1, respectively, are used as arguments.

Lemma 2.3. Let G and H be graphs such that \(\widehat{\operatorname{dis}}(G \oplus H) < \infty\). Then

\[\widehat{\operatorname{dis}}(G \oplus H) \ge \max \left\{ \widehat{\operatorname{dis}}(G), \widehat{\operatorname{dis}}(H) \right\}.\]

Lemma 2.4. Let G be a graph with \(\widehat{\mathrm{dis}}(G) < \infty\) and let \(\widehat{\phi}\) be an inclusive distance vertex irregular \(\widehat{\mathrm{dis}}(G)\)-labeling of G. Let \(\widehat{\beta}_G\) be an integer defined in (3). Then for any integer \(\widehat{\alpha} \geq \widehat{\beta}_G\) and every two distinct vertices \(u, v \in V(G)\), \(wt_{\widehat{\phi}}^{\widehat{\alpha}}(u) \neq wt_{\widehat{\phi}}^{\widehat{\alpha}}(v)\). Moreover, if \(\deg_G(u) < \deg_G(v)\) then \(wt_{\widehat{\phi}}^{\widehat{\alpha}}(u) < wt_{\widehat{\phi}}^{\widehat{\alpha}}(v)\).

Corollary 2.2. Let G and H be graphs such that \(\widehat{\mathrm{dis}}(G \oplus H) < \infty\), and let \(\widehat{\phi}_G\) and \(\widehat{\phi}_H\) be an inclusive distance vertex irregular \(\widehat{\mathrm{dis}}(G)\)-labeling of G and an inclusive distance vertex irregular \(\widehat{\mathrm{dis}}(H)\)-labeling of G, respectively. Let \(\widehat{\beta}_G\) and \(\widehat{\gamma}_{G,H}\) be integers defined in (3) and (4), respectively. Then for any two distinct vertices \(u, v \in V(G)\), \(wt_{\widehat{\phi}_G}^{\widehat{\gamma}_{G,H}}(u) \neq wt_{\widehat{\phi}_G}^{\widehat{\gamma}_{G,H}}(v)\).

Theorem 2.2. Let G and H be graphs such that \(\widehat{\operatorname{dis}}(G \oplus H) < \infty\), and let \(\widehat{\phi}_G\) and \(\widehat{\phi}_H\) be an inclusive distance vertex irregular \(\widehat{\operatorname{dis}}(G)\)-labeling of G and an inclusive distance vertex irregular \(\widehat{\operatorname{dis}}(H)\)-labeling of G, respectively. If either

(i) \[\sum_{u \in V(G)} \widehat{\phi}_G(u) - \sum_{v \in V(H)} \widehat{\phi}_H(v) < wt_{\widehat{\phi}_G}(u_{\min}) - wt_{\widehat{\phi}_H}(v_{\max})\] or

(ii) \[\sum_{u \in V(G)} \widehat{\phi}_G(u) - \sum_{v \in V(H)} \widehat{\phi}_H(v) > wt_{\widehat{\phi}_G}(u_{\max}) - wt_{\widehat{\phi}_H}(v_{\min}),\]

then

\[\widehat{\operatorname{dis}}(G \oplus H) = \max \left\{ \widehat{\operatorname{dis}}(G), \widehat{\operatorname{dis}}(H) \right\}.\]

Otherwise,

\[\widehat{\mathrm{dis}}(G \oplus H) \leq \min \left\{ \max \left\{ \widehat{\mathrm{dis}}(G), \widehat{\mathrm{dis}}(H) + \widehat{\gamma}_{H,G} \right\}, \max \left\{ \widehat{\mathrm{dis}}(H), \widehat{\mathrm{dis}}(G) + \widehat{\gamma}_{G,H} \right\} \right\}.\]

If we take \(H \cong K_1\) then from Theorem 2.2 we obtain the inclusive distance irregularity strength for the graph \(G \oplus K_1\) which was proved by Bača et al. [3].

Corollary 2.3. [3] Let G be a graph such that \(\widehat{\operatorname{dis}}(G \oplus K_1) < \infty\). Then \(\widehat{\operatorname{dis}}(G \oplus K_1) = \widehat{\operatorname{dis}}(G)\).

3. \(\operatorname{dis}(G \oplus K_1)\)

In [4], Bong et al. showed that the non-inclusive distance irregularity strength of \(G \oplus K_1\) and G is equal as stated in the following theorem.

Theorem 3.1. [4] Let G be a connected graph with \(dis(G) < \infty\). Then \(dis(G \oplus K_1) = dis(G)\).

However, the above assertion is not true as we can easily see a counter example namely the complete graph \(K_n \cong K_{n-1} \oplus K_1\) of Slamin [13] which showed that \(\operatorname{dis}(K_n) = \operatorname{dis}(K_{n-1} \oplus K_1) = n \neq n-1 = \operatorname{dis}(K_{n-1})\).

In this section, we provide a correction for Theorem 3.1. We prove that \(dis(G \oplus K_1)\) can be either dis(G) or dis(G) + 1. We will need the following lemma in order to prove our theorem.

Lemma 3.1. Let G be a graph with \(\operatorname{dis}(G) < \infty\). If \(\sum_{u \in V(G)} \phi_G(u) = wt_{\phi_G}(u_{\max}) + 1\) for every non-inclusive distance vertex irregular \(\operatorname{dis}(G)\)-labeling \(\phi_G\) of G then \(\Delta(G) = |V(G)| - 1\). Moreover, if G is not a complete graph then \(G \cong G^* \oplus K_m\) for some graph \(G^*\) with \(\Delta(G^*) < |V(G^*)| - 1\) and \(m = \operatorname{dis}(G)\).

Proof. Let \(\sum_{u \in V(G)} \phi_G(u) = wt_{\phi_G}(u_{\max}) + 1\) for each non-inclusive distance vertex irregular \(\operatorname{dis}(G)\)-labeling \(\phi_G\) of G. On contrary, assume that \(\Delta(G) < |V(G)| - 1\). Then \(wt_{\phi_G}(u_{\max}) < \sum_{u \in V(G)} \phi_G(u) - 1\) or \(\sum_{u \in V(G)} \phi_G(u) > wt_{\phi_G}(u_{\max}) + 1\), a contradiction. Thus \(\Delta(G) = |V(G)| - 1\). Let \(G \ncong K_n\). Then we may write \(G \cong G^* \oplus K_m\) for some graph \(G^*\) with \(\Delta(G^*) < |V(G^*)| - 1\) and some positive integer m. For each \(x, y \in V(G) \setminus V(G^*)\), \(\phi_G(x) \neq \phi_G(y)\). Clearly \(u_{\max} \in V(G) \setminus V(G^*)\) and \(\phi_G(u_{\max}) = 1\).

Next we show that \(m = \operatorname{dis}(G)\). By Lemma 2.1, \(m \leq \operatorname{dis}(G)\). Now assume that \(m < \operatorname{dis}(G)\). Then a labeling \(\phi'_G\) on the vertices of G defined as

\[\phi'_G(u) = \phi_G(u)\] if \(u \in V(G) \setminus \{u_{\text{max}}\},\)
\(\phi'_G(u) = p\) if \(u = u_{\text{max}},\)

where \(p \in \{1, 2, \ldots, \operatorname{dis}(G)\} \setminus \{\phi_G(u) : u \in V(G) \setminus V(G^*)\}\), is a non-inclusive distance vertex irregular \(\operatorname{dis}(G)\)-labeling of G. Next let \(u'_{\max} \in V(G)\) (possibly \(u'_{\max} = u_{\max}\)) such that \(wt_{\phi'_G}(u'_{\max}) = \max\{wt_{\phi'_G}(u) : u \in V(G)\}\). In fact, we have \(\phi'_G(u'_{\max}) > 1\) and

\[\sum_{u \in V(G)} \phi'_G(u) = wt_{\phi'_G}(u'_{\max}) + \phi'_G(u'_{\max}) > wt_{\phi_G}(u'_{\max}) + 1,\]

yielding a contradiction. Hence m = dis(G).

Now we are ready to prove the main result of this section. Note that for each graph G with \(dis(G) < \infty\) and non-inclusive distance vertex irregular labeling \(\phi_G\), it holds that

\[\sum_{u \in V(G)} \phi_G(u) \ge wt_{\phi_G}(u_{\text{max}}) + 1. \tag{5}\]

Theorem 3.2. Let G be a graph with \(\operatorname{dis}(G) < \infty\). If there exists a non-inclusive distance vertex irregular \(\operatorname{dis}(G)\)-labeling \(\phi_G\) of G such that \(\sum_{u \in V(G)} \phi_G(u) > wt_{\phi_G}(u_{\max}) + 1\) then \(\operatorname{dis}(G \oplus K_1) = \operatorname{dis}(G)\). Otherwise \(\operatorname{dis}(G \oplus K_1) = \operatorname{dis}(G) + 1\).

Proof. The first case follows from Theorem 2.1. Now we consider the second case, i.e., for every non-inclusive distance vertex irregular \(\operatorname{dis}(G)\)-labeling \(\phi_G\) of G there is \(\sum_{u \in V(G)} \phi_G(u) \leq wt_{\phi_G}(u_{\max}) + 1\). Combining this inequality with (5), we have that \(\sum_{u \in V(G)} \phi_G(u) = wt_{\phi_G}(u_{\max}) + 1\) for each non-inclusive distance vertex irregular \(\operatorname{dis}(G)\)-labeling \(\phi_G\) of G.

Evidently \(\operatorname{dis}(G \oplus K_1) = \operatorname{dis}(G) + 1\) if \(G \cong K_n\). Suppose that \(G \ncong K_n\). From Lemma 3.1, \(\Delta(G) = |V(G)| - 1\) and \(G \cong G^* \oplus K_m\) for some graph \(G^*\) with \(\Delta(G^*) < |V(G^*)| - 1\) and \(m = \operatorname{dis}(G)\).

Now let \(H \cong G \oplus K_1 \cong G^* \oplus K_{m+1}\). By Lemma 2.1, \(\operatorname{dis}(H) \geq m+1 = \operatorname{dis}(G)+1\). On the other hand, the labeling \(\varphi\) defined below is a non-inclusive distance vertex irregular \((\operatorname{dis}(G)+1)\)-labeling of H,

\[\varphi(u) = \phi_G(u) + \operatorname{dis}(G) + 1 - q \qquad \text{if } u \in V(G^*),\]
\[\varphi(u) = \phi_G(u) \qquad \text{if } u \in V(K_m),\]
\[\varphi(u) = \operatorname{dis}(G) + 1 \qquad \text{if } u \in V(K_1),\]

where \(q = \max\{\phi_G(u) : u \in V(G^*)\}.\)

4. Inclusive distance irregularity strength of complete multipartite graphs

In this part, we deal with the inclusive distance vertex irregular labeling of complete multipartite graphs. Let us denote the complete multipartite graphs with \(\sum_{i=1}^r p_i\) partite sets, \(r \geq 2\), \(p_i \geq 1\), by \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) where \(1 \leq n_1 < n_2 < \cdots < n_r\).

We begin with the following observation which is easy to prove.

Observation 4.1. Let \[n > 1\]. Then \(\widehat{\operatorname{dis}}(nK_1) = n\).

The next lemma presents the upper bound for the inclusive distance irregularity strength of complete multipartite graphs with same size of partite sets.

Lemma 4.1. Let \[G \cong K_{\underbrace{n,n,\ldots,n}}\] where \(n,p \geq 2\). Then \(\widehat{\mathrm{dis}}(G) \leq n+2(p-1)\).

Proof. By labeling n vertices in the i-th partite of G with \(2(i-1)+1, 2(i-1)+2, \ldots, 2(i-1)+n\), it is not difficult to see that the vertex weights are all distinct.

Complete multipartite graphs with infinite inclusive distance irregularity strength are given in the following result.

Observation 4.2. Let \[G \cong K_{\underbrace{n_1, n_1, \dots, n_1}_{p_1 \text{ times}}}, \underbrace{n_2, n_2, \dots, n_2}_{p_2 \text{ times}}, \underbrace{n_r, n_r, \dots, n_r}_{p_r \text{ times}} \text{ where } r \geq 2, p_1, p_2, \dots, p_r \geq 1 \text{ and } 1 \leq n_1 < n_2 < \dots < n_r. \text{ If } n_1 = 1 \text{ and } p_1 \geq 2 \text{ then } \widehat{\operatorname{dis}}(G) = \infty.\]

In the following, an algorithm for determining the upper bound for the inclusive distance irregularity strength of complete multipartite graphs for other cases is provided.

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Algorithm 1 Calculating an upper bound for the inclusive distance irregularity strength of complete multipartite graphs

Input: \(r, p_1, p_2, \ldots, p_r, n_1, n_2, \ldots, n_r\): positive integers where \(r \geq 2\), \(p_1, p_2, \ldots, p_r \geq 1\) and \(1 \le n_1 < n_2 < \cdots < n_r, (n_1, p_1) \ne (1, s), s \ge 2;\)

Output: k, i.e. an upper bound for \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

\[G \leftarrow K_{\underbrace{n_1, n_1, \dots, n_1}_{p_1 \text{ times}}};\]\nif \(p_1 = 1\) then

\(G \leftarrow n_1 K_1\);

Construct an inclusive distance vertex irregular \(\widehat{\operatorname{dis}}(G)\)-labeling of G by using Observation 4.1:

else

Construct an inclusive distance vertex irregular \(\widehat{dis}(G)\)-labeling of G by using Lemma 4.1; end if

for \(i \leftarrow 2\) to r do

\[H \leftarrow K_{\underbrace{n_i, n_i, \dots, n_i}_{p_i \text{ times}}};\]\nif \(p_i = 1\) then

if \[n - 1\] then

\[H \leftarrow n_i K_1\];

Construct an inclusive distance vertex irregular \(\widehat{dis}(H)\)-labeling of H by using Obser-

else

Construct an inclusive distance vertex irregular \(\widehat{\mathrm{dis}}(H)\)-labeling of H by using Lemma 4.1:

Construct an inclusive distance vertex irregular \(\widehat{dis}(G \oplus H)\)-labeling of \(G \oplus H\) by using Theorem 2.2:

\[G \leftarrow G \oplus H\];

\[\operatorname{dis}(G) \leftarrow \operatorname{dis}(G \oplus H);\]

end for

\[k \leftarrow \operatorname{dis}(G \oplus H);\]

return k;

From Algorithm 1 we immediately get the following.

Theorem 4.1. Let \[G \cong K_{\underbrace{n_1, n_1, \ldots, n_1, n_2, \ldots, n_2, \ldots, n_r}_{p_1 \text{ times}}, \underbrace{n_r, n_r, \ldots, n_r}_{p_r \text{ times}}}\] where \(r \geq 2\), \(p_1, p_2, \ldots\),

^{pr ≥ 1} and ^{1 ≤ n1} < n^{2 &}lt; · · · < nr, (n1, p1) ⁶= (1, s), ^{s ≥ 2}. Then dis( ^{c G}) ^{≤ k} where ^k is an integer which is the output of Algorithm 1.

Observe that in our construction of the inclusive distance vertex irregular labeling for the complete multipartite graphs in Algorithm 1, vertices with smaller degree receive smaller weights. From this observation, we then conjecture that the upper bound in Theorem 4.1 is tight.

Conjecture 1. Let \[G \cong K_{\underbrace{n_1, n_1, \dots, n_1}_{p_1 \text{ times}}, \underbrace{n_2, n_2, \dots, n_2}_{p_2 \text{ times}}, \dots, \underbrace{n_r, n_r, \dots, n_r}_{p_r \text{ times}}}\] where \(r \geq 2\), \(p_1, p_2, \dots\),

^{pr ≥ 1} and ^{1 ≤ n1} < n^{2 &}lt; · · · < nr, (n1, p1) ⁶= (1, s), ^{s ≥ 2}. Then dis( ^{c G}) = ^k where ^k is an integer which is the output of Algorithm 1.

The following result supports Conjecture 1.

Corollary 4.1. Let \[r \ge 2\] and \(1 \le n_1 < n_2 < \cdots < n_r\). Then \(\widehat{\text{dis}}(K_{n_1, n_2, \dots, n_r}) = n_r\).

Proof. The upper bound follows from Theorem 4.1 and the lower bound is obtained from Lemma 2.3.

References

• [1] S. Arumugam and N. Kamatchi, On (a, d)-distance antimagic graphs, Australas. J. Combin. 54 (2012), 279-288.
• [2] M. Baca, Z. Kim ˇ akov ´ a, M. Lascs ´ akov ´ a and A. Semani ´ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, The irregularity ´ and modular irregularity strength of fan graphs, Symmetry 13 (2021), 605.
• [3] M. Baca, A. Semani ˇ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, Slamin and K.A. Sugeng, On inclusive distance ver- ´ tex irregular labelings, Electron. J. Graph Theory Appl. (EJGTA) 6 (2018), 61-83.
• [4] N.H. Bong, Y. Lin and Slamin, On distance-irregular labelings of cycles and wheels, Australas. J. Combin. 69 (2017), 315-322.
• [5] N.H. Bong, Y. Lin and Slamin, On inclusive and non-inclusive vertex irregular d-distance vertex labeling, J. Combin. Math. Combin. Comput. 113 (2020), 233-247.
• [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] S. Cichacz, A. Gorlich and A. Semani ¨ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, Upper bounds on inclusive dis- ´ tance vertex irregularity strength, Graphs Combin. (2021). https://doi.org/10.1007/s00373- 021-02385-8
• [8] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 23 (2020), #DS6.
• [9] M. Miller, C. Rodger and R. Simanjuntak, Distance magic labelings of graphs, Australas. J. Combin. 28 (2017), 305-315.

• [10] A.A.G. Ngurah and R. Simanjuntak, On distance labelings of 2-regular graphs, Electron. J. Graph Theory Appl. (EJGTA) 9 (2021), 25-37.
• [11] S. Novindasari, Marjono and S. Abusini, On distance irregular labeling of ladder graph and triangular ladder graph, Pure Math. Sci. 5 (2016), 75-81.
• [12] R. Simanjuntak and P. Anuwiksa, D-magic strongly regular graphs, AKCE Int. J. Graphs Comb. 17 (2020), 995-999.
• [13] Slamin, On distance irregular labelling of graphs, Far East J. Math. Sci. 102 (2017), 919-932.
• [14] F. Susanto, C.N. Betistiyan, I. Halikin and K. Wijaya, On inclusive distance vertex irregularity strength of small identical copies of star graphs, J. Phys. Conf. Ser. 1872 (2021), 012005.
• [15] F. Susanto, K. Wijaya, P.M. Purnama and Slamin, On distance irregular labeling of disconnected graphs, Kragujevac J. Math. 46 (2022), 507-523.
• [16] F. Susanto, K. Wijaya, Slamin and A. Semanicov ˇ a-Fe ´ nov ˇ cˇ´ıkova, Distance irregularity ´ strength of graphs with pendant vertices, submitted.
• [17] B. Utami, K.A. Sugeng and S. Utama, Inclusive vertex irregular 1-distance labelings on triangular ladder graphs, AIP Conf. Proc. 2021 (2018), 060006.
• [18] B. Utami, K.A. Sugeng and S. Utama, On inclusive d-distance irregularity strength on triangular ladder graph and path, AKCE Int. J. Graphs Comb. 17 (2020), 810-819.
• [19] D.E. Wijayanti, N. Hidayat, D. Indriati, A.R. Alghofari and Slamin, On distance vertex irregular total k-labeling, preprint.
• [20] D.E. Wijayanti, N. Hidayat, D. Indriati and A.R. Alghofari, The total distance vertex irregularity strength of fan and wheel graphs, AIP Conf. Proc. 2326 (2021), 020043.