Martin Bacaˇ a , Andrea Semanicov ˇ a-Fe ´ nov ˇ cˇ´ıkova´ a , Slamin^b , Kiki A. Sugeng^c

martin.baca@tuke.sk, andrea.fenovcikova@tuke.sk, slamin@unej.ac.id, kiki@sci.ui.ac.id

For a simple graph G, a vertex labeling f : V (G) → {1, 2, . . . , k} is called a k-labeling. The weight of a vertex v, denoted by wt^f (v) is the sum of all vertex labels of vertices in the closed neighborhood of the vertex v. A vertex k-labeling is defined to be an inclusive distance vertex irregular distance k-labeling of G if for every two different vertices u and v there is wt^f (u) 6= wt^f (v). The minimum k for which the graph G has a vertex irregular distance k-labeling is called the inclusive distance vertex irregularity strength of G. In this paper we establish a lower bound of the inclusive distance vertex irregularity strength for any graph and determine the exact value of this parameter for several families of graphs.

Keywords: inclusive distance vertex irregular labeling, inclusive distance vertex irregularity strength Mathematics Subject Classification: 05C78 DOI: 10.5614/ejgta.2018.6.1.5

1. Introduction

Inspired by Miller, Rodger and Simanjuntak [5] who introduced a distance magic labeling, Slamin [6] introduced the concept of a distance vertex irregular labeling of graphs. A distance vertex irregular labeling of a graph is a mapping g : V (G) → {1, 2, . . . , k} such that the set of vertex weights consists of distinct numbers, where the weight of a vertex v ∈ V (G) under the labeling g is defined as

\[wt_g(v) = \sum_{u \in N_G(v)} g(u),\]

Received: 9 September 2017, Revised: 13 December 2017, Accepted: 13 January 2018.

^aDepartment of Applied Mathematics and Informatics, Technical University, Letna 9, Ko ´ sice, Slovakia ˇ

b Information System Study Program, University of Jember, Jl. Kalimantan 37 Jember, Indonesia

^cDepartment of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Indonesia, Kampus UI Depok, Depok 16424, Indonesia

where \(N_G(v)\) is a set of all neighbors of a vertex v, that is a set of vertices whose distance from v is 1. In other words the weight of a vertex v is the sum of all vertex labels of vertices in the neighborhood of the vertex v. The minimum k for which a graph G has a distance vertex irregular labeling is called the distance vertex irregularity strength of G, denoted by dis(G). In his paper, Slamin also proved that \(dis(K_n) = n\), for \(n \geq 3\), \(dis(P_n) = \lceil n/2 \rceil\), for \(n \geq 4\), \(dis(C_n) = \lceil (n+1)/2 \rceil\), for \(n \equiv 0, 1, 2, 3 \pmod{8}\) and \(dis(W_n) = \lceil (n+1)/2 \rceil\), for \(n \equiv 0, 1, 2, 5 \pmod{8}\).

Bong et al. [2] generalized the concept to inclusive and non-inclusive vertex irregular d-distance vertex labeling. The difference between inclusive and non-inclusive labeling depend on the way to calculate the vertex weight whether the vertex label of vertex which we calculate its weight is included or not. The symbol d represents on how far the neighborhood is consider. Thus the original concept of Slamin can be called a non-inclusive vertex irregular 1-distance vertex labeling. An inclusive vertex irregular d-distance vertex labeling f is an irregular labeling of vertices in a graph G where the weights of a vertex \(v \in V(G)\) is the sum of the label of v and all labels of vertices up to distance d from v,

\[wt_f(v) = f(v) + \sum_{u \in V(G): \ 1 \le d(u,v) \le d} f(u),\]

where d(u,v) is the distance between vertex u to vertex v. They determined the inclusive 1-distance irregularity strength for path \(P_n\) (\(n \equiv 0 \pmod 3\)), star, double star S(m,n) with \(m \le n\), lower bound for caterpillar, cycles and wheels.

In this paper we consider an inclusive vertex irregular d-distance vertex labeling with d=1. For simplicity in this paper, we call the labeling an inclusive distance vertex irregular labeling. Thus an inclusive distance vertex labeling f is an irregular labeling of vertices in a graph G where the weights of a vertex \(v \in V(G)\) is the sum of the label of v and all vertex labels of vertices in the neighborhood of the vertex v, and thus

\[wt_f(v) = \sum_{u \in N_G[v]} f(u),\]

where \(N_G[v]\) is a set of all neighbors of a vertex v including v, that is a set of vertices whose distance from v is maximum 1.

The minimum k for which there exists an inclusive distance vertex irregular labeling of a graph G is called the inclusive distance vertex irregularity strength of G and is denoted by \(\widehat{\operatorname{dis}}(G)\). If such k does not exist we say that \(\widehat{\operatorname{dis}}(G) = \infty\).

We establish a lower bound of the inclusive distance vertex irregularity strength and determine the exact value of this parameter for several families of graphs. We are dealing with the given graph invariant for complete graphs, complete bipartite graphs, paths, cycles, fans and wheels.

2. Lower and upper bound

The following lemma gives a lower bound on the inclusive distance vertex irregularity strength of a graph G.

Lemma 2.1. [2] Let G be a graph with maximum degree \(\Delta(G)\) and minimum degree \(\delta(G)\). Then

\[\widehat{\operatorname{dis}}(G) \ge \left\lceil \frac{|V(G)| + \delta(G)}{\Delta(G) + 1} \right\rceil.\]

Now we will deal with an upper bound of \(\widehat{\operatorname{dis}}(G)\). The following theorem gives a sufficient and necessary condition for \(\widehat{\operatorname{dis}}(G) < \infty\). Note that the graph G is not necessarily connected.

Theorem 2.1. For a graph G holds \(\widehat{\operatorname{dis}}(G) = \infty\) if and only if there exist two distinct vertices \(u, v \in V(G)\) such that \(N_G[u] = N_G[v]\).

Proof. Let us consider that in G there exist two distinct vertices \(u, v \in V(G)\) such that

\[N_G[u] = N_G[v]. (1)\]

Let f be any vertex labeling of G, \(f:V(G) \to \{1,2,\ldots,k\}\). For the weights of vertices u and v under a labeling f we get

\[wt_f(u) = \sum_{x \in N_G[u]} f(x) = \sum_{x \in N_G[u]} f(x) = \sum_{x \in N_G[v]} f(x) = \sum_{x \in N_G[v]} f(x) = wt_f(v).\]

According to the condition (1) we get \(wt_f(u) = wt_f(v)\) which evidently means that f can not be distance vertex irregular.

Now, let us consider that for all vertices \(u, v \in V(G)\) it holds that \(N_G[u] \neq N_G[v]\). Let us denote the vertices of G arbitrarily by the symbols \(v_1, v_2, \ldots, v_{|V(G)|}\). We define a vertex \(2^{|V(G)|-1}\)-labeling f of G in the following way:

\[f(v_i) = 2^{i-1},\] for \(i = 1, 2, ..., |V(G)|.\)

Let us define the labeling \(\theta\) such that

\[\theta_{i,j} = \begin{cases} 1, & \text{if } v_i \in N_G[v_j], \\ 0, & \text{if } v_i \notin N_G[v_j], \end{cases}\]

where i = 1, 2, ..., |V(G)|, j = 1, 2, ..., |V(G)|.

The weight of a vertex \(v_j\) is the sum of all vertex labels of vertices in a closed neighborhood of \(v_j\). Thus, for \(j=1,2,\ldots,|V(G)|\) we have

\[wt_f(v_j) = \sum_{v_i \in N_G[v_j]} f(v_i) = \sum_{i: \ v_i \in N_G[v_j]} 2^{i-1} = \sum_{i=1}^{|V(G)|} \theta_{i,j} 2^{i-1}.\] (2)

To prove that vertex weights are all distinct it is enough to show that the sums \(\sum_{i=1}^{|V(G)|} \theta_{i,j} 2^{i-1}\) are distinct for \(j=1,2,\ldots,|V(G)|\). However, this is evident if we consider that the ordered |V(G)|-tuple \((\theta_{|V(G)|,j}\theta_{|V(G)|-1,j}\ldots\theta_{2,j}\theta_{1,j})\) corresponds to the binary code representation of the sum (2). As different vertices have distinct closed neighborhoods we immediately get that the |V(G)|-tuples are different for different vertices. Which implies that \(\widehat{\mathrm{dis}}(G) < 2^{|V(G)|-1}\).

3. Complete and complete bipartite graph

Immediately from Theorem 2.1 we obtain the result for the inclusive distance vertex irregularity strength of complete graphs.

Corollary 3.1. Let n be a positive integer. Then

\[\widehat{\operatorname{dis}}(K_n) = \begin{cases} 1, & \text{for } n = 1, \\ \infty, & \text{for } n \ge 2. \end{cases}\]

From Theorem 2.1 we also obtain the following result.

Lemma 3.1. Let dis( ^{c G}) ^&lt; ^∞. If u, v ^{∈ V} (G) are two distinct vertices such that ^NG(u) = ^NG(v) then f(u) 6= f(v) in any inclusive distance vertex irregular labeling f of G.

We will use this lemma for finding the inclusive distance vertex irregularity strength of complete bipartite graphs Km,n, m, n ≥ 1.

Theorem 3.1. Let m, n be positive integers m ≥ n ≥ 1. Then

\[\widehat{\operatorname{dis}}(K_{m,n}) = \begin{cases} \infty, & \text{for } m = n = 1, \\ n+2, & \text{for } m = n \ge 2, \\ m, & \text{for } m > n. \end{cases}\]

Proof. Let m, n be positive integers m ≥ n ≥ 1. Let us denote the vertices and edges of Km,n such that

\[V(K_{m,n}) = \{u_i : i = 1, 2, \dots, m\} \cup \{v_j : j = 1, 2, \dots, n\},\]
\[E(K_{m,n}) = \{u_i v_j : i = 1, 2, \dots, m, j = 1, 2, \dots, n\}.\]

We will consider three cases.

Case 1: m = n = 1. In this case the graph Km,n = K1,¹ is isomorphic to K² and according to Corollary 3.1 we get dis( ^{c K}1,1) = ^∞.

Case 2: m = n ≥ 2. Let f : V (G) → {1, 2, . . . , k} be an inclusive distance vertex irregular labeling of Kn,n. According to Lemma 3.1 we get k ≥ n and the set of labels of vertices uⁱ , i = 1, 2, . . . , n must consist of distinct numbers and also the set of labels of vertices v^j , j = 1, 2, . . . , n must consist of distinct numbers. It is easy to see that k > n.

Let us consider that k = n + 1. Without loss of generality we can assume that

\[\{f(u_i): i=1,2,\ldots,n\} = \{1,2,\ldots,n\}\]

and

\[{f(v_j): j=1,2,\ldots,n} = {1,2,\ldots,n+1} \setminus {p},\]

where p is an integer 1 ≤ p ≤ n.

Then for the vertex weights we get

\[wt_f(v_j) = f(v_j) + \sum_{i=1}^n f(u_i) = f(v_j) + \sum_{i=1}^n i = f(v_i) + \frac{n(n+1)}{2},\]

for j = 1, 2, ..., n. Thus

\[\{wt_f(v_j): j=1,2,\ldots,n\} = \{\frac{n(n+1)}{2}+1,\frac{n(n+1)}{2}+2,\ldots,\frac{n(n+1)}{2}+n+1\}\setminus \{\frac{n(n+1)}{2}+p\}.\]

And

\[wt_f(u_i) = f(u_i) + \sum_{j=1}^n f(v_j) = f(u_i) + \sum_{j=1}^{n+1} j - p = f(u_i) + \sum_{j=1}^n j + (n+1) - p\]\[= f(u_i) + \frac{n(n+1)}{2} + (n+1) - p,\]

for i = 1, 2, ..., n. Thus

\[\{wt_f(u_i): i=1,2,\ldots,n\} = \{\frac{n(n+1)}{2} + n + 2 - p, \frac{n(n+1)}{2} + n + 3 - p, \ldots, \frac{n(n+1)}{2} + 2n + 2 - p\}.\]

Which is a contradiction as the vertex weights are not distinct. Thus \(k \ge n + 2\).

Let us define the vertex labeling g of \(K_{n,n}\) such that

\[g(u_i) = i,\] for \(i = 1, 2, ..., n,\)
\(g(v_i) = j + 2,\) for \(j = 1, 2, ..., n.\)

Thus \(g(u) \leq n+2\) for all vertices in \(K_{n,n}\).

Now we compute the vertex weights. For i = 1, 2, ..., n,

\[wt_g(u_i) = g(u_i) + \sum_{i=1}^{n} g(v_i) = i + \sum_{i=1}^{n} (j+2) = i + \frac{n(n+1)}{2} + 2n\]

and for j = 1, 2, ..., n

\[wt_g(v_j) = g(v_j) + \sum_{i=1}^n g(u_i) = (j+2) + \sum_{i=1}^n i = j+2 + \frac{n(n+1)}{2} \le \frac{n(n+1)}{2} + n + 2.\]

As \(n \ge 2\) we obtain that the vertex weights are distinct.

Case 3: m > n. Let \(f: V(G) \to \{1, 2, ..., k\}\) be an inclusive distance vertex irregular labeling of \(K_{m,n}\). According to Lemma 3.1 we get \(k \ge m\). Let us define the vertex labeling f of \(K_{m,n}\) such that

\[f(u_i) = i\], for \(i = 1, 2, ..., m\),
\(f(v_j) = j\), for \(j = 1, 2, ..., n\).

Evidently the vertex labels are not greater than m.

For the weights of the vertices we get the following. For i = 1, 2, . . . , m

\[wt_f(u_i) = f(u_i) + \sum_{j=1}^{n} f(v_j) = i + \sum_{j=1}^{n} j = i + \frac{n(n+1)}{2},\]

thus

\[\{wt_f(u_i): i=1,2,\ldots,m\} = \{\frac{n(n+1)}{2}+1,\frac{n(n+1)}{2}+2,\ldots,\frac{n(n+1)}{2}+m\}.\]

For j = 1, 2, . . . , n

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

which implies that that the weight sets do not overlap.

Immediately from Theorem 3.1 we obtain the result for the inclusive distance vertex irregularity strength of stars Sⁿ = K1,n, which is also proved by Bong et al. [2].

Corollary 3.2. Let n be a positive integer. Then

\[\widehat{\operatorname{dis}}(S_n) = \begin{cases} \infty, & \text{for } n = 1, \\ n, & \text{for } n \ge 2. \end{cases}\]

The join G ⊕ H of two disjoint graphs G and H is the graph G ∪ H together with all the edges joining vertices of V (G) and vertices of V (H). In the next theorem we will deal with the inclusive distance vertex irregularity strength of joins G ⊕ K1, where G is an arbitrary graph, possibly also disconnected.

Theorem 3.2. Let G be a graph with maximum degree ∆(G). Then

\[\widehat{\operatorname{dis}}(G \oplus K_1) = \begin{cases} \infty, & \text{if } \Delta(G) = |V(G)| - 1, \\ \widehat{\operatorname{dis}}(G), & \text{if } \Delta(G) < |V(G)| - 1. \end{cases}\]

Proof. Let G be a graph with maximum degree ∆(G). Let us denote the vertices and edges of a graph G ⊕ K¹ such that

\[V(G \oplus K_1) = V(G) \cup \{v\},\]
\[E(G \oplus K_1) = E(G) \cup \{vu : u \in V(G)\}.\]

Let w ∈ V (G) be a vertex such that degG(w) = ∆(G). If ∆(G) = |V (G)| − 1 then in the graph G ⊕ K¹ the degree of the vertex w will be |V (G)|, that is

\[N_{G \oplus K_1}[w] = V(G \oplus K_1).\]

But also for the vertex v we get \(\deg_{G \oplus K_1}(v) = |V(G)|\) which means

\[N_{G \oplus K_1}[v] = V(G \oplus K_1).\]

According to Theorem 2.1 we get \(\widehat{\operatorname{dis}}(G \oplus K_1) = \infty\).

Now let us consider that \(\Delta(G) < |V(G)| - 1\). We distinguish two cases.

Case 1: \(\widehat{\text{dis}}(G) = \infty\). By Theorem 2.1 we get that there must exist in G two distinct vertices, say x, y, such that \(N_G[x] = N_G[y]\). But this implies that

\[N_{G \oplus K_1}[x] = N_G[x] \cup \{v\} = N_G[y] \cup \{v\} = N_{G \oplus K_1}[y].\]

But this means that \(\widehat{\operatorname{dis}}(G \oplus K_1) = \infty\).

Case 2: \(\widehat{\mathrm{dis}}(G) < \infty\). Let \(f: V(G) \to \{1, 2, \dots, k\}\) be an inclusive distance vertex irregular labeling of a graph G such that \(k = \widehat{\mathrm{dis}}(G)\). Let us define a vertex labeling \(g: V(G \oplus K_1) \to \{1, 2, \dots, k\}\) such that

\[g(u) = f(u), \text{ for } u \in V(G),\]
\(g(v) = 1.\)

Evidently g is a k-labeling. For the vertex weights under the labeling g we get the following. If \(u \in V(G)\) then

\[wt_g(u) = \sum_{x \in N_{G, \mathbb{R}^K}, [u]} g(x) = \sum_{x \in N_G[u]} g(x) + g(v) = \sum_{x \in N_G[u]} f(x) + 1 = wt_f(u) + 1.\]

As f is an inclusive distance vertex irregular labeling of a graph G then the vertices \(u \in V(G \oplus K_1) \setminus \{v\}\) have distinct weights under the labeling g.

The weight of a vertex v is

\[wt_g(v) = \sum_{x \in N_{G \oplus K_1}[v]} g(x) = \sum_{x \in N_G[u]} g(x) = 1 + \sum_{x \in V(G)} f(x).\]

As \(\Delta(G) < |V(G)| - 1\) we get that for every vertex \(u \in V(G)\)

\[\sum_{x \in V(G)} f(x) > wt_f(u).\]

This implies that for every vertex \(u \in V(G)\)

\[wt_g(v) = 1 + \sum_{x \in V(G)} f(x) > 1 + wt_f(u) = wt_g(u).\]

Thus \(\widehat{\operatorname{dis}}(G \oplus K_1) \leq \widehat{\operatorname{dis}}(G)\).

To prove the equality it is sufficient to show that there does not exist an inclusive distance vertex irregular K-labeling of a graph \(G \oplus K_1\) such that \(K < \widehat{\mathrm{dis}}(G)\). On contrary let us consider

that such labeling h exists. Thus \(h: V(G \oplus K_1) \to \{1, 2, \dots, K\}\) is an inclusive distance vertex irregular labeling of a graph \(G \oplus K_1\). Under the labeling h the vertex weights of all vertices must be distinct, thus also for every two vertices \(x, y \in V(G)\) we have

\[wt_h(x) \neq wt_h(y)\].

Now we subtract from both sides the label of the vertex v and we obtain

\[wt_h(x) - h(v) \neq wt_h(y) - h(v)\].

But this means that a restriction of the labeling h on the graph G is an inclusive distance vertex irregular K-labeling of G. And this is a contradiction as \(K < \widehat{\mathrm{dis}}(G)\). This concludes the proof.

Immediately from Theorem 3.2 we get another proof of Corollary 3.1.

Let \(K_{n_1,n_2,...,n_p}\) denote the complete p-partite graph with partite sets of cardinalities \(n_i\), i = 1, 2, ..., p. Using Theorems 3.2 and 3.1 we obtain a result for complete multipartite graphs of a special type.

Theorem 3.3. Let m, n be positive integers \(m \ge n \ge 1\). Then

\[\widehat{\operatorname{dis}}(K_{m,n,1}) = \begin{cases} \infty, & \text{for } m = n = 1, \\ n+2, & \text{for } m = n \ge 2, \\ m, & \text{for } m > n. \end{cases}\]

4. Path

Let \(P_n\), \(n \ge 2\) be a path on n vertices. We denote the vertices and edges of \(P_n\) such that

\[V(P_n) = \{v_i : i = 1, 2, \dots, n\},\\]
\[E(P_n) = \{v_i v_{i+1} : i = 1, 2, \dots, n-1\}.\]

Bong et al. [2] proved that \(\widehat{\operatorname{dis}}(P_n) = n/3 + 1\) for \(n \equiv 0 \pmod{3}\). As \(P_2\) is isomorphic to a complete graph \(K_2\) using Corollary 3.1 we get \(\widehat{\operatorname{dis}}(P_2) = \infty\). For the inclusive distance vertex irregularity strength of a path we prove the following.

Theorem 4.1. Let n be a positive integer \(n \geq 2\). Then

\[\widehat{\operatorname{dis}}(P_n) = \begin{cases} \infty, & \text{for } n = 2, \\ 3, & \text{for } n = 5, \\ \left\lceil \frac{n+1}{3} \right\rceil, & \text{for } n \not\equiv 2 \pmod{9}, \ n \neq 5 \end{cases}\]

and

\[\frac{n+1}{3} \le \widehat{\operatorname{dis}}(P_n) \le \frac{n+1}{3} + 1,\]

when \(n \equiv 2 \pmod{9}\), \(n \ge 11\).

Let \(n \ge 3\) be a positive integer. As \(\Delta(P_n) = 2\) and \(\delta(P_n) = 1\) from Lemma 2.1 we obtain a lower bound of the inclusive distance vertex irregularity strength of a path

\[\widehat{\operatorname{dis}}(P_n) \ge \left\lceil \frac{n+1}{3} \right\rceil. \tag{3}\]

To prove the equality let us consider Lemmas 4.1 throughout 4.5.

Lemma 4.1. Let n be a positive integer, \(n \equiv 1, 7 \pmod{9}\), \(n \geq 7\). Then

\[\widehat{\operatorname{dis}}(P_n) = \frac{n+2}{3}.\]

Proof. Let \(n \equiv 1, 7 \pmod{9}\), \(n \geq 7\). According to (3) it suffices to show that there exists an inclusive distance vertex irregular \(\lceil (n+1)/3 \rceil\)-labeling of \(P_n\).

Let \(f: V(P_n) \to \{1, 2, \dots, \lceil (n+1)/3 \rceil \}\) be a vertex labeling of \(P_n\) defined such that

\[f(v_i) = \left\lceil \frac{i}{3} \right\rceil, \quad \text{for } i = 1, 2, \dots, \frac{2n+1}{3},\]
\(f(v_i) = \left\lceil \frac{i+2}{3} \right\rceil, \quad \text{for } i = \frac{2n+4}{3}, \frac{2n+7}{3}, \dots, n.\)

It is easy to see that every vertex label is not greater than \((n+2)/3 = \lceil (n+1)/3 \rceil\). For the vertex weights we get the following.

\[wt_f(v_1) = f(v_1) + f(v_2) = \left\lceil \frac{1}{3} \right\rceil + \left\lceil \frac{2}{3} \right\rceil = 2,\]
\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{i-1}{3} \right\rceil + \left\lceil \frac{i}{3} \right\rceil + \left\lceil \frac{i+1}{3} \right\rceil = i+1,\]
for \(i = 2, 3, \dots, \frac{2n-2}{3}\),

thus the corresponding weights are \(3, 4, \ldots, \frac{2n+1}{3}\),

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

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{(i-1)+2}{3} \right\rceil + \left\lceil \frac{i+2}{3} \right\rceil + \left\lceil \frac{(i+1)+2}{3} \right\rceil = i+3,\]
for \(i = \frac{2n+7}{3}, \frac{2n+10}{3}, \dots, n-1,\)

thus the corresponding weights are \(\frac{2n+16}{3}, \frac{2n+19}{3}, \dots, n+2\),

\[wt_f(v_n) = f(v_{n-1}) + f(v_n) = \left\lceil \frac{(n-1)+2}{3} \right\rceil + \left\lceil \frac{n+2}{3} \right\rceil = \frac{2n+4}{3}.\]

Thus the vertex weights are distinct. This concludes the proof.

Lemma 4.2. Let n be a positive integer, \(n \equiv 4 \pmod{9}\), \(n \geq 4\). Then

\[\widehat{\operatorname{dis}}(P_n) = \frac{n+2}{3}\].

Proof. Let \(n \equiv 4 \pmod 9\), \(n \geq 4\). A vertex labeling \(f: V(P_n) \to \{1, 2, \dots, (n+2)/3\}\) is defined in the following way

\[f(v_i) = \left\lceil \frac{i}{3} \right\rceil, \quad \text{for } i = 1, 2, \dots, \frac{2n-5}{3},\]
\(f(v_i) = \left\lceil \frac{i+2}{3} \right\rceil, \quad \text{for } i = \frac{2n-2}{3}, \frac{2n+1}{3}, \dots, n.\)

It is easy to see that every vertex label is not greater than \((n+2)/3 = \lceil (n+1)/3 \rceil\). Thus, according to (3) we only need to show that the corresponding vertex weights are distinct. In particular:

\[wt_f(v_1) = f(v_1) + f(v_2) = \left\lceil \frac{1}{3} \right\rceil + \left\lceil \frac{2}{3} \right\rceil = 2,\]
\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{i-1}{3} \right\rceil + \left\lceil \frac{i}{3} \right\rceil + \left\lceil \frac{i+1}{3} \right\rceil = i+1,\]
for \(i = 2, 3, \dots, \frac{2n-8}{3}\),

thus the corresponding weights are \(3, 4, \ldots, \frac{2n-5}{3}\),

\[wt_{f}(v_{\frac{2n-5}{3}}) = f(v_{\frac{2n-8}{3}}) + f(v_{\frac{2n-5}{3}}) + f(v_{\frac{2n-5}{3}}) = \begin{bmatrix} \frac{2n-8}{3} \\ \frac{3}{3} \end{bmatrix} + \begin{bmatrix} \frac{2n-5}{3} \\ \frac{3}{3} \end{bmatrix} + \begin{bmatrix} \frac{2n-2}{3} + 2 \\ \frac{3}{3} \end{bmatrix} = \frac{2n+1}{3},\] \[wt_{f}(v_{\frac{2n-2}{3}}) = f(v_{\frac{2n-5}{3}}) + f(v_{\frac{2n-2}{3}}) + f(v_{\frac{2n+1}{3}}) = \begin{bmatrix} \frac{2n-5}{3} \\ \frac{3}{3} \end{bmatrix} + \begin{bmatrix} \frac{2n-2}{3} + 2 \\ \frac{3}{3} \end{bmatrix} + \begin{bmatrix} \frac{2n+1}{3} + 2 \\ \frac{3}{3} \end{bmatrix} = \frac{2n+7}{3},\] \[wt_{f}(v_{i}) = f(v_{i-1}) + f(v_{i}) + f(v_{i+1}) = \begin{bmatrix} \frac{(i-1)+2}{3} \\ \frac{3}{3} \end{bmatrix} + \begin{bmatrix} \frac{i+2}{3} \\ \frac{3}{3} \end{bmatrix} + \begin{bmatrix} \frac{(i+1)+2}{3} \\ \frac{3}{3} \end{bmatrix} = i+3,\] \[for \ i = \frac{2n+1}{3}, \frac{2n+4}{3}, \dots, n-1,\]

thus the corresponding weights are \(\frac{2n+10}{3}, \frac{2n+13}{3}, \dots, n+2\),

\[wt_f(v_n) = f(v_{n-1}) + f(v_n) = \left\lceil \frac{(n-1)+2}{3} \right\rceil + \left\lceil \frac{n+2}{3} \right\rceil = \frac{2n+4}{3}.\]

Lemma 4.3. Let n be a positive integer, \(n \equiv 5 \pmod{9}\), \(n \geq 5\). Then

\[\widehat{\operatorname{dis}}(P_n) = \begin{cases} 3, & \text{for } n = 5, \\ \frac{n+1}{3}, & \text{for } n \equiv 5 \pmod{9}. \end{cases}\]

Proof. Let \(n \equiv 5 \pmod{9}\), \(n \geq 5\). The lower bound for \(\widehat{\operatorname{dis}}(P_n)\) is given by (3), thus

\[\widehat{\operatorname{dis}}(P_n) \ge \left\lceil \frac{n+1}{3} \right\rceil = \frac{n+1}{3}.\]

First, let n=5. Thus \(\widehat{\mathrm{dis}}(P_5)\geq 2\). We prove that \(\widehat{\mathrm{dis}}(P_n)>2\). Consider on contrary that there exists an inclusive distance vertex irregular 2-labeling of \(P_5\). This means that all numbers 2,3,4,5 and 6 must be realizable as vertex weights. Note, that the weight 2 we can get only as 1+1 and the weight 6 we can only get as 2+2+2, this implies that two incident vertices, say \(v_1\) and \(v_2\), must be labeled by 1 and three incident vertices, say \(v_3, v_4\) and \(v_5\), must be labeled by label 2. But, in this case the weights of vertices \(v_2\) and \(v_5\) are the same (equal to 4). A contradiction.

An inclusive distance vertex irregular 3-labeling f of \(P_5\) is

\[f(v_1) = f(v_2) = 1\], \(f(v_3) = f(v_4) = f(v_5) = 3\).

For n ≥ 14 let us consider a labeling f : V (Pn) → {1, 2, . . . ,(n + 1)/3} defined in the following way

\[f(v_i) = \frac{i+2}{3}, \quad \text{for } i = 1, 4, \dots, n-1,\] \[f(v_i) = \frac{i+1}{3}, \quad \text{for } i = 2, 5, \dots, \frac{2n+2}{3} - 5,\] \[f(v_i) = \frac{i+4}{3}, \quad \text{for } i = \frac{2n+2}{3} - 2, \frac{2n+2}{3} + 1, \dots, n-3,\] \[f(v_n) = \frac{n-5}{3},\] \[f(v_i) = \frac{i}{3}, \quad \text{for } i = 3, 6, \dots, n-5,\] \[f(v_{n-2}) = \frac{n+1}{3}.\]

Maximal number used as a vertex label is (n + 1)/3. The vertex weights are

\[wt_f(v_1) = f(v_1) + f(v_2) = \frac{1+2}{3} + \frac{2+1}{3} = 2,\] \[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \frac{i-1}{3} + \frac{i+2}{3} + \frac{(i+1)+1}{3} = i+1,\] for \(i = 4, 7, \dots, \frac{2n+2}{3} - 6,\)

thus the corresponding weights are 5, 8, . . . , 2n+2 ³ − 5,

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \frac{i-1}{3} + \frac{i+2}{3} + \frac{(i+1)+4}{3} = i+2,\]
for \(i = \frac{2n+2}{3} - 3, \frac{2n+2}{3}, \dots, n-7,\)

thus the corresponding weights are ²n+2 ³ − 1, 2n+2 ³ + 2, . . . , n − 5,

\[wt_f(v_{n-4}) = f(v_{n-5}) + f(v_{n-4}) + f(v_{n-3}) = \frac{n-5}{3} + \frac{(n-4)+2}{3} + \frac{(n-3)+4}{3} = n-2,\] \[wt_f(v_{n-1}) = f(v_{n-2}) + f(v_{n-1}) + f(v_n) = \frac{n+1}{3} + \frac{(n-1)+2}{3} + \frac{n-5}{3} = n-1,\] \[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \frac{(i-1)+2}{3} + \frac{i+1}{3} + \frac{i+1}{3} = i+1,\] \[\text{for } i = 2, 5, \dots, \frac{2n+2}{3} - 5,\]

thus the corresponding weights are 3, 6, . . . , 2n+2 ³ − 4,

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \frac{(i-1)+2}{3} + \frac{i+4}{3} + \frac{i+1}{3} = i+2,\]
for \(i = \frac{2n+2}{3} - 2, \frac{2n+2}{3} + 1, \dots, n-6,\)

thus the corresponding weights are ²n+2 3 , 2n+2 ³ + 3, . . . , n − 4,

\[wt_f(v_{n-3}) = f(v_{n-4}) + f(v_{n-3}) + f(v_{n-2}) = \frac{(n-4)+2}{3} + \frac{(n-3)+4}{3} + \frac{n+1}{3} = n,\] \[wt_f(v_n) = f(v_{n-1}) + f(v_n) = \frac{(n-1)+2}{3} + \frac{n-5}{3} = \frac{2n-4}{3},\] \[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \frac{(i-1)+1}{3} + \frac{i}{3} + \frac{(i+1)+2}{3} = i+1,\] \[\text{for } i = 3, 6, \dots, \frac{2n+2}{3} - 4,\]

thus the corresponding weights are 4, 7, . . . , 2n+2 ³ − 3,

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \frac{(i-1)+4}{3} + \frac{i}{3} + \frac{(i+1)+2}{3} = i+2,\]
for \(i = \frac{2n+2}{3} - 1, \frac{2n+2}{3} + 2, \dots, n-5,\)

thus the corresponding weights are ²n+2 ³ + 1, 2n+2 ³ + 4, . . . , n − 3,

\[wt_f(v_{n-2}) = f(v_{n-3}) + f(v_{n-2}) + f(v_{n-1}) = \frac{(n-3)+4}{3} + \frac{n+1}{3} + \frac{(n-1)+2}{3} = n+1.\]

Thus the set of vertex weights is \(\{2, 3, \dots, n+1\}\).

Lemma 4.4. Let n be a positive integer, \(n \equiv 8 \pmod{9}\), \(n \geq 8\). Then

\[\widehat{\operatorname{dis}}(P_n) = \frac{n+1}{3}.\]

Proof. Let \(n \equiv 8 \pmod{9}\), \(n \geq 8\). We define a vertex labeling \(f: V(P_n) \to \{1, 2, \dots, (n+1)/3\}\) in the following way

\[f(v_i) = \left\lceil \frac{i}{3} \right\rceil,\] for \(i = 1, 2, \dots, \frac{2n-1}{3},\)
\(f(v_i) = \left\lfloor \frac{i}{3} \right\rfloor + 1,\) for \(i = \frac{2n+2}{3}, \frac{2n+5}{3}, \dots, n.\)

It is easy to see that every vertex label is at most \((n+1)/3 = \lceil (n+1)/3 \rceil\). Thus, according to (3) we only need to show that the corresponding vertex weights are distinct. In particular:

\[wt_f(v_1) = f(v_1) + f(v_2) = \left\lceil \frac{1}{3} \right\rceil + \left\lceil \frac{2}{3} \right\rceil = 2,\]
\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{i-1}{3} \right\rceil + \left\lceil \frac{i}{3} \right\rceil + \left\lceil \frac{i+1}{3} \right\rceil = i+1,\]
for \(i = 2, 3, \dots, \frac{2n-4}{3}\),

thus the corresponding weights are \(3, 4, \ldots, \frac{2n-1}{3}\),

\[wt_f(v_{\frac{2n-1}{3}}) = f(v_{\frac{2n-4}{3}}) + f(v_{\frac{2n-1}{3}}) + f(v_{\frac{2n+2}{3}}) = \left\lceil \frac{\frac{2n-4}{3}}{3} \right\rceil + \left\lceil \frac{\frac{2n-1}{3}}{3} \right\rceil + \left( \left\lfloor \frac{\frac{2n+2}{3}}{3} \right\rfloor + 1 \right)\] \[= \frac{2n+5}{3},\]

\[wt_f(v_{\frac{2n+2}{3}}) = f(v_{\frac{2n-1}{3}}) + f(v_{\frac{2n+2}{3}}) + f(v_{\frac{2n+5}{3}}) = \left\lceil \frac{\frac{2n-1}{3}}{3} \right\rceil + \left( \left\lfloor \frac{\frac{2n+2}{3}}{3} \right\rfloor + 1 \right) + \left( \left\lfloor \frac{\frac{2n+5}{3}}{3} \right\rfloor + 1 \right) = \frac{2n+8}{3},\]

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left( \left\lfloor \frac{i-1}{3} \right\rfloor + 1 \right) + \left( \left\lfloor \frac{i}{3} \right\rfloor + 1 \right) + \left( \left\lfloor \frac{i+1}{3} \right\rfloor + 1 \right) = i + 2,\] for \(i = \frac{2n+5}{3}, \frac{2n+8}{3}, \dots, n-1,\)

thus the corresponding weights are \(\frac{2n+11}{3}, \frac{2n+14}{3}, \dots, n+1\),

\[wt_f(v_n) = f(v_{n-1}) + f(v_n) = \left(\left\lfloor \frac{n-1}{3} \right\rfloor + 1\right) + \left(\left\lfloor \frac{n}{3} \right\rfloor + 1\right) = \frac{2n+2}{3}\]

Thus the edge weights are distinct.

Lemma 4.5. Let n be a positive integer, \(n \equiv 2 \pmod{9}\), \(n \geq 11\). Then

\[\frac{n+1}{3} \le \widehat{\operatorname{dis}}(P_n) \le \frac{n+4}{3}.\]

Proof. Let \(n \equiv 2 \pmod 9\), \(n \ge 11\). We define a vertex labeling \(f: V(P_n) \to \{1, 2, \dots, k\}\) in the following way

\[f(v_i) = \left\lceil \frac{i}{3} \right\rceil,\] for \(i = 1, 2, \dots, \frac{2n+5}{3},\)
\(f(v_i) = \left\lceil \frac{i}{3} \right\rceil + 1,\) for \(i = \frac{2n+8}{3}, \frac{2n+11}{3}, \dots, n.\)

Evidently, the vertex labels are not greater that \(\lceil n/3 \rceil + 1 = (n+4)/3\). For the vertex weights we get

\[\begin{split} wt_f(v_1) = & f(v_1) + f(v_2) = \left\lceil \frac{1}{3} \right\rceil + \left\lceil \frac{2}{3} \right\rceil = 2, \\ wt_f(v_i) = & f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{i-1}{3} \right\rceil + \left\lceil \frac{i}{3} \right\rceil + \left\lceil \frac{i+1}{3} \right\rceil = i+1, \\ \text{for } i = 2, 3, \dots, \frac{2n+2}{3}, \\ \text{thus the corresponding weights are } 3, 4, \dots, \frac{2n+5}{3}, \\ wt_f(v_{\frac{2n+5}{3}}) = & f(v_{\frac{2n+2}{3}}) + f(v_{\frac{2n+5}{3}}) + f(v_{\frac{2n+8}{3}}) = \left\lceil \frac{2n+2}{3} \right\rceil + \left\lceil \frac{2n+5}{3} \right\rceil + \left\lceil \frac{2n+8}{3} \right\rceil + 1 \end{split}\]

\[wt_{f}(v_{\frac{2n+8}{3}}) = f(v_{\frac{2n+5}{3}}) + f(v_{\frac{2n+8}{3}}) + f(v_{\frac{2n+11}{3}}) = \left\lceil \frac{2n+5}{3} \right\rceil + \left( \left\lceil \frac{2n+8}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{2n+11}{3} \right\rceil + 1 \right) = \frac{2n+17}{3},\] \[wt_{f}(v_{i}) = f(v_{i-1}) + f(v_{i}) + f(v_{i+1}) = \left( \left\lceil \frac{i-1}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{i}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{i+1}{3} \right\rceil + 1 \right) = i+4,\] \[\text{for } i = \frac{2n+11}{3}, \frac{2n+14}{3}, \dots, n-1,\]

thus the corresponding weights are \[\frac{2n+23}{3}, \frac{2n+26}{3}, \dots, n+3\], \(wt_f(v_n) = f(v_{n-1}) + f(v_n) = \left(\left\lceil \frac{n-1}{3} \right\rceil + 1\right) + \left(\left\lceil \frac{n}{3} \right\rceil + 1\right) = \frac{2n+8}{3}\).

We proved that the vertex weights of distinct vertices are distinct. This means that f is an inclusive distance vertex irregular ((n+4)/3)-labeling. Thus \(\widehat{\operatorname{dis}}(P_n) \leq (n+4)/3\).

The join of a path \(P_n\), \(n \ge 2\), and a complete graph \(K_1\) is called a fan graph \(F_n\). Combining Theorems 3.2 and 4.1 we obtain that for fans holds the following.

Theorem 4.2. Let n be a positive integer \(n \geq 2\). Then

\[\widehat{\operatorname{dis}}(F_n) = \begin{cases} \infty, & \text{for } n = 2, \\ 3, & \text{for } n = 5, \\ \left\lceil \frac{n+1}{3} \right\rceil, & \text{for } n \not\equiv 2 \pmod{9}, \ n \neq 5 \end{cases}\]

and

\[\frac{n+1}{3} \le \widehat{\operatorname{dis}}(F_n) \le \frac{n+1}{3} + 1,\]

when \(n \equiv 2 \pmod{9}\), \(n \ge 11\).

5. Cycle

We denote the vertices and edges of a cycle \(C_n\) on \(n, n \ge 3\), vertices in the following way

\[V(C_n) = \{v_i : i = 1, 2, \dots, n\},\\]

On inclusive distance vertex irregular labelings | Martin Bača et al.

\[E(C_n) = \{v_i v_{i+1} : i = 1, 2, \dots, n-1\} \cup \{v_1 v_n\}.\]

As \(\Delta(C_n) = \delta(C_n) = 2\) using Lemma 2.1 we obtain a lower bound of the distance vertex irregularity strength of a cycle

\[\widehat{\operatorname{dis}}(C_n) \ge \left\lceil \frac{n+2}{3} \right\rceil. \tag{4}\]

As \(C_3\) is isomorphic to a complete graph \(K_3\) using Corollary 3.1 we get \(\widehat{\operatorname{dis}}(C_3) = \infty\). From a lower bound we get \(\widehat{\operatorname{dis}}(C_4) \geq 2\). But it is easy to prove that \(\widehat{\operatorname{dis}}(C_4) \geq 4\). The corresponding inclusive distance vertex irregular 4-labeling f of \(C_4\) is

\[f(v_i) = i\], for \(1 \le i \le 4\).

Some results for the inclusive distance vertex irregularity strength of cycles are obtained in [2]. Combining and extending these results we get the following.

Theorem 5.1. Let n be a positive integer \(n \geq 3\). Then

\[\widehat{\operatorname{dis}}(C_n) = \begin{cases} \infty, & \text{for } n = 3, \\ 4, & \text{for } n = 4, \\ \left\lceil \frac{n+2}{3} \right\rceil, & \text{for } n \not\equiv 2, 3, 4 \pmod{18}, n \ge 5 \end{cases}\]

and

\[\left\lceil \frac{n+2}{3} \right\rceil \le \widehat{\operatorname{dis}}(C_n) \le \left\lceil \frac{n+2}{3} \right\rceil + 1,\]

when \(n \equiv 2, 3, 4 \pmod{18}\), \(n \ge 20\).

According to (4) if we want to prove the equality it is suffices to describe the corresponding inclusive distance vertex irregular labelings for cycles. These labelings are given in Lemmas 5.1, 5.2, 5.3 and 5.4.

Lemma 5.1. Let n be a positive integer, \(n \equiv 5, 0, 1 \pmod{6}\), \(n \geq 5\). Then

\[\widehat{\operatorname{dis}}(C_n) = \left\lceil \frac{n+2}{3} \right\rceil.\]

Proof. Let \(n \equiv 1 \pmod{6}\), \(n \geq 7\). We define a vertex labeling \(f: V(C_n) \to \{1, 2, \dots, (n+2)/3\}\) of \(C_n\) in the following way

\[f(v_i) = 2 \left\lceil \frac{i}{3} \right\rceil - 1, \qquad \text{for } i = 1, 2, \dots, \frac{n+5}{2},\] \[f(v_i) = \frac{2(n-i)}{3} + 2, \qquad \text{for } i = \frac{n+7}{2}, \frac{n+13}{2}, \dots, n,\] \[f(v_i) = \frac{2(n-i+1)}{3} + 1, \quad \text{for } i = \frac{n+9}{2}, \frac{n+15}{2}, \dots, n-2,\] \[f(v_i) = \frac{2(n-i+2)}{3} + 1, \quad \text{for } i = \frac{n+11}{2}, \frac{n+17}{2}, \dots, n-1.\]

Evidently, the vertex labels are not greater that \(\lceil (n+2)/3 \rceil = (n+2)/3\). For the vertex weights we get

\[wt_f(v_1) = f(v_n) + f(v_1) + f(v_2) = \left(\frac{2(n-n)}{3} + 2\right) + \left(2\left\lceil\frac{1}{3}\right\rceil - 1\right) + \left(2\left\lceil\frac{2}{3}\right\rceil - 1\right) = 4,\]
\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left(2\left\lceil\frac{i-1}{3}\right\rceil - 1\right) + \left(2\left\lceil\frac{i}{3}\right\rceil - 1\right) + \left(2\left\lceil\frac{i+1}{3}\right\rceil - 1\right)\]
\[= 2i - 1,\]

for \[i = 2, 3, \dots, \frac{n+3}{2}\],

thus the corresponding weights are \(3, 5, \ldots, n+2\)

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

\[wt_f(v_{\frac{n+7}{2}}) = f(v_{\frac{n+5}{2}}) + f(v_{\frac{n+7}{2}}) + f(v_{\frac{n+9}{2}}) = \left(2\left\lceil \frac{n+5}{2} \right\rceil - 1\right) + \left(\frac{2\left(n - \frac{n+7}{2}\right)}{3} + 2\right) + \left(\frac{2\left(n - \frac{n+9}{2} + 1\right)}{3} + 1\right) = n - 1,\]

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left(\frac{2(n-(i-1))}{3} + 2\right) + \left(\frac{2(n-i+1)}{3} + 1\right) + \left(\frac{2(n-(i+1)+2)}{3} + 1\right) = 2n + 6 - 2i,\]

for \[i = \frac{n+9}{2}, \frac{n+15}{2}, \dots, n-2,\]

thus the corresponding weights are \(10, 16, \ldots, n-3\),

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left(\frac{2(n-(i-1)+1)}{3} + 1\right) + \left(\frac{2(n-i+2)}{3} + 1\right) + \left(\frac{2(n-(i+1))}{3} + 2\right) = 2n + 6 - 2i,\] for \(i = \frac{n+11}{2}, \frac{n+17}{2}, \dots, n-1\),

thus the corresponding weights are \(8, 14, \ldots, n-5\),

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left(\frac{2(n - (i-1) + 2)}{3} + 1\right) + \left(\frac{2(n - i)}{3} + 2\right) + \left(\frac{2(n - (i+1) + 1)}{3} + 1\right) = 2n + 6 - 2i,\] for \(i = \frac{n+13}{3}, \frac{n+19}{3}, \dots, n-3\),

thus the corresponding weights are \(12, 18, \ldots, n-7\),

\[wt_f(v_n) = f(v_{n-1}) + f(v_n) + f(v_n) + f(v_1) = \left(\frac{2(n-(n-1)+2)}{3} + 1\right) + \left(\frac{2(n-n)}{3} + 2\right) + \left(2\left\lceil \frac{1}{3}\right\rceil - 1\right) = 6.\]

Thus the vertex weights are distinct numbers from the set \(\{3, 4, \dots, n+2\}\). This means that f is an inclusive distance vertex irregular ((n+2)/3)-labeling. Combining this and (4), for \(n \equiv 1\)

(mod 6), n ≥ 7, we get

\[\widehat{\operatorname{dis}}(C_n) = \frac{n+2}{3}.\]

Let us consider the cycle Cn−¹ that we obtain from Cⁿ such that

\[C_{n-1} = C_n - \{v_2\} \cup \{v_1v_3\}.\]

It is easy to get that the restriction of the labeling f defined above on the graph Cn−¹ = Cⁿ − {v2} ∪ {v1v3} is an inclusive distance vertex irregular ((n + 2)/3)-labeling of Cn−1. In particular, the vertex weights are {4, 5, . . . , n + 2}. For n − 1 ≡ 0 (mod 6), n ≥ 7 according to (4) we get

\[\widehat{\operatorname{dis}}(C_{n-1}) \ge \left\lceil \frac{(n-1)+2}{3} \right\rceil = \frac{n+2}{3}.\]

This means that for n ≡ 0 (mod 6), n ≥ 6

\[\widehat{\operatorname{dis}}(C_n) = \left\lceil \frac{n+2}{3} \right\rceil.\]

Now we will deal with the case when the order of a cycle is congruent 5 modulo 6. We consider the cycle Cn−² obtained from Cⁿ by deleting two vertices and adding corresponding edges

\[C_{n-2} = C_n - \{v_2, v_5\} \cup \{v_1v_3, v_4v_6\}.\]

Again, the restriction of the labeling f defined above on the graph Cn−² = Cⁿ − {v2, v5} ∪ {v1v3, v4v6} is an inclusive distance vertex irregular ((n + 2)/3)-labeling of Cn−2. In particular, the vertex weights are {4, 5, . . . , 8, 10, 11, . . . , n + 2}. As (n − 2) ≡ 5 (mod 6), n ≥ 5 then according to (4)

\[\widehat{\operatorname{dis}}(C_{n-2}) \ge \left\lceil \frac{(n-2)+2}{3} \right\rceil = \frac{n+2}{3}.\]

This means that for n ≡ 5 (mod 6), n ≥ 5

\[\widehat{\operatorname{dis}}(C_n) = \left\lceil \frac{n+2}{3} \right\rceil.\]

Lemma 5.2. Let n be a positive integer, n ≡ 8, 9, 10 (mod 18), n ≥ 8. Then

\[\widehat{\operatorname{dis}}(C_n) = \left\lceil \frac{n+2}{3} \right\rceil.\]

Proof. Let n ≡ 10 (mod 18), n ≥ 10. We define a vertex labeling f : V (Cn) → {1, 2, . . . ,(n + 2)/3} in the following way

\[f(v_i) = \left\lceil \frac{i}{3} \right\rceil, \quad \text{for } i = 1, 2, \dots, \frac{n+5}{3},\] \[f(v_i) = \left\lceil \frac{i+1}{3} \right\rceil, \quad \text{for } i = \frac{n+8}{3}, \frac{n+11}{3}, \dots, \frac{2n-5}{3},\] \[f(v_i) = \left\lceil \frac{i+2}{3} \right\rceil, \quad \text{for } i = \frac{2n-2}{3}, \frac{2n+1}{3}, \dots, n.\]

Every vertex label is at most \(\lceil (n+2)/3 \rceil = (n+2)/3\). The vertex weights are

\[wt_f(v_1) = f(v_n) + f(v_1) + f(v_2) = \left\lceil \frac{n+2}{3} \right\rceil + \left\lceil \frac{1}{3} \right\rceil + \left\lceil \frac{2}{3} \right\rceil = \frac{n+8}{3},\] \[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{i-1}{3} \right\rceil + \left\lceil \frac{i}{3} \right\rceil + \left\lceil \frac{i+1}{3} \right\rceil = i+1,\] for \(i = 2, 3, \dots, \frac{n+2}{3}\),

thus the corresponding weights are \(3, 4, \ldots, \frac{n+5}{3}\),

\[\begin{split} wt_f(v_{\frac{n+5}{3}}) = & f(v_{\frac{n+2}{3}}) + f(v_{\frac{n+5}{3}}) + f(v_{\frac{n+8}{3}}) = \left\lceil \frac{\frac{n+2}{3}}{3} \right\rceil + \left\lceil \frac{\frac{n+5}{3}}{3} \right\rceil + \left\lceil \frac{\frac{n+8}{3}+1}{3} \right\rceil = \frac{n+11}{3}, \\ wt_f(v_{\frac{n+8}{3}}) = & f(v_{\frac{n+5}{3}}) + f(v_{\frac{n+8}{3}}) + f(v_{\frac{n+11}{3}}) = \left\lceil \frac{\frac{n+5}{3}}{3} \right\rceil + \left\lceil \frac{\frac{n+8}{3}+1}{3} \right\rceil + \left\lceil \frac{\frac{n+11}{3}+1}{3} \right\rceil = \frac{n+14}{3}, \\ wt_f(v_i) = & f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{(i-1)+1}{3} \right\rceil + \left\lceil \frac{i+1}{3} \right\rceil + \left\lceil \frac{(i+1)+1}{3} \right\rceil = i+2, \\ \text{for } i = \frac{n+11}{3}, \frac{n+14}{3}, \dots, \frac{2n-8}{3}, \end{split}\]

thus the corresponding weights are \(\frac{n+17}{3}, \frac{n+20}{3}, \dots, \frac{2n-2}{3},\)

\[wt_f(v_{\frac{2n-5}{3}}) = f(v_{\frac{2n-8}{3}}) + f(v_{\frac{2n-5}{3}}) + f(v_{\frac{2n-5}{3}}) = \left\lceil \frac{\frac{2n-8}{3}+1}{3} \right\rceil + \left\lceil \frac{\frac{2n-5}{3}+1}{3} \right\rceil + \left\lceil \frac{\frac{2n-2}{3}+2}{3} \right\rceil = \frac{2n+1}{3},\] \[wt_f(v_{\frac{2n-2}{3}}) = f(v_{\frac{2n-5}{3}}) + f(v_{\frac{2n-2}{3}}) + f(v_{\frac{2n+1}{3}}) = \left\lceil \frac{\frac{2n-5}{3}+1}{3} \right\rceil + \left\lceil \frac{\frac{2n-2}{3}+2}{3} \right\rceil + \left\lceil \frac{\frac{2n+1}{3}+2}{3} \right\rceil = \frac{2n+4}{3},\] \[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{(i-1)+2}{3} \right\rceil + \left\lceil \frac{i+2}{3} \right\rceil + \left\lceil \frac{(i+1)+2}{3} \right\rceil = i+3,\] \[\text{for } i = \frac{2n+1}{3}, \frac{2n+4}{3}, \dots, n-1,\]

thus the corresponding weights are \(\frac{2n+10}{3}, \frac{2n+13}{3}, \dots, n+2\),

\[wt_f(v_n) = f(v_{n-1}) + f(v_n) + f(v_n) = \left\lceil \frac{(n-1)+2}{3} \right\rceil + \left\lceil \frac{n+2}{3} \right\rceil + \left\lceil \frac{1}{3} \right\rceil = \frac{2n+7}{3}.\]

The set of vertex weights consists of numbers \(\{3, 4, \ldots, n+2\}\). This means that f is an inclusive distance vertex irregular ((n+2)/3)-labeling. Thus, using (4), for \(n \equiv 10 \pmod{18}\), \(n \geq 10\), we have

\[\widehat{\operatorname{dis}}(C_n) = \frac{n+2}{3}.\]

As in the proof of the previous lemma we use the above described labeling to obtain ((n+2)/3)labelings of \(C_{n-1}\) and \(C_{n-2}\).

The cycle \(C_{n-1}\) we obtain from \(C_n\) such that

\[C_{n-1} = C_n - \{v_2\} \cup \{v_1v_3\}.\]

The restriction of the labeling f defined above on the graph \(C_{n-1} = C_n - \{v_2\} \cup \{v_1v_3\}\) is an inclusive distance vertex irregular ((n+2)/3)-labeling of \(C_{n-1}\). The vertex weights are \(\{4, 5, \ldots, n+2\}\). As \((n-1) \equiv 9 \pmod{18}\), n > 10 then according to (4)

\[\widehat{\operatorname{dis}}(C_{n-1}) \ge \left\lceil \frac{(n-1)+2}{3} \right\rceil = \frac{n+2}{3}.\]

This means that for \(n \equiv 9 \pmod{18}\), \(n \geq 9\)

\[\widehat{\operatorname{dis}}(C_n) = \left\lceil \frac{n+2}{3} \right\rceil.\]

If \(n \equiv 8 \pmod{18}\), \(n \geq 8\) let us consider the cycle \(C_{n-2}\) obtained from \(C_n\) by deleting two vertices and adding corresponding edges

\[C_{n-2} = C_n - \{v_2, v_{n-1}\} \cup \{v_1v_3, v_nv_{n-2}\}.\]

It is easy to see that the restriction of the labeling f defined above on the graph \(C_{n-2} = C_n - \{v_2, v_{n-1}\} \cup \{v_1v_3, v_nv_{n-2}\}\) is an inclusive distance vertex irregular ((n+2)/3)-labeling of \(C_{n-2}\). The set of vertex weights is \(\{4, 5, \ldots, n+1\}\). As \((n-2) \equiv 8 \pmod{18}\), \(n \geq 10\) then according to (4)

\[\widehat{\operatorname{dis}}(C_{n-2}) \ge \left\lceil \frac{(n-2)+2}{3} \right\rceil = \frac{n+2}{3}.\]

Thus for \(n \equiv 8 \pmod{18}\), \(n \ge 8\)

\[\widehat{\operatorname{dis}}(C_n) = \left\lceil \frac{n+2}{3} \right\rceil.\]

Lemma 5.3. Let n be a positive integer, \(n \equiv 14, 15, 16 \pmod{18}\), \(n \geq 8\). Then

\[\widehat{\operatorname{dis}}(C_n) = \left\lceil \frac{n+2}{3} \right\rceil.\]

Proof. Let \(n \equiv 16 \pmod{18}\), \(n \geq 16\). We consider a labeling \(f: V(C_n) \to \{1, 2, \dots, (n+2)/3\}\) defined such that

\[f(v_i) = \left\lceil \frac{i}{3} \right\rceil, \qquad \text{for } i = 1, 2, \dots, \frac{n+5}{3},\] \[f(v_i) = \left\lceil \frac{i+2}{3} \right\rceil, \qquad \text{for } i = \frac{n+8}{3}, \frac{n+17}{3}, \dots, \frac{2n-8}{3},\] \[f(v_i) = \left\lceil \frac{i+2}{3} \right\rceil - 1, \quad \text{for } i = \frac{n+11}{3}, \frac{n+20}{3}, \dots, \frac{2n-5}{3},\] \[f(v_i) = \left\lceil \frac{i+2}{3} \right\rceil, \qquad \text{for } i = \frac{n+14}{3}, \frac{n+23}{3}, \dots, \frac{2n-2}{3},\] \[f(v_i) = \left\lceil \frac{i+2}{3} \right\rceil, \qquad \text{for } i = \frac{2n+1}{3}, \frac{2n+4}{3}, \dots, n.\]

The numbers used as vertex labels are not greater than \(\lceil (n+2)/3 \rceil = (n+2)/3\). For the vertex weights we have the following

\[wt_f(v_1) = f(v_n) + f(v_1) + f(v_2) = \left\lceil \frac{n+2}{3} \right\rceil + \left\lceil \frac{1}{3} \right\rceil + \left\lceil \frac{2}{3} \right\rceil = \frac{n+8}{3},\]
\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{i-1}{3} \right\rceil + \left\lceil \frac{i}{3} \right\rceil + \left\lceil \frac{i+1}{3} \right\rceil = i+1,\]
for \(i = 2, 3, \dots, \frac{n+2}{3}\),

thus the corresponding weights are \(3, 4, \ldots, \frac{n+5}{3}\),

\[wt_f(v_{\frac{n+5}{3}}) = f(v_{\frac{n+2}{3}}) + f(v_{\frac{n+5}{3}}) + f(v_{\frac{n+8}{3}}) = \left[\frac{\frac{n+2}{3}}{\frac{3}{3}}\right] + \left[\frac{\frac{n+5}{3}}{\frac{3}{3}}\right] + \left[\frac{\frac{n+8}{3}+2}{3}\right] = \frac{n+11}{3},\]

On inclusive distance vertex irregular labelings | Martin Bača et al.

\[wt_f(v_{\frac{n+8}{3}}) = f(v_{\frac{n+5}{3}}) + f(v_{\frac{n+8}{3}}) + f(v_{\frac{n+11}{3}}) = \left\lceil \frac{\frac{n+5}{3}}{\frac{3}{3}} \right\rceil + \left\lceil \frac{\frac{n+8}{3} + 2}{3} \right\rceil + \left( \left\lceil \frac{\frac{n+11}{3} + 2}{3} \right\rceil - 1 \right)\]\[= \frac{n+14}{3},\]

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{(i-1)+2}{3} \right\rceil + \left( \left\lceil \frac{i+2}{3} \right\rceil - 1 \right) + \left\lceil \frac{(i+1)+2}{3} \right\rceil = i+2,\] \[\text{for } i = \frac{n+11}{3}, \frac{n+20}{3}, \dots, \frac{2n-5}{3},\]

thus the corresponding weights are \(\frac{n+17}{3}, \frac{n+26}{3}, \dots, \frac{2n+1}{3}\),

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left( \left\lceil \frac{(i-1)+2}{3} \right\rceil - 1 \right) + \left\lceil \frac{i+2}{3} \right\rceil + \left\lceil \frac{(i+1)+2}{3} \right\rceil = i+2,\] for \(i = \frac{n+14}{3}, \frac{n+23}{3}, \dots, \frac{2n-11}{3},\)

thus the corresponding weights are \(\frac{n+20}{3}, \frac{n+29}{3}, \dots, \frac{2n-5}{3},\)

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{(i-1)+2}{3} \right\rceil + \left\lceil \frac{i+2}{3} \right\rceil + \left( \left\lceil \frac{(i+1)+2}{3} \right\rceil - 1 \right) = i+2,\] for \(i = \frac{n+17}{3}, \frac{n+26}{3}, \dots, \frac{2n-8}{3}\),

thus the corresponding weights are \(\frac{n+23}{3}, \frac{n+32}{3}, \dots, \frac{2n-2}{3},\)

\[wt_f(v_{\frac{2n-2}{3}}) = f(v_{\frac{2n-5}{3}}) + f(v_{\frac{2n-2}{3}}) + f(v_{\frac{2n+1}{3}}) = \left( \left\lceil \frac{\frac{2n-5}{3} + 2}{3} \right\rceil - 1 \right) + \left\lceil \frac{\frac{2n-2}{3} + 2}{3} \right\rceil + \left\lceil \frac{\frac{2n+1}{3} + 2}{3} \right\rceil = \frac{2n+4}{2},\]

\[wt_f(v_{\frac{2n+1}{3}}) = f(v_{\frac{2n-2}{3}}) + f(v_{\frac{2n+1}{3}}) + f(v_{\frac{2n+4}{3}}) = \left\lceil \frac{2n-2}{3} + 2 \right\rceil + \left\lceil \frac{2n+1}{3} + 2 \right\rceil + \left\lceil \frac{2n+4}{3} + 2 \right\rceil = \frac{2n+10}{3},\]

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{(i-1)+2}{3} \right\rceil + \left\lceil \frac{i+2}{3} \right\rceil + \left\lceil \frac{(i+1)+2}{3} \right\rceil = i+3,\]
for \(i = \frac{2n+4}{3}, \frac{2n+7}{3}, \dots, n-1,\)

thus the corresponding weights are \(\frac{2n+13}{3}\), \(\frac{2n+16}{3}\), ..., n+2,

\[wt_f(v_n) = f(v_{n-1}) + f(v_n) + f(v_n) = \left\lceil \frac{(n-1)+2}{3} \right\rceil + \left\lceil \frac{n+2}{3} \right\rceil + \left\lceil \frac{1}{3} \right\rceil = \frac{2n+7}{3}.\]

The set of vertex weights consists of numbers \(\{3, 4, \ldots, n+2\}\). This means that f is an inclusive distance vertex irregular ((n+2)/3)-labeling. Thus for \(n \equiv 16 \pmod{18}\), \(n \geq 16\), using (4), we obtain

\[\widehat{\operatorname{dis}}(C_n) = \frac{n+2}{3}.\]

Now we describe ((n+2)/3)-labelings of cycles \(C_{n-1}\) and \(C_{n-2}\). First we consider the cycle \(C_{n-1}\) obtained from the cycle \(C_n\) such that

\[C_{n-1} = C_n - \{v_2\} \cup \{v_1v_3\}.\]

The restriction of the labeling f defined above on the graph \(C_{n-1} = C_n - \{v_2\} \cup \{v_1v_3\}\) is an inclusive distance vertex irregular ((n+2)/3)-labeling of \(C_{n-1}\). The vertex weights are \(\{4, 5, \ldots, n+2\}\). According to (4) and as \((n-1) \equiv 15 \pmod{18}\), \(n \geq 16\) we get

\[\widehat{\operatorname{dis}}(C_{n-1}) \ge \left\lceil \frac{(n-1)+2}{3} \right\rceil = \frac{n+2}{3}.\]

Thus for \(n \equiv 15 \pmod{18}\), \(n \ge 15\)

\[\widehat{\operatorname{dis}}(C_n) = \left\lceil \frac{n+2}{3} \right\rceil.\]

Now we will deal with the cycle \(C_{n-2}\) obtained from \(C_n\) such that

\[C_{n-2} = C_n - \{v_2, v_{n-1}\} \cup \{v_1v_3, v_nv_{n-2}\}.\]

Evidently, the restriction of the labeling f defined above on the graph \(C_{n-2} = C_n - \{v_2, v_{n-1}\} \cup \{v_1v_3, v_nv_{n-2}\}\) is an inclusive distance vertex irregular ((n+2)/3)-labeling of \(C_{n-2}\). The set of vertex weights is \(\{4, 5, \ldots, n+1\}\). As \((n-2) \equiv 14 \pmod{18}\), \(n \geq 16\) then according to (4)

\[\widehat{\operatorname{dis}}(C_{n-2}) \ge \left\lceil \frac{(n-2)+2}{3} \right\rceil = \frac{n+2}{3}.\]

Thus for \(n \equiv 14 \pmod{18}\), \(n \ge 14\)

\[\widehat{\operatorname{dis}}(C_n) = \left\lceil \frac{n+2}{3} \right\rceil.\]

Lemma 5.4. Let n be a positive integer, \(n \equiv 2, 3, 4 \pmod{18}\), \(n \geq 20\). Then

\[\left\lceil \frac{n+2}{3} \right\rceil \le \widehat{\operatorname{dis}}(C_n) \le \left\lceil \frac{n+2}{3} \right\rceil + 1.\]

Proof. The lower bound follows from (4). The upper bound we prove by describing the corresponding ((n+2)/3+1)-labelings of cycles \(C_n\).

Let \(n \equiv 4 \pmod{18}\), \(n \geq 22\). We consider a labeling \(f: V(C_n) \to \{1, 2, \dots, (n+2)/3+1\}\) of vertices of \(C_n\) defined such that

\[f(v_i) = \left\lceil \frac{i}{3} \right\rceil, \qquad \text{for } i = 1, 2, \dots, \frac{n+8}{3},\] \[f(v_i) = \left\lceil \frac{i+2}{3} \right\rceil, \qquad \text{for } i = \frac{n+11}{3}, \frac{n+14}{3}, \dots, \frac{n}{2},\] \[f(v_i) = \left\lceil \frac{i}{3} \right\rceil + 1, \qquad \text{for } i = \frac{n}{2} + 1, \frac{n}{2} + 2, \dots, \frac{2n-8}{3},\] \[f(v_i) = \left\lceil \frac{i+2}{3} \right\rceil + 1, \qquad \text{for } i = \frac{2n-5}{3}, \frac{2n-2}{3}, \dots, n.\]

Every vertex label is smaller or equal to \(\lceil (n+2)/3 \rceil + 1 = (n+2)/3 + 1\). The vertex weights under the labeling f are

\[wt_f(v_1) = f(v_n) + f(v_1) + f(v_2) = \left( \left\lceil \frac{n+2}{3} \right\rceil + 1 \right) + \left\lceil \frac{1}{3} \right\rceil + \left\lceil \frac{2}{3} \right\rceil = \frac{n+11}{3},\]
\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left\lceil \frac{i-1}{3} \right\rceil + \left\lceil \frac{i}{3} \right\rceil + \left\lceil \frac{i+1}{3} \right\rceil = i+1,\]
for \(i = 2, 3, \dots, \frac{n+5}{3}\),

thus the corresponding weights are \(3, 4, \ldots, \frac{n+8}{3}\),

\[wt_f(v_{\frac{n+8}{3}}) = f(v_{\frac{n+5}{3}}) + f(v_{\frac{n+8}{3}}) + f(v_{\frac{n+11}{3}}) = \left\lceil \frac{n+5}{3} \right\rceil + \left\lceil \frac{n+8}{3} \right\rceil + \left\lceil \frac{n+11}{3} + 2 \right\rceil = \frac{n+14}{3},\]

On inclusive distance vertex irregular labelings | Martin Bača et al.

\[wt_f(v_{\frac{n+11}{3}}) = f(v_{\frac{n+8}{3}}) + f(v_{\frac{n+11}{3}}) + f(v_{\frac{n+14}{3}}) = \begin{bmatrix} \frac{n+8}{3} \\ \frac{n+14}{3} \end{bmatrix} + \begin{bmatrix} \frac{n+11}{3} + 2 \\ \frac{n+14}{3} \end{bmatrix} + \begin{bmatrix} \frac{n+14}{3} + 2 \\ \frac{n+14}{3} \end{bmatrix} = \frac{n+20}{3},\] \[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \begin{bmatrix} \frac{(i-1)+2}{3} \end{bmatrix} + \begin{bmatrix} \frac{i+2}{3} \end{bmatrix} + \begin{bmatrix} \frac{(i+1)+2}{3} \end{bmatrix} = i+3,\] \[\text{for } i = \frac{n+14}{3}, \frac{n+17}{3}, \dots, \frac{n}{2} - 1,\]

thus the corresponding weights are \(\frac{n+23}{3}, \frac{n+26}{3}, \dots, \frac{n}{2}+2\),

\[wt_f(v_{\frac{n}{2}}) = f(v_{\frac{n-2}{2}}) + f(v_{\frac{n}{2}}) + f(v_{\frac{n+2}{2}}) = \left\lceil \frac{n-2}{2} + 2 \right\rceil + \left\lceil \frac{n}{2} + 2 \right\rceil + \left( \left\lceil \frac{n+2}{2} \right\rceil + 1 \right) = \frac{n}{2} + 3,\] \[wt_f(v_{\frac{n+2}{2}}) = f(v_{\frac{n}{2}}) + f(v_{\frac{n+2}{2}}) + f(v_{\frac{n+4}{2}}) = \left\lceil \frac{n}{2} + 2 \right\rceil + \left( \left\lceil \frac{n+2}{2} \right\rceil + 1 \right) + \left( \left\lceil \frac{n+4}{2} \right\rceil + 1 \right)\] \[= \frac{n}{2} + 5,\]

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left( \left\lceil \frac{i-1}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{i}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{i+1}{3} \right\rceil + 1 \right) = i + 4,\] for \(i = \frac{n}{2} + 2, \frac{n}{2} + 3, \dots, \frac{2n-11}{3},\)

thus the corresponding weights are \(\frac{n}{2} + 6, \frac{n}{2} + 7, \dots, \frac{2n+1}{3}\),

\[wt_f(v_{\frac{2n-8}{3}}) = f(v_{\frac{2n-11}{3}}) + f(v_{\frac{2n-8}{3}}) + f(v_{\frac{2n-5}{3}}) = \left( \left\lceil \frac{\frac{2n-11}{3}}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{\frac{2n-8}{3}}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{\frac{2n-8}{3}}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{2n-8}{3} \right\rceil + 1 \right) = \frac{2n+4}{3},\]

\[wt_f(v_{\frac{2n-5}{3}}) = f(v_{\frac{2n-8}{3}}) + f(v_{\frac{2n-5}{3}}) + f(v_{\frac{2n-5}{3}}) = \left( \left\lceil \frac{\frac{2n-8}{3}}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{\frac{2n-5}{3}+2}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{\frac{2n-5}{3}+2}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{\frac{2n-5}{3}+2}{3} \right\rceil + 1 \right) = \frac{2n+10}{3},\]

\[wt_f(v_i) = f(v_{i-1}) + f(v_i) + f(v_{i+1}) = \left( \left\lceil \frac{(i-1)+2}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{i+2}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{(i+1)+2}{3} \right\rceil + 1 \right) = i + 6.\]

for \[i = \frac{2n-2}{3}, \frac{2n+1}{3}, \dots, n-1\],

thus the corresponding weights are \(\frac{2n+16}{3}\), \(\frac{2n+19}{3}\), ..., n+5,

\[wt_f(v_n) = f(v_{n-1}) + f(v_n) + f(v_n) + f(v_1) = \left( \left\lceil \frac{(n-1)+2}{3} \right\rceil + 1 \right) + \left( \left\lceil \frac{n+2}{3} \right\rceil + 1 \right) + \left\lceil \frac{1}{3} \right\rceil = \frac{2n+13}{3}\]

The set of vertex weights consist of numbers \(\{3,4,\ldots,\frac{n+14}{3},\frac{n+20}{3},\frac{n+23}{3},\ldots,\frac{n}{2}+3,\frac{n}{2}+5,\frac{n}{2}+6,\ldots,\frac{2n+4}{3},\frac{2n+10}{3},\frac{2n+13}{3},\ldots,n+5\}\). This means that f is an inclusive distance vertex irregular ((n+2)/3+1)-labeling. Thus for \(n\equiv 4\pmod{18}\), \(n\geq 22\)

\[\widehat{\operatorname{dis}}(C_n) \le \frac{n+2}{3} + 1.\]

First we consider the cycle \(C_{n-1}\) obtained from \(C_n\) in the following way

\[C_{n-1} = C_n - \{v_2\} \cup \{v_1v_3\}.\]

The restriction of the labeling f defined above on the graph \(C_{n-1} = C_n - \{v_2\} \cup \{v_1v_3\}\) is an inclusive distance vertex irregular ((n+2)/3+1)-labeling of \(C_{n-1}\). The vertex weights are

\(\{4, 5, \dots, \frac{n+14}{3}, \frac{n+20}{3}, \frac{n+23}{3}, \dots, \frac{n}{2} + 3, \frac{n}{2} + 5, \frac{n}{2} + 6, \dots, \frac{2n+4}{3}, \frac{2n+10}{3}, \frac{2n+13}{3}, \dots, n+5\}\). Thus for \(n \equiv 3 \pmod{18}, n \ge 21\)

\[\widehat{\operatorname{dis}}(C_n) \le \left\lceil \frac{n+2}{3} \right\rceil + 1.\]

Now let us consider the cycle \(C_{n-2}\) obtained from \(C_n\) such that

\[C_{n-2} = C_n - \{v_2, v_{n-1}\} \cup \{v_1v_3, v_nv_{n-2}\}.\]

It is easy to see that the restriction of the labeling f defined above on the graph \(C_{n-2}=C_n-\{v_2,v_{n-1}\}\cup\{v_1v_3,v_nv_{n-2}\}\) is an inclusive distance vertex irregular ((n+2)/3+1)-labeling of \(C_{n-2}\). The vertex weights are distinct numbers from the set \(\{4,5,\ldots,\frac{n+14}{3},\frac{n+20}{3},\frac{n+23}{3},\ldots,\frac{n}{2}+3,\frac{n}{2}+5,\frac{n}{2}+6,\ldots,\frac{2n+4}{3},\frac{2n+10}{3},\frac{2n+13}{3},\ldots,n+4\}\). However, this proves that for \(n\equiv 2\pmod{18}\), \(n\geq 20\)

\[\widehat{\operatorname{dis}}(C_n) \le \left\lceil \frac{n+2}{3} \right\rceil + 1.\]

The join of a cycle \(C_n\), \(n \ge 3\), and a complete graph \(K_1\) is a graph known as a wheel \(W_n\). Thus from Theorems 5.1 and 3.2, we have the following.

Theorem 5.2. Let n be a positive integer \(n \geq 3\). Then

\[\widehat{\operatorname{dis}}(W_n) = \begin{cases} \infty, & \text{for } n = 3, \\ 4, & \text{for } n = 4, \\ \left\lceil \frac{n+2}{3} \right\rceil, & \text{for } n \not\equiv 2, 3, 4 \pmod{18}, n \ge 5 \end{cases}\]

and

\[\left\lceil \frac{n+2}{3} \right\rceil \le \widehat{\operatorname{dis}}(W_n) \le \left\lceil \frac{n+2}{3} \right\rceil + 1,\]

when \(n \equiv 2, 3, 4 \pmod{18}\), \(n \ge 20\).

While Bong et al. [2] also proved that \(\widehat{\operatorname{dis}}(W_n) = \widehat{\operatorname{dis}}(C_n)\).

6. Conclusion

In the foregoing sections we studied the existence of inclusive vertex irregular distance labelings of graphs. We established a lower bound of the distance vertex irregularity strength and determined the exact value of this parameter for complete and complete bipartite graphs and for join graphs \(G \oplus K_1\).

For a path \(P_n\) we determined the exact value of the inclusive distance vertex irregularity strength for every \(n \ge 2\) except for \(n \equiv 2 \pmod{9}\), when \(n \ge 11\). For \(n \equiv 2 \pmod{9}\), \(n \ge 11\), we found only an upper bound. Consequently, we propose the following open problem.

Problem 6.1. For a path \(P_n\), \(n \equiv 2 \pmod{9}\), \(n \geq 11\), determine the exact value of the inclusive distance vertex irregularity strength.

For cycle Cⁿ we determined the exact value of the inclusive distance vertex irregularity strength for every n ≥ 3 except for n ≡ 2, 3, 4 (mod 18) when n ≥ 20. For these values of n we described the inclusive diatance vertex irregular (d(n + 2)/3e + 1)-labeling which gives an upper bound of the inclusive distance vertex irregularity strength. So, we suggest the following open problem.

Problem 6.2. For the cycle Cn, n ≡ 2, 3, 4 (mod 18), n ≥ 20, determine the exact value of the inclusive distance vertex irregularity strength.

For both cases mentioned in Problems 6.1 and 6.2 we suppose that the corresponding parameters reach the lower bounds.

According to obtained results for inclusive distance vertex irregularity strength of paths, cycles, fan graphs and wheels it seems that the subgraph relation posses the hereditary properties with respect to dis( ^{c G}). We state the following open problem.

Problem 6.3. Determine if \[H \subset G\] implies \(\widehat{\operatorname{dis}}(H) \leq \widehat{\operatorname{dis}}(G)\).

Another interesting problem is whether the corresponding hereditary properties are preserved also for other graph operations, for example Cartesian product or subdivision of edges.

Acknowledgement

This work was supported by the Slovak Science and Technology Assistance Agency under the contract No. APVV-15-0116 and by VEGA 1/0233/18.

References

• [1] S. Arumugam, D. Froncek and N. Kamatchi, Distance magic graphs a survey, ˇ J. Indones. Math. Soc., Special Ed. (2011), 11–26.
• [2] N.H. Bong, Y. Lin and Slamin, On inclusive and non-inclusive vertex irregular d-distance vertex labelings, preprint.
• [3] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988), 187–192.
• [4] J.A. Gallian, A dynamic survey of graph labelings, Electron. J. Combin. 19 (2016), # DS6.
• [5] M. Miller, C. Rodger and R. Simanjuntak, Distance magic labelings of graphs, Australas. J. Combin. 28 (2003), 305–315.
• [6] Slamin, On distance irregular labelings of graphs, Far East Journal of Mathematical Sciences (FJMS) 102(5) (2017), 919–932.