Distance antimagic labeling of join and corona of two graphs

Peer review under responsibility of Kalasalingam University.

Abstract

Let $G$ be a graph of order $n$. Let $f:V\left(G\right)⟶\{1,2,\dots ,n\}$ be a bijection. The weight $w_f\left(v\right)$ of a vertex $v$ with respect to $f$ is defined by $w_f\left(v\right)={\sum }_{x\in N\left(v\right)}f\left(x\right)$, where $N\left(v\right)$ is the open neighborhood of $v$. The labeling $f$ is said to be distance antimagic if $w_f\left(u\right)\ne w_f\left(v\right)$ for every pair of distinct vertices $u,v$ $\in V\left(G\right)$. If the graph $G$ admits such a labeling, then $G$ is said to be a distance antimagic graph. In this paper we investigate the existence of distance antimagic labelings of $G+H$ and $G\circ H$.

Keywords:

• Distance antimagic labeling
• Arbitrarily distance antimagic labeling
• Distance magic labeling

1 Introduction

By a graph $G=(V,E)$, we mean a finite undirected graph without loops, multiple edges or isolated vertices. For graph theoretic terminology we refer to West [1].

Most of the graph labeling methods trace their origin to the concept of $\beta$-valuation introduced by Rosa [2]. For a general overview of graph labeling we refer to the dynamic survey by Gallian [3].

Let $G$ be a graph of order $n$. Let $f:V\left(G\right)⟶\{1,2,\dots ,n\}$ be a bijection. The weight $w_f\left(v\right)$ of a vertex $v$ is defined by $w_f\left(v\right)={\sum }_{x\in N\left(v\right)}f\left(x\right)$. The labeling $f$ is said to be distance antimagic if $w_f\left(u\right)\ne w_f\left(v\right)$ for every pair of vertices $u,v$ $\in V\left(G\right)$. If the graph $G$ admits such a labeling, then $G$ is said to be a distance antimagic graph. Many classes of graphs are known to be distance antimagic. For details one may refer to Gallian [3] and Kamatchi and Arumugam [4].

Let $G=(V,E)$ be a graph of order $n$. Let $f:V\to \{1,2,\dots ,n\}$ be a bijection. For $v\in V$, the weight of $v$ is defined to be $w_f\left(v\right)={\sum }_{x\in N\left(v\right)}f\left(x\right)$. If $w_f\left(v\right)=k$ (a constant) for every $v\in V$, then $f$ is said to be a distance magic labeling of the graph $G$. A graph which admits a distance magic labeling is called a distance magic graph. The constant $k$ is called the distance magic constant. For more details one may refer to Arumugam et al. [5]

Definition 1.1

Let $G$ and $H$ be two graphs. The corona $G\circ H$ is obtained by taking one copy of $G$ and $\left|V\left(G\right)\right|$ copies of $H$ and joining each vertex of the $i$th copy of $H$ to the $i$th vertex of $G$.

In [4] Kamatchi and Arumugam proved that the graphs $P_n(n\ne 3)$ and $C_n(n\ne 4)$ are distance antimagic. They also proved that for any graph $G$ the corona $H=G\circ K_1$ is a distance antimagic graph. They posed the following problem:

Problem 1.2

If $G$ is a distance antimagic graph, are $G+K_1$ and $G+K_2$ distance antimagic?

In this paper we solve the above problem in the affirmative. We also prove certain sufficient conditions for the existence of distance antimagic labeling for the join and corona of two graphs.

Let $f:V\left(G\right)⟶\{1,2,\dots ,n\}$ be a bijection. Then for any positive integer $k$, we define a bijection $f_k:V\left(G\right)⟶\{k+1,k+2,\dots ,k+n\}$ by $f_k\left(x\right)=f\left(x\right)+k$. It should be noted that if $f$ is a distance antimagic labeling then $f_k$ need not induce distinct vertex weights.

For example, for the path $P_6=(v_1,v_2,v_3,v_4,v_5,v_6)$, the labeling $f:V⟶\{1,2,\dots ,6\}$ defined by $f\left(v_i\right)=i$ is a distance antimagic labeling. However $w_{f_1}\left(v_6\right)=w_{f_1}\left(v_2\right)=6$.

These observations lead to the following concept of arbitrarily distance antimagic labeling, which serves as a nice tool in proving that under certain conditions the join of two graphs is distance antimagic.

Definition 1.3

A graph $G$ of order $n$ is said to be arbitrarily distance antimagic if there exists a bijection $f:V⟶\{1,2,\dots ,n\}$ such that $w_{f_k}\left(u\right)\ne w_{f_k}\left(v\right)$ for any two distinct vertices $u$ and $v$ and for any $k\ge 0$. The labeling $f$ with this property is called an arbitrarily distance antimagic labeling of $G$.

In this paper we use the concept of arbitrarily distance antimagic labeling to prove the existence of distance antimagic labeling of $G+H$ and $G\circ H$ for some graphs $G$ and $H$.

2 Arbitrarily distance antimagic labeling of graphs

In this section, we discuss the existence of arbitrarily distance antimagic labelings of some graphs.

Proposition 2.1

Any $r$-regular distance antimagic graph $G$ is arbitrarily distance antimagic.

Proof

Let $f$ be a distance antimagic labeling of $G$. Since $w_{f_k}\left(u\right)=w_f\left(u\right)+rk$ and $w_f\left(u\right)\ne w_f\left(v\right)$ for any two distinct vertices, it follows that $w_{f_k}\left(u\right)\ne w_{f_k}\left(v\right)$. Hence $f$ is arbitrarily distance antimagic.  □

Proposition 2.2

Let $f$ be a distance antimagic labeling of a graph $G$ of order $n$, such that $deg\left(u\right)<deg\left(v\right)⟹w_f\left(u\right)<w_f\left(v\right)$. Then $f$ is an arbitrarily distance antimagic labeling.

Proof

Let $u$ and $v$ be two distinct vertices. Then $w_f\left(v\right)\ne w_f\left(u\right)$. Also $w_{f_k}\left(u\right)=w_f\left(u\right)+k\left(deg\left(u\right)\right)$. Hence it follows that if $deg\left(u\right)=deg\left(v\right)$ then $w_{f_k}\left(u\right)\ne w_{f_k}\left(v\right)$. Now if $deg\left(u\right)<deg\left(v\right)$ then $w_f\left(u\right)<w_f\left(v\right)$. Hence $w_{f_k}\left(u\right)<w_{f_k}\left(v\right)$. Hence $f$ is an arbitrarily distance antimagic labeling.  □

Theorem 2.3

The path $P_n$ is arbitrarily distance antimagic for every $n\ne 3$.

Proof

Let $P_n=(v_1,v_2,\dots ,v_n)$. We consider two cases:

Case 1 : $n$ is odd.

Define $f\left(v_i\right)=\left\{\begin{array}{cc}n\hfill & \text{if}i=1\hfill \\ n-1\hfill & \text{if}i=n\hfill \\ 1\hfill & \text{if}i=2\hfill \\ 2\hfill & \text{if}i=n-1\hfill \\ (n+1)-i\hfill & \text{if}i=3,4,\dots ,n-2.\hfill \end{array}\right.$Then $w_f\left(v_i\right)=\left\{\begin{array}{cc}1\hfill & \text{if}i=1\hfill \\ 2\hfill & \text{if}i=n\hfill \\ n-2\hfill & \text{if}i=3\hfill \\ n+2\hfill & \text{if}i=n-1\hfill \\ 2n-2\hfill & \text{if}i=2\hfill \\ 2n+2-2i\hfill & \text{if}i=4,5,\dots ,n-2.\hfill \end{array}\right.$

Case 2 : $n$ is even.

Define $f\left(v_i\right)=\left\{\begin{array}{cc}n-(i-1)\hfill & \text{if}i\text{is odd}\hfill \\ i-1\hfill & \text{if}i\text{is even.}\hfill \end{array}\right.$Then $w_f\left(v_i\right)=\left\{\begin{array}{cc}2n+2-2i\hfill & \text{if}i\text{is even}\hfill \\ 2i-2\hfill & \text{if}i\text{is odd},3\le i\le n-1\hfill \\ 1\hfill & \text{if}i=1\text{.}\hfill \end{array}\right.$

In both cases the vertex weights are distinct. Hence $P_n$ is distance antimagic. Further if $u,v\in V\left(P_n\right)$ and $deg\left(u\right)<deg\left(v\right)$, then $w_f\left(u\right)<w_f\left(v\right)$. Hence it follows from Proposition 2.2 that $f$ is an arbitrarily distance antimagic labeling of $P_n.$  □

Theorem 2.4

The cycle $C_n$ is arbitrarily distance antimagic for every $n\ge 3,n\ne 4$.

Proof

Let $C_n=(v_1,v_2,\dots ,v_n,v_1)$. We consider two cases:

Case 1 : $n$ is odd.

Define $f:V\left(C_n\right)⟶\{1,2,\dots ,n\}$ by $f\left(v_i\right)=i$ for $1\le i\le n$. Clearly $f$ is a bijection and $w_f\left(v_i\right)=\left\{\begin{array}{cc}n+2\hfill & \text{if}i=1\hfill \\ 2i\hfill & \text{if}2\le i\le n-1\hfill \\ n\hfill & \text{if}i=n.\hfill \end{array}\right.$

Case 2 : $n$ is even.

Define $f:V\left(C_n\right)⟶\{1,2,\dots ,n\}$ by $f\left(v_i\right)=i$ for $2\le i\le n-1$, $f\left(v_1\right)=n$ and $f\left(v_n\right)=1$. Then $w_f\left(v_i\right)=\left\{\begin{array}{cc}3\hfill & \text{if}i=1\hfill \\ n+3\hfill & \text{if}i=2\hfill \\ 2i\hfill & \text{if}3\le i\le n-2\hfill \\ n-1\hfill & \text{if}i=n-1\hfill \\ 2n-1\hfill & \text{if}i=n.\hfill \end{array}\right.$In both the cases the vertex weights are distinct and hence $C_n$ is distance antimagic. Now since $C_n$ is regular it follows from Proposition 2.1 that the labeling $f$ is an arbitrarily distance antimagic labeling.  □

Handa et al. [6] have also proved the following theorem.

Theorem 2.5

For $r\ge 2$ and $n\ne 3$, the graph $r{P}_n$ admits an arbitrarily distance antimagic labeling with the highest induced vertex weight equal to $2rn-1$.

3 Distance antimagic labeling of join of two graphs

In this section we shall use the concept of arbitrarily distance antimagic labeling to prove that join of some classes of graphs is distance antimagic.

Theorem 3.1

Let $G_1$ and $G_2$ be two graphs of order $n_1$ and $n_2$ with arbitrarily distance antimagic labelings $f_1$ and $f_2$ respectively and let $n_1\le n_2$. Let $x\in V\left(G_1\right)$ be the vertex with lowest weight under $f_1$ and $y\in V\left(G_2\right)$ be the vertex with highest weight under $f_2$. If (1) $w_{f_1}\left(x\right)+\sum _{i=1}^{n_2}(n_1+i)>w_{f_2}\left(y\right)+\Delta \left(G_2\right)n_1+\sum _{i=1}^{n_1}i$(1) then $G_1+G_2$ is distance antimagic.

Proof

We define $f:V\left(G_1\right)\cup V\left(G_2\right)⟶\{1,2,\dots ,n_1+n_2\}$ by $f\left(v\right)=\left\{\begin{array}{cc}{f}_1\left(v\right)\hfill & ifv\in V\left(G_1\right)\hfill \\ f_2\left(v\right)+n_1\hfill & ifv\in V\left(G_2\right).\hfill \end{array}\right.$

Clearly $f$ is a bijection. Since $f_1$ and $f_2$ are arbitrarily distance antimagic labeling, if $u,v\in V\left(G_1\right)$ or $u,v\in V\left(G_2\right)$, then $w_f\left(u\right)\ne w_f\left(v\right)$. Now the lowest weight in $G_1$ under $f$ is $w_{f_1}\left(x\right)+{\sum }_{i=1}^{n_2}(n_1+i)$ and the highest weight in $G_2$ under $f$ is less than or equal to $w_{f_2}\left(y\right)+\Delta \left(G_2\right)n_1+{\sum }_{i=1}^{n_1}i$. Hence by hypothesis the lowest weight in $G_1$ is greater than the highest weight in $G_2$ and hence it follows that $w_f\left(u\right)\ne w_f\left(v\right)$ if $u\in V\left(G_1\right)$ and $u\in V\left(G_2\right)$. Thus $f$ is a distance antimagic labeling of $G_1+G_2$.  □

Remark 3.2

Since $n_1\le n_2$, inequality (1(1) $w_{f_1}\left(x\right)+\sum _{i=1}^{n_2}(n_1+i)>w_{f_2}\left(y\right)+\Delta \left(G_2\right)n_1+\sum _{i=1}^{n_1}i$(1) ) implies the inequality (2) $w_{f_1}\left(x\right)+n_1{n}_2>w_{f_2}\left(y\right)+n_1\Delta \left(G_2\right).$(2)

Further inequality (2(2) $w_{f_1}\left(x\right)+n_1{n}_2>w_{f_2}\left(y\right)+n_1\Delta \left(G_2\right).$(2) ) implies inequality (1(1) $w_{f_1}\left(x\right)+\sum _{i=1}^{n_2}(n_1+i)>w_{f_2}\left(y\right)+\Delta \left(G_2\right)n_1+\sum _{i=1}^{n_1}i$(1) ).

Theorem 3.3

Let $G_1$ and $G_2$ be graphs of order at least $4$ which are arbitrarily distance antimagic and let $\Delta \left(G_1\right),\Delta \left(G_2\right)\le 2$. Then $G_1+G_2$ is distance antimagic.

Proof

Let $\left|V\left(G_1\right)\right|=n_1$, $\left|V\left(G_2\right)\right|=n_2$ and $n_1\le n_2$. Let $f_1$ and $f_2$ be arbitrarily distance antimagic labelings of $G_1$ and $G_2$ respectively. Now the highest vertex label in $G_2$ under $f_2$ is at most $2n_2-1$ and the lowest vertex label in $G_1$ under $f_1$ is at least $1$. Hence inequality (2(2) $w_{f_1}\left(x\right)+n_1{n}_2>w_{f_2}\left(y\right)+n_1\Delta \left(G_2\right).$(2) ) reduces to $1+n_1{n}_2>2n_2-1+2n_1$. This inequality can be rewritten as $\frac{1}{2}>\frac{1}{n_1}+\frac{1}{n_2}-\frac{1}{n_1{n}_2}$ which is obviously true since $n_1,n_2\ge 4$. Hence the result follows from Theorem 3.1.  □

Corollary 3.4

For $n,m\ge 4$ the graph $P_n+P_m$ is distance antimagic.

Proof

Follows from Theorems 3.3 and 2.3.  □

Corollary 3.5

For $n,m\ge 5$, the graph $C_n+C_m$ is distance antimagic.

Proof

Follows from Theorems 2.4 and 3.3.  □

Theorem 3.6

Let $G$ be a distance antimagic graph of order $n\ge 3$ with distance antimagic labeling $f$ such that the highest weight under $f$ is less than or equal to $\frac{n(n+1)}{2}-3$. Then $G+K_3$ is distance antimagic.

Proof

Since $K_3$ is arbitrarily distance antimagic, by Theorem 3.1, it is enough to prove that inequality (1(1) $w_{f_1}\left(x\right)+\sum _{i=1}^{n_2}(n_1+i)>w_{f_2}\left(y\right)+\Delta \left(G_2\right)n_1+\sum _{i=1}^{n_1}i$(1) ) holds. Since $G$ is distance antimagic and $\left|V\left(G\right)\right|\ge 3$, the highest vertex weight in $G$ is less than $\frac{n(n+1)}{2}-3$ and the lowest vertex weight in $C_3$ is at least 3, inequality (1(1) $w_{f_1}\left(x\right)+\sum _{i=1}^{n_2}(n_1+i)>w_{f_2}\left(y\right)+\Delta \left(G_2\right)n_1+\sum _{i=1}^{n_1}i$(1) ) holds.  □

Remark 3.7

By using the same proof technique of Theorem 3.6 it can be easily proved that if $G$ is a distance magic graph of order $n$ with labeling $f$ such that the highest vertex weight under $f$ is less than or equal to $\frac{n(n+1)}{2}-3$, then $G+K_1$ and $G+K_2$ are distance antimagic. Hence from Theorem 2.3 and Theorem 2.4 we have the following corollary.

Corollary 3.8

Let $W_n=C_{n-1}+K_1$ be the wheel on $n$ vertices. The graph $P_n+P_2$ where $n\ne 3$, $C_n+P_2$, where $n\ne 4$ and $W_m+W_n$, where $n,m\ne 4$ are distance antimagic.

4 Corona of graphs

In this section we investigate the existence of distance antimagic labeling for corona of two graphs.

Theorem 4.1

Let $G_1$ and $G_2$ be two graphs of order $n_1$ and $n_2$ respectively. If there exist vertices $u_i,u_j$ in $G_2$ such that $N\left(u_i\right)=N\left(u_j\right)$ then the graph $G_1\circ G_2$ is not distance antimagic.

Proof

Let $V\left(G_1\right)=\{v_1,v_2,\dots ,v_{n_1}\}$ and $V\left(G_2\right)=\{u_1,u_2,\dots ,u_{n_2}\}$. Let $H_1,H_2,\dots ,H_{n_1}$ be $n_1$ copies of $G_2$ such that $v_i$ is adjacent to each vertex of $H_i$ for $1\le i\le n_1$. Let $u_{ik}$ and $u_{jk}$ be the vertices in $H_k$ corresponding to the vertices $u_i$ and $u_j$ respectively. Then the vertices $u_{ik}$ and $u_{jk}$ have the same neighborhood in $G_1\circ G_2$. Hence $G_1\circ G_2$ is not distance antimagic.  □

Theorem 4.2

Suppose $G_1$ is a distance magic graph of order $n_1$ with magic constant $k$. Let $G_2$ be a $r$-regular graph of order $n_2$ with an arbitrarily distance antimagic labeling $f$. Let $K$ be the maximum weight of a vertex in $G_2$ under $f$. Suppose (3) $k+\frac{n_2}{2}(n_2+2n_1+1)>n_{1}r\left(1+\frac{(n_1-1)n_2}{n_1}\right)+(K+n_1).$(3) Then $G_1\circ G_2$ is distance antimagic.

Proof

Let $V\left(G_1\right)=\{v_1,v_2,\dots ,v_{n_1}\}$ and $V\left(G_2\right)=\{u_1,u_2,\dots ,u_{n_2}\}$. Let $H_1,H_2,\dots ,H_{n_1}$ be $n_1$ copies of $G_2$ such that $v_i$ is adjacent to each vertex of $H_i$ for $1\le i\le n_1$. Let $V\left(H_i\right)=\{u_1^i,u_2^i,\dots ,u_{n_2}^i\}.$ Let $g:V\left(G_1\right)\to \{1,2,\dots ,n_1\}$ be a distance magic labeling of $G_1$. Now define a bijection $h:V(G\circ G_2)\to \{1,2,\dots ,n_1+n_1{n}_2\}$ as follows:

$h\left(v_i\right)=g\left(v_i\right)\mathrm{if}1\le i\le n_1\mathrm{and}$$h\left(u_j^i\right)=f\left(u_j\right)+n_1+n_2(g\left(v_i\right)-1),\mathrm{if}1\le i\le n_1,1\le j\le n_2.$

Then $w_h\left(v_i\right)=k+n_2^2\left(\frac{n_1}{n_2}+(g\left(v_i\right)-1)+\frac{n_2+1}{2n_2}\right),\mathrm{if}1\le i\le n_2$and $w_h\left(u_j^i\right)=w_f\left(u_j\right)+r[n_1+(g\left(v_i\right)-1)n_2]+g\left(v_i\right)\mathrm{if}1\le i\le n_1,1\le j\le n_2.$

Since $f$ is arbitrarily distance antimagic it follows that for $1\le i\le n_1$ and $1\le j_1,j_2\le n_2$, $w_h\left(u_{j_1}^i\right)\ne w_h\left(u_{j_2}^i\right)$. Furthermore for $i_1\ne i_2$, $w_h\left(v_{i_1}\right)\ne w_h\left(v_{i_2}\right)$.

It remains to show that $w_h\left(v_i\right)\ne w_h\left(u_j^q\right)$ for $1\le i,q\le n_1,1\le j\le n_2$.

$\underset{1\le i\le n_1}{\min }{w}_h\left(v_i\right)=\underset{1\le i\le n_1}{\min }\left(k+n_2^2\left(\frac{n_1}{n_2}+(g\left(v_i\right)-1)+\frac{n_2+1}{2n_2}\right)\right)=k+n_2^2\left(\frac{n_1}{n_2}+\frac{n_2+1}{2n_2}\right).$

Furthermore

$\underset{\genfrac{}{}{0ex}{}{1\le i\le n_1}{1\le j\le n_2}}{max}{w}_h\left(u_j^i\right)=\underset{\genfrac{}{}{0ex}{}{1\le i\le n_1}{1\le j\le n_2}}{max}\{w_f\left(u_j\right)+r[n_1+(g\left(v_i\right)-1)n_2]+g\left(v_i\right)\}\le K+r[n_1+(n_1-1)n_2]+n_1=n_{1}r\left(1+\frac{(n_1-1)n_2}{n_1}\right)+(K+n_1).$

Since $k+\frac{n_2}{2}(n_2+2n_1+1)>n_{1}r\left(1+\frac{(n_1-1)n_2}{n_1}\right)+(K+n_1)$, it follows that $\underset{1\le i\le n_1}{\min }{w}_h\left(v_i\right)>\underset{\genfrac{}{}{0ex}{}{1\le i\le n_1}{1\le j\le n_2}}{max}{w}_h\left(u_j^i\right).$

Hence $w_h\left(v_i\right)\ne w_h\left(u_j^q\right)1\le i,q\le n_1,1\le j\le n_2.\square$

Theorem 4.3

The graph $C_4\circ C_n$ is distance antimagic for $n\ge 9$.

Proof

It follows from Theorem 2.4 that $C_n,n\ne 4$ admits a distance antimagic labeling and the highest weight induced by this labeling is $2n-1$. Since $C_4$ is distance magic with magic constant $5$, the result follows from Theorem 4.2.  □

5 Conclusion

In this paper the concept of arbitrarily distance antimagic labeling has been used as a tool for proving the existence of distance antimagic labelings for join and corona of two graphs. This tool can be efficiently used for proving that several classes of graphs admit distance antimagic labelings.

Notes

Peer review under responsibility of Kalasalingam University.