A Note on Distance Irregular Labeling of Graphs

1. Introduction

Let \(G\) be a simple connected and undirected graph with vertex set \(V(G)\) and edge set \(E(G)\). The labeling of a graph is a mapping that carries a set of graph elements (vertices or edges or both) onto a set of numbers (usually positive integers). In a a complete survey on labelings [1], many types of graph labelings are studied.

In 2003, Miller et al. [2] introduced “ \(1\)-vertex-magic labeling” which is obtained by combining magic labelings and distance labelings. The weight of a vertex \(u\) is defined as: \(wt(u)=\sum\limits_{v\in N(u)} \phi(v)\), where \(N(u)\) is the open neighbourhood of \(u.\)

In 1988, Chartrand et al. [3] introduced the notion of irregular labeling. In this labeling, we determine the weights (the sum of edge labels incident to a vertex) of each vertex are distinct such that minimum largest label that we can assign to the edges of a graph. This minimum largest label is known as irregularity strength of the graph.

Slamin [4] combined the distance and the irregular labeling to be the distance irregular vertex \(k\)-labeling. For a graph \(G,\) a \(k\)-labeling \(\phi: V(G)\to \{1,2, \dots, k\}\) to be a distance irregular vertex \(k\)-labeling of the graph \(G\) if for every two different vertices \(u\) and \(v\) of \(G\) one has \(wt(u) \ne wt(v)\) where the weight of a vertex \(u\) in the labeling \(\phi\) is \[wt(u)=\sum\limits_{v\in N(u)}\phi(v),\] where \(N(u)\) is the set of neighbors of \(u\). The minimum \(k\) for which the graph \(G\) has a distance irregular vertex \(k\)-labeling is known as distance irregularity strength of \(G,\) it is denoted as \(dis(G).\)

Slamin [4] determined the distance irregularity strength for complete graphs, paths, cycles \(C_n\) and wheels \(W_n, n\ge5, n\equiv 0,1,2,5\pmod8\). Bong et al. [5] determined the distance irregularity strength of cycle \(C_n\) and wheel \(W_n\) for \(n\ge5, n\equiv 3,4,6,7\pmod8\).

2. Main Results

Some important observations in [4] regarding the distance irregular labeling are:

Observation 1. [4] Let \(u\) and \(w\) be any two distinct vertices in a connected graph \(G.\) If \(u\) and \(w\) have identical neighbours, i.e., \(N(u) = N(w),\) then \(G\) has no distance irregular vertex labeling.

Observation 2. [4] Let \(u\) and \(w\) be two adjacent vertices in a connected graph \(G.\) If \(N(u)-w = N(w)-u,\) then the labels of \(u\) and \(w\) must be distinct, that is, \( \phi(u) \ne \phi(w).\)

From these Observations, one can easily see that not all graphs have distance irregular vertex labelings, for example complete bipartite and multipartite graphs, and trees that contain a vertex with at least two leaves. The lower bound for distance irregularity strength for connected graphs in general is given by Slamin [4] in Lemma 1.

Lemma 1. Let \(G\) be a connected graph on \(v\) vertices with minimum degree \(\delta\) and maximum degree \(\Delta\) and such that there is no vertex having identical neighbors. Then \(dis(G) \ge \lceil \frac{v+\delta-1}{\Delta}\rceil.\)

This bound is improved in the following theorem.

Theorem 3. Let \(G=(V,E)\) be a graph with maximum degree \(\triangle(G)\) and minimum degree \(\delta(G),\) then \begin{equation*} dis(G) \ge \max \limits_{{j=0}}^{\triangle (G)} \left \{\left\lceil \frac{(\sum \limits_{t=1}^{j}m_p)+\delta (G)-1}{j} \right\rceil \right\}, \end{equation*}

where \(m_j\) represents number of vertices of degree \(j\) in \(G.\)

Proof. Let \(G=(V,E)\) be any connected graph with \(\triangle(G)\), \(\delta(G)\) and\(m_j\), \(\delta(G) \le j\le \Delta(G)\) represents the maximum degree, minimum degree and number of vertices of degree \(j\) in \(G\). Let \(t=\max \limits_{{j=\delta(G)}}^{\triangle(G)} \Bigg \{\Bigg\lceil \frac{(\sum \limits_{p=\delta(G)}^{j}m_p)+\delta(G)-1}{j} \Bigg\rceil \Bigg\}.\) Assume that \(t= \Bigg\lceil \frac{(\sum \limits_{{j=\delta(G)}}^im_i)+\delta(G)-1}{i} \Bigg\rceil ,\) for some \(i.\) In any distance irregular vertex \(k-\)labeling on \(G\) the smallest weight among all vertices of degree \(j \ge \delta(G)\) and \(j\) is at least \(\delta(G)\) and the largest of them is at least \((\sum \limits_{{j=\delta}}^im_j)+\delta(G)-1.\) Thus the value of \(k\) will be minimum if the largest weight is at the vertex of degree \(i.\) Since the weight of any vertex of degree \(i\) is the sum of \(i\) positive labels, so at least one label is at least \(\Bigg\lceil \frac{(\sum \limits_{{j=\delta(G)}}^im_j)+\delta(G)-1}{i} \Bigg\rceil.\) Therefore the minimum value of the \(k\) is at least \(t\). This gives \[\max \limits_{{j=\delta(G)}}^{\triangle(G)} \Bigg \{\Bigg\lceil \frac{(\sum \limits_{p=\delta(G)}^{j}m_p)+\delta(G)-1}{j} \Bigg\rceil \Bigg\} \le dis(G) \] and we are done.

The corona product of two graphs \(G\) and \(H\), denoted by \(G\odot H,\) is a graph obtained by taking one copy of \(G\) (which has \(n\) vertices) and \(n\) copies \(H_1,H_2, \dots, H_n\) of \(H,\) and then joining the \(i\)-th vertex of \(G\) to every vertex in \(H_i.\) In the next two Theorems, we determined the distance irregularity strength of the corona product of cycle and path with complete graph \(K_1.\)

Theorem 4. Let \(C_n\odot K_1\) be the graph of corona product of cycle \(C_n\) and \(K_1,\) then distance irregularity strength of \(C_n\odot K_1\) is \( dis(C_n\odot K_1)=n,\) for \(n\ge 3.\)

Proof. The vertex set and edge set of \(C_n\odot K_1\) are \(V(C_n\odot K_1)=\{a_i, b_i: 1 \le i \le n\},\) \(E(C_n\odot K_1)=\{a_ib_i: 1 \le i \le n\}\cup\{a_ia_{i+1}: 1 \le i \le n-1\}\cup\{a_na_1\},\) respectively. The graph \(C_n\odot K_1\) contains \(n\) vertices of degree one and \(n\) vertices of degree three. The lower bound of \(C_n\odot K_1\) follows from Theorem 3. To show that \(n\) is an upper bound for distance irregularity strength of \(C_n\odot K_1,\) we describe a vertex \(n\)-labeling \(\phi:V(C_n\odot K_1)\to \{1,2,\dots, n \}\) for \(n\ge 3\) as follows: \[ \begin{array}{rcll} \phi(a_i)&=&i, {\rm for}\ 1\le i \le n.\\ \phi(b_i)& = & \lfloor\frac{n}{2}\rfloor, & {\rm for}\ i=1,n\\ \phi(b_i)& = & n-1-i, & {\rm for}\ 2 \le i \le \lfloor\frac{n}{2}\rfloor \\ \phi(b_i)& = &\lfloor\frac{n}{2}\rfloor, & {\rm for}\ i= \lfloor\frac{n}{2}\rfloor+1, \, n\,\, {\rm odd}\ \\ \phi(b_i)& = &\lfloor\frac{n}{2}\rfloor-1, & {\rm for}\ i= \lfloor\frac{n}{2}\rfloor+1, \, n\,\, {\rm even}\ \\ \phi(b_i)& = & n+1-i, & {\rm for}\ \lfloor\frac{n}{2}\rfloor+2 \le i \le n-1 \\ \end{array} \] This labeling gives the weight of the vertices as follows: \[ \begin{array}{rcll} wt(b_i)& = & i, & {\rm for}\ 1 \le i \le n \\ wt(a_i) & = & n+2+\lfloor\frac{n}{2}\rfloor, & {\rm for}\ i=1 \\ wt(a_i) & = & n-1+i, & {\rm for}\ 2 \le i \le \lfloor\frac{n}{2}\rfloor \\ wt(a_i) & = & n+1+\lfloor\frac{n}{2}\rfloor, & {\rm for}\ i = \lfloor\frac{n}{2}\rfloor+1 \\ wt(a_i) & = & n+1+i, & {\rm for}\ \lfloor\frac{n}{2}\rfloor+2 \le i\le n-1 \\ wt(a_i) & = & n+\lfloor\frac{n}{2}\rfloor, & {\rm for}\ i=n \\ \end{array} \] It is easy to check that the weight of the vertices are distinct. The above constructions show that \[dis(C_n\odot K_1) \le n.\] Combining with the lower bounds, we conclude that \[dis(C_n\odot K_1)= n.\]

Theorem 5. Let \(P_n\odot K_1\) be the graph of corona product of path \(P_n\) and \(K_1,\) then distance irregularity strength of \(P_n\odot K_1\) is \( dis(P_n\odot K_1)=n,\) for \(n\ge 3.\)

Proof. The vertex set and edge set of \(P_n\odot K_1\) are \(V(P_n\odot K_1)=\{x_i, y_i: 1 \le i \le n\},\) \(E(P_n\odot K_1)=\{x_iy_i: 1 \le i \le n\}\cup\{x_ix_{i+1}: 1 \le i \le n-1\},\) respectively. The graph \(P_n\odot K_1\) contains \(n\) vertices of degree one, two vertices of degree two and \(n-2\) vertices of degree three. The lower bound of \(P_n\odot K_1\) follows from Theorem 3. To show that \(n\) is an upper bound for distance irregularity strength of \(P_n\odot K_1,\) we describe a vertex \(n\)-labeling \(\phi:V(P_n\odot K_1)\to \{1,2,\dots, n \}\) for \(n\ge 3\) as follows: \[ \begin{array}{rcll} \phi(x_i)&=&i, {\rm for}\ 1\le i \le n.\\ \phi(y_i)& = & n-1, & {\rm for}\ 2 \le i \le n-1\\ \phi(y_i)& = & 3, & {\rm for}\ i=n \\ \end{array} \] This labeling gives the weight of the vertices as follows: \[ \begin{array}{rcll} wt(y_i)& = & i, & {\rm for}\ 1 \le i \le n \\ wt(x_i) & = & n+1, & {\rm for}\ i=1 \\ wt(x_i) & = & n+2i-1, & {\rm for}\ 2\le i \le n-1 \\ wt(x_i) & = & n+2, & {\rm for}\ i=n \\ \end{array} \] It is easy to check that the weight of the vertices are distinct. The above constructions show that \[dis(P_n\odot K_1) \le n.\] Combining with the lower bounds, we conclude that \[dis(P_n\odot K_1)= n.\]

The friendship graph \(F_m\) is a set of \(m\) triangles having a common central vertex, and otherwise disjoint. In the next Theorem, we determined the distance irregularity strength of friendship graph \(F_m.\)

Theorem 6. The distance irregularity strength of friendship graph \(F_m\) is \( dis(F_m)=2m,\) for \(m\ge 3.\)

Proof. The friendship graph \(F_m\) has \(2m + 1\) vertices (\(2m\) vertices of degree \(2\) and one vertex of degree \(2m\)) and \(3m\) edges. The vertex set and edge set of \(F_m\) are \(V(F_m)=\{a_i, b_i: 1 \le i \le n\}\cup\{c\},\) \(E(F_m)=\{a_ib_i: 1 \le i \le n\}\cup\{ca_i,cb_i: 1 \le i \le n\},\) respectively. From Theorem 3, we get \(dis(F_m)\ge \lceil \frac{2m+1}{2} \rceil=m+1.\) Let \(\phi\) be the distance irregular vertex labeling. Let \(x,y \in V(F_m)\) be two distinct vertices on different triangle of the friendship graph \(F_m.\) Then there exist two different vertices \(t,s\in V(F_m)\) other than central vertex \(c\) such that \(xt,ys\in E(F_m).\) If \(\phi(x)=\phi(y),\) then \(wt(t)=\phi(c)+\phi(x)=\phi(c)+\phi(y)=wt(s),\) a contradiction. This implies that the labels of all vertices of \(F_m\) graph other than central vertex are distinct. Hence, the lower bound of \(F_m\) is as follows:

To show that \(2m\) is an upper bound for distance irregularity strength of \(F_m,\) we describe a vertex \(2m\)-labeling \(\phi:V(F_m)\to \{1,2,\dots, 2m \}\) for \(m\ge 3\) as follows: \[ \begin{array}{rcll} \phi(c)&=&1,\\ \phi(a_i)& = & 2i, & {\rm for}\ 1 \le i \le m\\ \phi(b_i)& = & 2i-1, & {\rm for}\ 1 \le i \le m \\ \end{array} \] This labeling gives the weight of the vertices as follows: \[ \begin{array}{rcll} wt(c)& = & m(2m+1), & \\ wt(a_i) & = & 2i, & {\rm for}\ 1 \le i \le m \\ wt(b_i) & = & 2i+1, & {\rm for}\ 1 \le i \le m \\ \end{array} \] It is easy to check that the weight of the vertices are distinct. The above constructions show that Combining equation (\ref{eq1}) and equation (\ref{eq2}), we get \begin{equation*} dis(F_m)=2m. \end{equation*} This completes the proof.

The Jahangir graph \(J_{m,n},\) \(m\geq 3,\) \(n\geq 1,\) consists of a cycle \(C_{nm}\) and one additional vertex which is adjacent to \(m\) vertices of \(C_{nm}\) at distance \(n\) to each other on \(C_{nm}.\) The Jahangir graph was introduced by Tomescu in [6]. The Jahangir graph \(J_{m,2}\) is also known as the gear graph, see Ma and Feng [7], and also Gallian [1]. For \(n=1,\) the Jahangir graph is wheel \(W_m.\) It was shown in [4,5] that \(dis(W_m)= \left\lceil \frac{n+1}{2} \right\rceil.\) In the next theorem, we determine the distance irregularity strength of Jahangir graph \(J_{m,n},\) for \(n=2\) and \(m\equiv 0,1\pmod4.\)

Theorem 7. The distance irregularity strength of Jahangir graph \(J_{m,2}\) is \( dis(J_{m,2})=\lceil\frac{2m+1}{3}\rceil,\) for \(m\ge 3\) and \(m\equiv 0,1\pmod4.\)

Proof. The Jahangir graph \(J_{m,2}\) has \(2m + 1\) vertices (\(m\) vertices of degree \(2,\) \(m\) vertices of degree \(3\) and one vertex of degree \(m\)) and \(3m\) edges. The vertex set and edge set of \(J_{m,2}\) are \(V(J_{m,2})=\{u_i, v_i: 1 \le i \le m\}\cup\{c\},\) \(E(J_{m,2})=\{v_iu_i,cv_i: 1 \le i \le m\}\cup\{u_iv_{i+1}: 1 \le i \le m-1\}\cup\{u_mv_1\},\) respectively. From Theorem 3, we get \(dis(J_{m,2})\ge \left\lceil \frac{2m+1}{3} \right\rceil.\) Let \(k=\left\lceil \frac{2m+1}{3} \right\rceil.\) The lower bound of \(J_{m,2}\) is as follows:

To show that \(\left\lceil\frac{2m+1}{3}\right\rceil\) is an upper bound for distance irregularity strength of \(J_{m,2},\) we describe a vertex \(k\)-labeling \(\phi:V(J_{m,2})\to \{1,2,\dots, k \}\) for \(m\ge 3\) as follows:

Case 1: \(m\equiv 1\pmod4\) \[ \begin{array}{rcll} \phi(c)&=&k,\\ \phi(c)&=&k,\\ \phi(v_i)& = & i, & {\rm for}\ 1 \le i \le \left\lfloor\frac{m}{2}\right\rfloor\\ \phi(v_i)& = &\left\lceil\frac{m}{2}\right\rceil-2\left\lfloor\frac{i-\left\lfloor\frac{m}{2}\right\rfloor-1}{2}\right\rfloor, & {\rm for}\ \left\lfloor\frac{m}{2}\right\rfloor+1 \le i \le m \\ \phi(u_i)& = &k-i, & {\rm for}\ 1 \le i \le \left\lfloor\frac{m}{2}\right\rfloor-1\\ \phi(u_i)& = &k-\left\lfloor\frac{m}{2}\right\rfloor+2\left\lfloor\frac{i-\left\lfloor\frac{m}{2}\right\rfloor}{2}\right\rfloor, & {\rm for}\ \left\lfloor\frac{m}{2}\right\rfloor \le i \le m \\ \end{array} \] This labeling gives the weight of the vertices as follows: \[ \begin{array}{rcll} wt(c)& = & \frac{\left\lfloor\frac{m}{2}\right\rfloor(\left\lfloor\frac{m}{2}\right\rfloor+1)}{2}+\sum\limits_{i=\left\lfloor\frac{m}{2}\right\rfloor+1}^m(\left\lceil\frac{m}{2}\right\rceil-2\left\lfloor\frac{i-\left\lfloor\frac{m}{2}\right\rfloor-1}{2}\right\rfloor),\\ wt(u_i) & = & 2i+1, & {\rm for}\ 1 \le i \le \left\lfloor\frac{m}{2}\right\rfloor \\ wt(u_i) & = & 2(m+1-i), & {\rm for}\ \left\lfloor\frac{m}{2}\right\rfloor+1 \le i \le m \\ wt(v_i) & = & 3k+1-2i, & {\rm for}\ 1 \le i \le \left\lfloor\frac{m}{2}\right\rfloor \\ wt(v_i) & = & 3k-2\left\lfloor\frac{m}{2}\right\rfloor+2\left\lfloor\frac{i-\left\lfloor\frac{m}{2}\right\rfloor}{2}\right\rfloor+2\left\lfloor\frac{i-1-\left\lfloor\frac{m}{2}\right\rfloor}{2}\right\rfloor, & {\rm for}\ \left\lfloor\frac{m}{2}\right\rfloor+1 \le i \le m \\ \end{array} \]

Case 2: \(m\equiv 0\pmod4\) \(\phi(c)=k.\) \[ \begin{array}{rcll} \phi(v_i)& = & i, & {\rm for}\ 1 \le i \le \frac{m}{2}+1\\ \phi(v_i)& = &\frac{m}{2}-1-2\left\lfloor\frac{i-(\frac{m}{2}+2)}{2}\right\rfloor, & {\rm for}\ \frac{m}{2}+2 \le i \le m \\ \phi(u_i)& = &k-i, & {\rm for}\ 1 \le i \le \frac{m}{2}\\ \phi(u_i)& = &k-\frac{m}{2}+2+2\left\lfloor\frac{i-(\frac{m}{2}+1)}{2}\right\rfloor, & {\rm for}\ \frac{m}{2}+1 \le i \le m \\ \end{array} \] This labeling gives the weight of the vertices as follows: \[ \begin{array}{rcll} wt(c)& = & \frac{(m+2)(m+4)}{8}+\sum\limits_{i=\left\lfloor\frac{m}{2}\right\rfloor+2}^m(\frac{m}{2}-1-2\left\lfloor\frac{i-(\frac{m}{2}+2)}{2}\right\rfloor), \\ wt(u_i) & = & 2i+1, & {\rm for}\ 1 \le i \le \frac{m}{2} \\ wt(u_i) & = & 2(m+1-i), & {\rm for}\ \frac{m}{2}+1 \le i \le m \\ wt(v_i) & = & 3k+1-2i, & {\rm for}\ 1 \le i \le \frac{m}{2} \\ wt(v_i) & = & 3k-m+2, & {\rm for}\ i=\frac{m}{2}+1 \\ wt(v_i) & = & 3k-m+4+2\left\lfloor\frac{i-1-(\frac{m}{2}+1)}{2}\right\rfloor+2\left\lfloor\frac{i-(\frac{m}{2}+1)}{2}\right\rfloor, & {\rm for}\ \frac{m}{2}+2 \le i \le m \\ \end{array} \] It is easy to check that the weight of the vertices are distinct. The above constructions show that

Combining equation (3) and equation (4), we get \begin{equation*} dis(J_{m,2})=k=\left\lceil\frac{2m+1}{3}\right\rceil. \end{equation*} This completes the proof.

Helm graph \(H_m\) is the graph obtained from a wheel by attaching a pendant edge at each vertex of the \(m\)-cycle. Thus the vertex set of \(H_m\) is \(V(H_m) = \{c, x_i, y_i : 1 \le i \le m\}\) and the edge set of \(H_m\) is \(E(H_m) = \{cx_i, x_ix_{i+1}, x_iy_i : 1 \le i \le m\}\) with indices taken modulo \(m\). In [8,9], Ahmad et. al determined the total vertex irregularity strength of Helm graph and union of isomorphic Helm graph In the next Theorem, we determined the distance irregularity strength of Helm graph \(H_m\), for \(m\ge 3.\)

Theorem 8. For \(m \geq 3,\) the distance irregularity strength of helm graph \(H_m\) is \(dis(H_m) = m.\)

Proof. Recall that the vertex set and edge set of helm \(H_m\) are \begin{eqnarray} \nonumber V(H_m)& = & \{x_i, y_i : 1 \le i \le m\}\cup \{c\} \\ \nonumber E(H_m)& = & \{cx_i, x_ix_{i+1}, x_iy_i : 1 \le i \le m\} \nonumber \end{eqnarray} The helm graph \(H_m\) contains \(m\) vertices of degree 1, \(m\) vertices of degree \(4\) and one vertex of degree \(m.\) As \(m \ge \left\lceil\frac{2m}{4}\right\rceil,\) thus the lower bound of \(H_m\) from Theorem 3 is as follows:

To show that \(dis(H_m)\le m,\) we define a labeling \(\phi:V(H_m)\to \{1,2,\dots, m \}\) for \(m\ge 3\) as follows: \[\phi(c)=m, \;\;\textrm{and}\;\; \phi(x_i)=i, \;\;\textrm{for}\;\; 1 \le i \le m.\] If \(m\) is odd, then \[\phi(y_i)= i, \;\;\textrm{for}\;\; 1 \le i \le m.\] If \(m\) is even, then \[\phi(y_1)=1, \phi(y_i)= m+2-i, \;\;\textrm{for}\;\; 2 \le i \le m.\] This labeling gives the weight of the vertices as follows: \[wt(c) = \frac{m(m+1)}{2}, wt(y_i) = i, {\rm for}\ 1 \le i \le m.\] If \(m\) is odd, then \[wt(x_1) =2m+3,wt(x_m) =3m, \;\;\textrm{and}\;\; wt(x_i) = m+3i, \;\;\textrm{for}\;\; 2 \le i \le m-1.\] If \(m\) is even, then \[wt(x_1) =2m+3, wt(x_m) =2m+2,\;\;\textrm{and}\;\; wt(x_i) = 2m+2+i,\;\;\textrm{for}\;\;2 \le i \le m-1.\] It is easy to check that the weight of the vertices are distinct. The above constructions show that \( dis(H_{m})\le m.\) Combine with equation (5), we get \begin{equation*} dis(H_{m})=m. \end{equation*} This completes the proof.

3. Conclusion and Open Problems

In this paper, the lower bound for the distance irregular labeling for any graphs is improved and determined the exact values of distance irregularity strength of the corona product of cycle \(C_n,\) path \(P_n\) with \(\overline{K_m},\) and propose the following open problems.

Problem 1. Let \(C_n\odot K_m\) be the graph of corona product of cycle \(C_n\) and complete graph \(K_m,\) then find the exact value of the distance irregularity strength of \(C_n\odot K_m,\) for \(n\ge 3, m\ge 2.\)

Problem 2. Let \(P_n\odot K_m\) be the graph of corona product of path \(P_n\) and complete graph \(K_m,\) then find the exact value of the distance irregularity strength of \(P_n\odot K_m,\) for \(n\ge 3, m\ge 2.\)

Also the exact value of distance irregularity strength of the friendship graph \(F_m\), Jahangir graph \(J_{m,2}\) for \(m\equiv 0,1\pmod4,\) is determined and suggest the following open problems.

Problem 3. For \(m\ge 3\) and \(m\equiv 2,3\pmod4,\) find the exact value of distance irregularity strength of Jahangir graph \(J_{m,2}.\)

Problem 4. For \(m, n\ge 3,\) find the exact value of distance irregularity strength of Jahangir graph \(J_{m,n}.\)

Conflicts of Interest:

”The author declares no conflict of interests.”