Another Antimagic Conjecture

Abstract

An antimagic labeling of a graph G is a bijection $f:E(G)\to \{1,\dots ,|E(G)\left|\right\}$ such that the weights $w(x)={\sum }_{y\sim x}f(y)$ distinguish all vertices. A well-known conjecture of Hartsfield and Ringel (1990) is that every connected graph other than $K_2$ admits an antimagic labeling. For a set of distances D, a D-antimagic labeling of a graph G is a bijection $f:V(G)\to \{1,\dots ,|V(G)\left|\right\}$ such that the weight$\omega (x)={\sum }_{y\in N_D(x)}f(y)$ is distinct for each vertex x, where $N_D(x)=\{y\in V(G)|d(x,y)\in D\}$ is the D-neigbourhood set of a vertex x. If $N_D(x)=r$, for every vertex x in G, a graph G is said to be $(D,r)$-regular. In this paper, we conjecture that a graph admits a D-antimagic labeling if and only if it does not contain two vertices having the same D-neighborhood set. We also provide evidence that the conjecture is true. We present computational results that, for $D=\left\{1\right\}$, all graphs of order up to 8 concur with the conjecture. We prove that the set of $(D,r)$-regular D-antimagic graphs is closed under union. We provide examples of disjoint union of symmetric $(D,r)$-regular that are D-antimagic and examples of disjoint union of non-symmetric non-$(D,r)$-regular graphs that are D-antimagic. Furthermore, lastly, we show that it is possible to obtain a D-antimagic graph from a previously known distance antimagic graph.

1. Introduction

Let $G=G(V,E)$ be a finite, simple, and undirected graph with v vertices and e edges. The notion of antimagic labeling of a graph G was introduced in Hartsfield and Ringel’s book Pearls in Graph Theory [1] as a bijection f:$E(G)\to \{1,\dots ,e\}$ such that the weights ($w(x)={\sum }_{xy\in E(G)}f(xy)$) distinguish all vertices. Hartsfield and Ringel [1] also conjectured that every connected graph other than $K_2$ admits antimagic labeling in this seminal work.

As of today, the antimagic conjecture is still open; however, much evidence has been presented by many authors. By using a probabilistic method, Alon et al. [2] proved the conjecture for graphs with minimum degree at least $Clog\left|V\right|$, for some constant C. Eccles [3] improved this result, by proving the conjecture for graphs with average degree at least some constant $d_0$. Hefetz, Saluz, and Tran [4] utilized Combinatorial Nullstellensatz to prove that if a graph on $p^k$ vertices, where p is an odd prime and k is a positive integer, admits a $C_p$-factor, then it is antimagic. A series of articles by Cranston, Liang, and Zhu [5], Bérczi, Bernáth, and Vizer [6], and Chang et al. [7] showed that for $k\ge 2$, every k-regular graph is antimagic. For trees, Kaplan, Lev, and Roddity [8] proved that a tree with at most one vertex of degree 2 is antimagic. On the other hand, Liang, Wong, and Zhu [9] proved that a tree with many vertices of degree 2 is antimagic. The latest result on antimagic trees is by Lozano, Mora, Seara, and Tey [10] who proved that caterpillars are antimagic.

In 2017, Arumugam et al. [11] and Bensmail et al. [12] independently introduced a weaker notion of antimagic labeling, called the local antimagic labeling, where only adjacent vertices must be distinguished. Both sets of authors conjectured that any connected graph other than $K_2$ admits a local antimagic labeling. This conjecture has been completely settled by Haslegrave [13] using probabilistic method.

Another type of antimagic labeling was introduced by Kamatchi and Arumugam in 2013 [14]. A bijection $f:V(G)\to \{1,2,...,v\}$ is called a distance antimagic labeling of graph G if for two distinct vertices x and y, $w(x)\ne \omega (y)$, where ${\omega }_f(x)={\sum }_{y\in N(x)}f(y)$, for $N(x)$ the open neighborhood of x, i.e., the set of all vertices adjacent to x. A graph admitting a distance antimagic labeling is called a distance antimagic graph. In the same paper, Kamatchi and Arumugam conjectured that a graph G is distance antimagic if and only if G does not have two vertices with the same open neighbourhood.

Some families of graphs have been shown to be distance antimagic, among others, the path $P_n$, the cycle $C_n$ ($n\ne 4$), the wheel $W_n$ ($n\ne 4$) [14], and the hypercube $Q_n$ ($n\ge 3$) [15]. In 2016, Llado and Miller [16] utilized Combinatorial Nullstellensatz to prove that a tree with l leaves and $2l$ vertices is distance antimagic.

In 2011, O’Neal and Slater [17] introduced the D-magic labeling as follows. Let $D\subseteq \{0,1,\dots ,diam(G)\}$ be a set of distances in G. The graph G is said to be D-magic if there exists a bijection $f:V\to \{1,2,\dots ,v\}$ and a magic constantk such that for any vertex x, ${\omega }_f(x)={\sum }_{y\in N_D(x)}f(y)=k$, where $N_D(x)=\left\{y\right|d(x,y)=d,d\in D\}$ is the D-neighborhood set of x.

When we consider the D-neighborhood set of a vertex, the regularity of a graph is defined as follows. A graph G is said to be $(D,r)$-regular if $|N_D(x)|=r$ for every vertex $x\in G$. Clearly, an regular graph is $(\{1\},r)$-regular.

Inspired by the notion of D-magic labeling, the idea of distance antimagic labeling was generalized by considering a set of distances $D\subseteq \{0,1,\dots ,diam(G)\}$ and the D-neighborhood set of a vertex.

Definition 1.

A D-antimagic labeling of a graph G is a bijection $f:V(G)\to \{1,\dots ,v\}$ such that the weight ${\omega }_f(x)={\sum }_{y\in N_D(x)}f(y)$ is distinct for each vertex x.

It is clear that if a graph contains two vertices having the same D-neighborhood set, then the graph does not admit a D-antimagic labeling. Here we boldly conjecture that the converse of the previous statement is also true, and thus we propose the following.

Conjecture 1.

A graph admits a D-antimagic labeling if and only if it does not contain two vertices having the same D-neighborhood set.

If x and y are two distinct vertices with the same D-neighborhood set, the two vertices are called D-twins of each other, denoted by $x{\sim }_{D}y$. It is clear that ${\sim }_D$ is an equivalence relation, and thus Conjecture 1 can be rewritten as: “A graph admits a D-antimagic labeling if and only if its vertex set partition defined by ${\sim }_D$ contains only singletons”.

An automorphism of a graph G is a permutation of $V(G)$ preserving adjacency. A graph G is said to be vertex-transitive if, for any two vertices x and y, there exists an automorphism of G that maps x to y and it is said to be edge-transitive if, for any two edges $xy$ and $uv$, there is an automorphism of G that maps $xy$ to $uv$. If G is both vertex-transitive and edge-transitive, G is symmetric. Recall that a cycle, a complete graph, and a hypercube are symmetric. A path on at least four vertices and a wheel on at least five vertices are neither vertex-transitive nor edge-transitive.

In the rest of the paper, we shall provide several pieces of evidence that Conjecture 1 is true. First, in Section 2, we provide computational results where all graphs of order up to 8 concur with Conjecture 1, for the case of $D=\left\{1\right\}$. Second, in Section 3, we show that the set of $(D,r)$-regular D-antimagic graphs is closed under union. For particular D, we provide examples of symmetric $(D,r)$-regular graphs that are D-antimagic, so the disjoint union of those graphs is also D-antimagic. Examples of disjoint union of non-$(D,r)$-regular graphs that are neither vertex-transitive nor edge-transitive but admit D-antimagic labelings are also presented in this section. Lastly, in Section 4, we show that it is possible to obtain a D-antimagic graph from a previously known distance antimagic graph. We realize that Conjecture 1, if true, will be laborious to prove, and thus in the following sections, we propose several open problems that hopefully are more feasible to solve.

2. Computational Result

We build an exhaustive algorithm to search for all distance antimagic graphs of order v. We split the algorithm into three functions: Algorithm 1 checks whether an input graph G contains $\left\{1\right\}$-twins by seeking two identical rows in the adjacency matrix of G. Algorithm 2 decides whether labeling is distance antimagic, and Algorithm 3 searches for distance antimagic graphs. We implemented this algorithm in C++, and the source code can be found in [18].

Let $V(G)=\{x_1,x_2,\dots ,x_v\}$, A be the adjacency matrix of G, and the labeling matrix $L(G)$ be a $v\times v$ matrix whose $(i,i)$ entry is $\lambda (x_i)$, the label of vertex $x_i$.

Algorithm 1. Check If G Contains $\left\{1\right\}$-Twins

1: functionISTWINS(G) 2:     for $i\leftarrow 1\mathbf{to}v$ do 3:         for $j\leftarrow 1\mathbf{to}v$ do 4:            $v_i=A_{i,1\cdots v}$                                                                                  ▹$v_i$ is the ith row vector of A 5:            if $i\ne j\mathbf{and}{v}_i\ne v_j$ then 6:                return false                                         ▹ return false if two identical row vectors are found 7:            end if 8:         end for 9:      end for 10:     return true 11: end function

Algorithm 2. Evaluate Distance Anti Magic

1: functionEVALDISTANCEANTIMAGIC($L(G)$) 2:     for $i\leftarrow 1\mathbf{to}v$ do 3:         $w_i=0$                                                                                                      ▹ initialize weight $w_i$ 4:         for $j\leftarrow 1\mathbf{to}v$ do                                                                                   ▹ calculate weight $w_i$ 5:            $w_i\leftarrow w_i+\lambda (x_j)(A_{i,j})$ 6:         end for 7:     end for 8:     if ISUNIQUE(w) then                                                                  ▹ check if $w_i\ne w_j$ for all $i,j$ 9:         return 0 10:     else 11:        return 1 12:     end if 13: end function

Algorithm 3. Search Distance Anti Magic

1: functionSEARCHDISTANCEANTIMAGIC($G,P$) ▹P is the set of permutation on v elements 2:     $c\leftarrow 1$ 3:     $i\leftarrow 1$ 4:     if ISTWINS(G) then 5:         while $c\ne 0$ or $\lambda$ and $i\le \left|P\right|$ do 6:            $\lambda =P_i$ 7:            $L(\beta )=L(G,\lambda )$ 8:            $c\leftarrow$ EVALDISTANCEANTIMAGIC($L(\beta )$) 9:            $i\leftarrow i+1$ 10:         end while 11:     end if 12: end function

We run the algorithm to search for all distance antimagic (non-isomorphic) graphs of order up to 8 generated by nauty [19], with results as depicted in

Table 1. Distance antimagic graphs of order $v,1\le v\le 8$.

v	# Non-Isomorphic	# Graphs Not Containing	#$\left\{1\right\}$-Antimagic
	Graphs	$\left\{1\right\}$-Twins	Graphs
1	1	1	1
2	2	1	1
3	4	2	2
4	11	5	5
5	34	16	16
6	156	78	78
7	1044	588	588
8	12346	8047	8047

.

Thus, we obtain the following result, which supports Conjecture 1.

Theorem 1.

A graph of order $v,1\le vs.\le 8,$ admits a $\left\{1\right\}$-antimagic labeling if and only if it does not contain two vertices having the same $\left\{1\right\}$-neighborhood set.

3. Closedness of Union of D-Antimagic Graphs

Theorem 2.

Let D be an arbitrary set of distances and $G,H$ be two D-antimagic graphs. If H is $(D,r)$-regular and $|N_D(x)|\le r$, for every $x\in V(G)$, then $G\bigcup H$ is also D-antimagic.

Proof. 

Let g and h be D-antimagic labelings of G and H. Define a new labeling l for $G\bigcup H$ as $l(x)=h(x)+v$, when $x\in H$, and $l(x)=g(x)$, when $x\in G$.

We shall show that l is D-antimagic. Let x and y be two distinct vertices in $G\bigcup H$. If both $x,y\in V(G)$, then $w_l(x)=w_g(x)\ne w_g(y)=w_l(y)$. If both $x,y\in V(H)$, then

$$\begin{array}{ccc}{w}_l(x)& =& \sum _{u\in N_D(x)}(h(u)+v)\hfill \\ & =& \sum _{u\in N_D(x)}h(u)+\left|N_D(x)\right|v\hfill \\ & =& w_h(x)+rv\hfill \\ & \ne & w_h(y)+rv\hfill \\ & =& w_l(y)\hfill \end{array}$$

The last case is if, without loss of generality, $x\in V(G)$ and $y\in V(H)$. Since $w_l(x)=w_g(x)\le vs.{max}_{x\in V(G)}|N_D(x)|$ and $w_l(y)\ge (v+1)+(v+2)+\dots +(v+r)>vr$, then $w_l(x)\le vs.{max}_{x\in V(G)}|N_D(x)|\le vr<w_l(y)$. □

Let ${\mathcal{G}}_{\mathcal{A}}(D)$ be the set of all D- antimagic graphs and $\mathcal{G}(D,r)$ be the set of all $(D,r)$-regular graphs. A direct consequence of Theorem 2 is

Corollary 1.

${\mathcal{G}}_{\mathcal{A}}(D)\bigcap \mathcal{G}(D,r)$ is closed under union.

Corollary 1 is a generalization of a result in [15], where it was proved that if G is a regular distance antimagic graph, then $2G$ is also distance antimagic.

Direct application of Corollary 1 to known graphs in ${\mathcal{G}}_{\mathcal{A}}(D)\bigcap \mathcal{G}(D,r)$ results in the following.

Corollary 2.

1.

For $n_i\ne 4,i=1,\dots ,k$, the disjoint union of cycles ${\bigcup }_{i=1}^k{C}_{n_i}$ is $\left\{1\right\}$-antimagic.

2.

For $n_i\ge 3,i=1,\dots ,k$, the disjoint union of cycles ${\bigcup }_{i=1}^k{C}_{n_i}$ is $\{0,1\}$-antimagic.

3.

For $n_i\ge 1,i=1,\dots ,k$, the disjoint union of complete graphs ${\bigcup }_{i=1}^k{K}_{n_i}$ is $\left\{1\right\}$-antimagic.

4.

For $n_i\ge 3,i=1,\dots ,k$, the disjoint union of hypercubes ${\bigcup }_{i=1}^k{Q}_{n_i}$ is $\left\{1\right\}$-antimagic.

5.

For $n_i\equiv 0mod4, i=1,\dots ,k$, the disjoint union of hypercubes ${\bigcup }_{i=1}^{k}2Q_{n_i}$ is $\{0,1\}$-antimagic.

Proof. 

Due to facts that:

1.

For $n\ne 4$, the cycle $C_n$ is $\left\{1\right\}$-antimagic [14].

2.

For $n\ge 3$, the cycle $C_n$ is $\{0,1\}$-antimagic [20].

3.

For $n\ge 1$, the complete graph $K_n$ is trivially $\left\{1\right\}$-antimagic.

4.

For $n\ge 3$, the hypercube $Q_n$ is $\left\{1\right\}$-antimagic [15].

5.

For $n\equiv 0\mathrm{mod}4$, the disjoint union of two hypercubes $2Q_n$ is $\{0,1\}$-antimagic [21].

 □

Although closedness under union is still unknown for the set of non-regular graphs, in the following theorems, we shall provide some families of disjoint union of non-regular graphs admitting D-antimagic labelings for $D=\left\{1\right\}$. We start by showing that particular cases of disjoint union of paths are distance antimagic.

Theorem 3.

For any positive integers $m,n>3$, the disjoint union of two paths $P_m\cup P_n$ is distance antimagic.

Proof. 

Let $V(P_m)=\{v_i^{(1)}:1\le i\le m\}$ and $V(P_n)=\{v_j^{(2)}:1\le j\le n\}$. We shall consider three cases which depend on the parity of m and n.

Case 1. Without loss of generality, when m odd and n even. Define a labeling $g:V(P_m\cup P_n)\to \{1,2,\dots ,m+n\}$, where $g(v_i^{(1)})=m+n$, for $i=1$, $g(v_i^{(1)})=n+i-1$, for $2\le i\le m$, and $g(v_j^{(2)})=j$, for $1\le j\le n$.

Under this labeling, the weights are:

$${\omega }_g(v_i^{(1)})=\left\{\begin{array}{cc}n+1,\hfill & \mathrm{if}i=1,\hfill \\ m+2n+2,\hfill & \mathrm{if}i=2,\hfill \\ 2n+2i-2,\hfill & \mathrm{if}3\le i\le m-1,\hfill \\ n+m-2,\hfill & \mathrm{if}i=m,\hfill \end{array}\right.$$

and

$${\omega }_g(v_j^{(2)})=\left\{\begin{array}{cc}2j,\hfill & \mathrm{if}1\le j\le n-1,\hfill \\ n-1,\hfill & \mathrm{if}j=n,\hfill \end{array}\right.$$

It is clear that every vertex in $P_n$ has a distinct weight less than any weight in $P_m$. On the other hand, in $P_m$, the only even weights are $2n+2i-2,3\le i\le m-1$, all of which are different. To conclude, for the odd weights in $P_m$, the following inequalities hold

$$n-1<n+1<n+m-2<m+2n+2.$$

Case 2. When both m and n are even. Since the case when $m=n$ is considered in Theorem 4, we may assume $m<n$. Define a labeling $g_1:V(P_m)\to \{1,2,\dots ,m\}$, where $g_1(v_i^{(1)})=i$. Under this labeling, ${\omega }_{g_1}(v_i^{(1)})<2m-1$, for $1\le i\le m$.

We then define three different labelings for $P_n$, depending on the value of n.

Sub Case 2.1. When $m=4$ and $n=6$, define a labeling $g_2:V(P_n)\to \{5,\dots ,10\}$, where

$$g_2(v_1^{(2)})=5,g_2(v_2^{(2)})=7,g_2(v_3^{(2)})=6,g_2(v_4^{(2)})=9,g_2(v_5^{(2)})=8,g_2(v_6^{(2)})=10.$$

Here the weights are:

$${\omega }_{g_2}(v_1^{(2)})=7,{\omega }_{g_2}(v_2^{(2)})=11,{\omega }_{g_2}(v_3^{(2)})=16,{\omega }_{g_2}(v_4^{(2)})=14,{\omega }_{g_2}(v_5^{(2)})=19,{\omega }_{g_2}(v_6^{(2)})=8,$$

all of which are larger the the weights of all vertices in $P_m$.

Sub Case 2.2. For $n=m+2,m\ge 6$, define a labeling $g_2:V(P_n)\to \{1,\dots ,n\}$, where

$$g_2(v_j^{(2)})=\left\{\begin{array}{cc}m+j,\hfill & \mathrm{if}j=1,m+1,m+2,\hfill \\ 2m,\hfill & \mathrm{if}j=2,\hfill \\ m+j-1,\hfill & \mathrm{if}3\le j\le m.\hfill \end{array}\right.$$

This labeling results to the following weights of vertices in $P_n$.

$${\omega }_{g_2}(v_j^{(2)})=\left\{\begin{array}{cc}2m+3j-3,\hfill & \mathrm{if}j=1,2,\hfill \\ 3m+3,\hfill & \mathrm{if}j=3,\hfill \\ 2m+2j-2,\hfill & \mathrm{if}4\le j\le m-1,\hfill \\ 2m+2j-1,\hfill & \mathrm{if}j=m,m+1,\hfill \\ 2m+1,\hfill & \mathrm{if}j=m+2.\hfill \end{array}\right.$$

The even weights are $2m<2m+6<2m+8<...<4m-4$ and the odd weights $2m+1<2m+3<3m+3<4m-1<4m+1$, all of which are larger than the weights of vertices in $P_m$.

Sub Case 2.3. When $n>m+2,$$m\ge 4,$ define a labeling $g_2:V(P_n)\to \{1,\dots ,n\}$, where

$$g_2(v_j^{(2)})=\left\{\begin{array}{cc}m+j,\hfill & \mathrm{if}j=1\mathrm{and}n,\hfill \\ 2m,\hfill & \mathrm{if}j=2,\hfill \\ m+j-1,\hfill & \mathrm{if}3\le j\le m,\hfill \\ m+j+1,\hfill & \mathrm{if}m+1\le j\le n-2,\hfill \\ 2m+1,\hfill & \mathrm{if}j=n-1.\hfill \end{array}\right.$$

Thus, we obtain the following weights for vertices in $P_n$.

$${\omega }_{g_2}(v_j^{(2)})=\left\{\begin{array}{cc}2m+3(j-1),\hfill & \mathrm{if}j=1\mathrm{and}2,\hfill \\ 3m+3,\hfill & \mathrm{if}j=3,\hfill \\ 2m+2j-2,\hfill & \mathrm{if}4\le j\le m-1,\hfill \\ 2m+2j,\hfill & \mathrm{if}j=m\mathrm{and}m+1,\hfill \\ 2m+2j+2,\hfill & \mathrm{if}m+2\le j\le n-3,\hfill \\ 3m+n-1,\hfill & \mathrm{if}j=n-2,\hfill \\ 2m+2n-1,\hfill & \mathrm{if}j=n-1,\hfill \\ 2m+1,\hfill & \mathrm{if}j=n.\hfill \end{array}\right.$$

Here the odd weights are $2m+1<2m+3<3m+3<3m+n-1<2m+2n-1$ and the even weights are $2m,2m+6,2m+8,\dots ,4m-4,4m,4m+2,4m+6,4m+8,\dots ,$$2m+2n-4$.

Case 3. When both m and n are odd, define a labeling $g:V(P_m\cup P_n)\to \{1,\dots ,m+n\}$, where $g(v_i^{(1)})=i+1$, for $1\le i\le m$, and

$$g(v_j^{(2)})=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}j=1,\hfill \\ m+j,\hfill & \mathrm{if}2\le j\le n.\hfill \end{array}\right.$$

Under the labeling g, we obtain the following weights of vertices.

$${\omega }_g(v_i^{(1)})=\left\{\begin{array}{cc}3,\hfill & \mathrm{if}i=1,\hfill \\ 2i+2,\hfill & \mathrm{if}2\le i\le m-1,\hfill \\ m,\hfill & \mathrm{if}i=m,\hfill \end{array}\right.$$

and

$${\omega }_g(v_j^{(2)})=\left\{\begin{array}{cc}m+2j,\hfill & \mathrm{if}j=1\mathrm{and}2,\hfill \\ 2m+2j,\hfill & \mathrm{if}3\le j\le n-1,\hfill \\ m+n-1\hfill & \mathrm{if}j=n.\hfill \end{array}\right.$$

The odd weights are $3<m<m+2<m+4<m+n-1$ and the even weights are $2i+2$, for $2\le i\le n$, and $2m+2j$, for $3\le j\le n-1$. This concludes our proof.

An example of a distance magic labeling for $P_9\cup P_{12}$ can be viewed in Figure 1. □

Theorem 4.

For $n\ne 3$, $m{P}_n$ is distance antimagic.

Proof. 

Let $V(m{P}_n)=\{v_i^j:1\le i\le n,1\le j\le m\},$ and $E(m{P}_n)=\{v_i^j{v}_{i+1}^j:1\le i\le n-1,1\le j\le m\}$. We shall consider three cases:

Case 1. When $n\equiv 0,2(\mathrm{mod}4)$, define a labeling f of $m{P}_n$ as follows.

$$f(v_i^j)=\left\{\begin{array}{cc}n(j-1)+\frac{i}{2},\hfill & \mathrm{if}\mathrm{i}\mathrm{even},\hfill \\ n(j-1)+\frac{i+n+1}{2},\hfill & \mathrm{if}\mathrm{i}\mathrm{odd}.\hfill \end{array}\right.$$

Thus, we obtain the weight of each vertex as follows.

$${\omega }_f(v_i^j)=\left\{\begin{array}{cc}1+n(j-1),\hfill & \mathrm{if}i=1,\hfill \\ (n+i+1)+2n(j-1),\hfill & \mathrm{if}i=2,4,\dots ,n-2,\hfill \\ i+2n(j-1),\hfill & \mathrm{if}i=3,5,\dots ,n-1,\hfill \\ nj,\hfill & \mathrm{if}i=n.\hfill \end{array}\right.$$

Case 2. When $n\equiv 1(\mathrm{mod}4)$, define a labeling f of $m{P}_n$ as follows.

$$f(v_i^j)=\left\{\begin{array}{cc}3-i+n(j-1),\hfill & \mathrm{if}i=1,2,\hfill \\ n-\frac{i-3}{2}+n(j-1),\hfill & \mathrm{if}i=3,5,\dots ,n,\hfill \\ \frac{n+5-i}{2}+n(j-1),\hfill & \mathrm{if}i=4,6,\dots ,n-1.\hfill \end{array}\right.$$

Thus, the weight of each vertex is as follows.

$${\omega }_f(v_i^j)=\left\{\begin{array}{cc}1+n(j-1),\hfill & \mathrm{if}i=1,\hfill \\ n+2+2n(j-1),\hfill & \mathrm{if}i=2,\hfill \\ \frac{1}{2}(n+3)+2n(j-1),\hfill & \mathrm{if}i=3,\hfill \\ 2n-i+3+2n(j-1),\hfill & \mathrm{if}i=4,6,\dots ,n-1,\hfill \\ n+5-i+2n(j-1),\hfill & \mathrm{if}i=5,7,\dots ,n-2,\hfill \\ 3+n(j-1),\hfill & \mathrm{if}i=n.\hfill \end{array}\right.$$

Case 3. When $n\equiv 3(\mathrm{mod}4)$, define a labeling f of $m{P}_n$ as follows.

$$f(v_i^j)=\left\{\begin{array}{cc}i+n(j-1),\hfill & \mathrm{if}i=1,2,\hfill \\ n-\frac{i-3}{2}+n(j-1),\hfill & \mathrm{if}i=3,5,\dots ,n,\hfill \\ \frac{n+5-i}{2}+n(j-1),\hfill & \mathrm{if}i=4,6,\dots ,n-1.\hfill \end{array}\right.$$

This leads to the following weights of vertices.

$${\omega }_f(v_i^j)=\left\{\begin{array}{cc}2+n(j-1),\hfill & \mathrm{if}i=1,\hfill \\ n+1+2n(j-1),\hfill & \mathrm{if}i=2,\hfill \\ \frac{1}{2}(n+5)+2n(j-1),\hfill & \mathrm{if}i=3,\hfill \\ 2n-i+3+2n(j-1),\hfill & \mathrm{if}i=4,6,\dots ,n-1,\hfill \\ n+5-1+2n(j-1),\hfill & \mathrm{if}i=5,7,\dots ,n-2,\hfill \\ 3+n(j-1),\hfill & \mathrm{if}i=n.\hfill \end{array}\right.$$

This concludes the proof since, in all three cases, all the vertex-weights are distinct. An example of a distance antimagic labeling for $4P_5$ is depicted in Figure 2. □

In general, we are still not able to prove that the disjoint union of arbitrary paths is distance antimagic.

Problem 1.

Show that ${\cup }_{i=1}^k{P}_{n_i}$, where $n_i\ne 3,1\le i\le k$, is distance antimagic.

The next three theorems deal with the distance antimagicness of graphs containing many triangles, i.e., wheels, fans, and friendship graphs. A wheel $W_n$ is a graph obtained by joining all vertices of a cycle of order n to another vertex called the center. Let $V(W_n)=\{x_0,x_1,\dots ,x_n\}$ where $x_0$ is the center and $x_1,\dots ,x_n$ are the vertices of the cycle.

Theorem 5.

For $m\ge 1$ and $n\ge 3$, $m{W}_n$ is distance antimagic.

Proof. 

Let $V(m{W}_n)=\left\{x_i^j\right|i=0,1,\dots ,n,j=1,2,\dots ,m\}$. We define different vertex labelings f of $m{W}_n$, depending on the value of n.

Case 1. When n is even.

Sub Case 1.1. When $n\equiv 0(\mathrm{mod}4)$.

$$f(x_i^j)=\left\{\begin{array}{ccc}(n+1)j\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (n+1)(j-1)+1\hfill & \mathrm{for}\hfill & i=1,\hfill \\ (n+1)(j-1)+(i-1)\hfill & \mathrm{for}\hfill & i=3,5,\dots ,\frac{1}{2}n+1,\hfill \\ (n+1)(j-1)(n+2-i)\hfill & \mathrm{for}\hfill & i=\frac{1}{2}n+3,\frac{1}{2}n+5,\dots ,n-1,\hfill \\ (n+1)(j-1)+\frac{1}{2}n-1+i\hfill & \mathrm{for}\hfill & i=2,4,\dots ,\frac{1}{2}n,\hfill \\ (n+1)(j-1)+\frac{1}{2}3n+2-i\hfill & \mathrm{for}\hfill & i=\frac{1}{2}n+2,\frac{1}{2}n+4,\dots ,n.\hfill \end{array}\right.$$

This will lead to the following weights of vertices.

$${\omega }_f(x_i^j)=\left\{\begin{array}{ccc}\frac{1}{2}n(n+1)(2j-1)\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (n+1)(3j-2)+n+3\hfill & \mathrm{for}\hfill & i=1,\hfill \\ (n+1)(3j-2)+3\hfill & \mathrm{for}\hfill & i=2,\hfill \\ (n+1)(3j-2)+n-2+2i\hfill & \mathrm{for}\hfill & i=3,5,\dots ,\frac{1}{2}n-1,\hfill \\ (n+1)(3j-2)+2n-1\hfill & \mathrm{for}\hfill & i=\frac{1}{2}n+1,\hfill \\ (n+1)(3j-2)+3n+4-2i\hfill & \mathrm{for}\hfill & i=\frac{1}{2}n+3,\frac{1}{2}n+5,\dots ,n-1,\hfill \\ (n+1)(3j-2)-2+2i\hfill & \mathrm{for}\hfill & i=4,6,\dots ,\frac{1}{2}n,\hfill \\ (n+1)(3j-2)+n-1+\frac{1}{2}(1+i)\hfill & \mathrm{for}\hfill & i=\frac{1}{2}n+2,\hfill \\ (n+1)(3j-2)-2n+4-2i\hfill & \mathrm{for}\hfill & i=\frac{1}{2}n+4,\frac{1}{2}n+6,\dots ,n.\hfill \end{array}\right.$$

Sub Case 1.2.$n\equiv 2(\mathrm{mod}4)$.

$$f(x_i^j)=\left\{\begin{array}{ccc}(n+1)j\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (n+1)(j-1)+\frac{1}{2}(i+1)\hfill & \mathrm{for}\hfill & i=1,3,\dots ,n-1,\hfill \\ (n+1)j-\frac{1}{2}i\hfill & \mathrm{for}\hfill & i=2,4,\dots ,n,\hfill \end{array}\right.$$

and so we obtain the following vertex-weights.

$${\omega }_f(x_i^j)=\left\{\begin{array}{ccc}\frac{1}{2}n(n+1)(2j-1)\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (n+1)3j-\frac{1}{2}(n+1+i)\hfill & \mathrm{for}\hfill & i=1,\hfill \\ (n+1)(3j-2)+1+i\hfill & \mathrm{for}\hfill & i=2,4,\cdots ,n-2,\hfill \\ (n+1)3j-i\hfill & \mathrm{for}\hfill & i=3,5,\cdots ,n-1,\hfill \\ (n+1)(3j-2)+\frac{1}{2}(n+2)\hfill & \mathrm{for}\hfill & i=n.\hfill \end{array}\right.$$

Case 2. When n is odd.

Sub Case 2.1. When $n\equiv 1,5(\mathrm{mod}6)$.

$$f(x_i^j)=\left\{\begin{array}{ccc}(n+1)j\hfill & \mathrm{for} j \mathrm{odd}\hfill & i=0,\hfill \\ (n+1)(j-1)+i\hfill & \mathrm{for} j \mathrm{odd}\hfill & i=1,2,\dots ,n,\hfill \\ (n+1)j-n+i\hfill & \mathrm{for} j \mathrm{even}\hfill & i=0,1,\dots ,n.\hfill \end{array}\right.$$

The vertex-weights under this labeling are as follows.

For odd j,

$${\omega }_f(x_i^j)=\left\{\begin{array}{ccc}\frac{1}{2}n(n+1)(2j-1)\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (n+1)(3j-2)+n+2\hfill & \mathrm{for}\hfill & i=1,\hfill \\ (n+1)(3j-2)+2i\hfill & \mathrm{for}\hfill & i=2,3,\cdots ,n-1,\hfill \\ (n+1)(3j-2)+n\hfill & \mathrm{for}\hfill & i=n,\hfill \end{array}\right.$$

and for even j,

$${\omega }_f(x_i^j)=\left\{\begin{array}{ccc}\frac{1}{2}n(2j(n+1)-n+1)\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (n+1)3j-2n+2\hfill & \mathrm{for}\hfill & i=1,\hfill \\ (n+1)3j-3n+2i\hfill & \mathrm{for}\hfill & i=2,3,\cdots ,n-1,\hfill \\ (n+1)3j-2n\hfill & \mathrm{for}\hfill & i=n.\hfill \end{array}\right.$$

Sub Case 2.2. For $n\equiv 3(\mathrm{mod}6)$.

$$f(x_i^j)=\left\{\begin{array}{ccc}(n+1)j\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (n+1)(j-1)+i\hfill & \mathrm{for}\hfill & i=1,2,\dots ,n.\hfill \end{array}\right.$$

Thus, we obtain the following vertex-weights.

$${\omega }_f(x_i^j)=\left\{\begin{array}{ccc}\frac{1}{2}n(n+1)(2j-1)\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (n+1)(3j-2)+n+2\hfill & \mathrm{for}\hfill & i=1,\hfill \\ (n+1)(3j-2)+2i\hfill & \mathrm{for}\hfill & i=2,3,\cdots ,n-1,\hfill \\ (n+1)(3j-2)+n\hfill & \mathrm{for}\hfill & i=n.\hfill \end{array}\right.$$

This concludes the proof since, in all the cases, all the vertex-weights are clearly distinct.

An example of a distance antimagic labeling for $4W_7$ can be seen in Figure 3. □

A fan $F_n$ is a graph obtained by joining all vertices of a path of order n to a further vertex called the center. Let $V(F_n)=\{x_0,x_1,\dots ,x_n\}$ where $x_0$ is the center and $x_1,\dots ,x_n$ are the vertices of the path.

Theorem 6.

For $m\ge 1$ and $n\ge 1$, $m{F}_n$ is distance antimagic.

Proof. 

$V(m{F}_n)=\left\{x_i^j\right|i=0,1,\dots ,n,j=1,2,\dots ,m\}.$ We define a vertex labeling f of $m{F}_n$ as follow:

Case 1. When n is odd,

$$f(x_i^j)=(n+1)(j-1)+1+i,\mathrm{for}i=0,1,\cdots ,n,$$

and thus we obtain the following vertex-weights.

$${\omega }_f(x_i^j)=\left\{\begin{array}{ccc}n(n+1)(j-1)+\frac{1}{2}n(n+3)\hfill & \mathrm{for}\hfill & i=0,\hfill \\ 2(n+1)(j-1)+4\hfill & \mathrm{for}\hfill & i=1,\hfill \\ 3(n+1)(j-1)+3+2i\hfill & \mathrm{for}\hfill & i=2,3,\cdots ,n-1,\hfill \\ 2(n+1)(j-1)+n+1\hfill & \mathrm{for}\hfill & i=n.\hfill \end{array}\right.$$

Case 2. When n is even.

Sub Case 2.1. When $j=2,4(\mathrm{mod}6)$,

$$f(x_i^j)=\left\{\begin{array}{ccc}(n+1)(j-1)+\frac{1}{2}(n+2)\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (n+1)(j-1)+i\hfill & \mathrm{for}\hfill & i=1,2,\dots ,\frac{n}{2},\hfill \\ (n+1)(j-1)+1+i\hfill & \mathrm{for}\hfill & i=\frac{n}{2}+1,\frac{n}{2}+2,\dots ,n,\hfill \end{array}\right.$$

which leads to the following vertex-weights.

$${\omega }_f(x_i^j)=\left\{\begin{array}{ccc}n(n+1)(j-1)+\frac{1}{2}n(n+2)\hfill & \mathrm{for}\hfill & i=0,\hfill \\ 2(n+1)(j-1)+\frac{1}{2}n+3\hfill & \mathrm{for}\hfill & i=1,\hfill \\ 3(n+1)(j-1)+\frac{1}{2}n+1+2i\hfill & \mathrm{for}\hfill & i=2,3,\dots ,\frac{n}{2}-1\hfill \\ 3(n+1)(j-1)+\frac{1}{2}n+2+2i\hfill & \mathrm{for}\hfill & i=\frac{n}{2},\frac{n}{2}+1,\hfill \\ 3(n+1)(j-1)+\frac{1}{2}n+3+2i\hfill & \mathrm{for}\hfill & i=\frac{n}{2}+2,\frac{n}{2}+1,\dots ,n-1,\hfill \\ 2(n+1)(j-1)+\frac{1}{2}(3n+2)\hfill & \mathrm{for}\hfill & i=n.\hfill \end{array}\right.$$

Sub Case 2.2. When $j=0(\mathrm{mod}6)$,

$$f(x_i^j)=\left\{\begin{array}{ccc}(n+1)j-\frac{n}{2}+i\hfill & \mathrm{for}\hfill & i=0,1,\dots ,\frac{n}{2},\hfill \\ (n+1)(j-1)-\frac{n}{2}+i\hfill & \mathrm{for}\hfill & i=\frac{n}{2}+1,\frac{n}{2}+2,\dots ,n,\hfill \end{array}\right.$$

and so we obtain the following vertex-weights.

$${\omega }_f(x_i^j)=\left\{\begin{array}{ccc}nj(n+1)-\frac{1}{2}{n}^2\hfill & \mathrm{for}\hfill & i=0,\hfill \\ 2j(n+1)-n+2\hfill & \mathrm{for}\hfill & i=1,\hfill \\ 3j(n+1)-\frac{1}{2}3+2i\hfill & \mathrm{for}\hfill & i=2,3,\dots ,\frac{n}{2}-1\hfill \\ 3j(n+1)-\frac{1}{2}5n-1+2i\hfill & \mathrm{for}\hfill & i=\frac{n}{2},\frac{n}{2}+1,\hfill \\ 3j(n+1)(j-1)-\frac{1}{2}7n-2+2i\hfill & \mathrm{for}\hfill & i=\frac{n}{2}+2,\frac{n}{2}+1,\dots ,n-1,\hfill \\ 2j(n+1)-n-2\hfill & \mathrm{for}\hfill & i=n.\hfill \end{array}\right.$$

In all cases, we can see that all the weights are distinct.

Examples of distance antimagic labelings for for $4F_6$ and $4F_7$ are depicted in Figure 4. □

A friendship graph $f_n$ is obtained by identifying a vertex from n copies of cycles of order 3. Let $V(m{f}_n)=\{x_0^j,x_1^j,\dots ,x_{2n}^j\}$ where $x_0^j,x_{2i-1}^j,x_{2i}^j$ are the vertices in the j-th $C_3$, for $i=1,\dots ,n$ and $j=1,2,\dots ,m.$

Theorem 7.

For $m\ge 1$ and $n\ge 3$, $m{f}_n$ is distance antimagic.

Proof. 

We define a vertex labeling f of $m{f}_n$ as follow.

For $j=1,2,\dots ,m$,

$$f(x_i^j)=\left\{\begin{array}{ccc}(2n+1)j,\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (2n+1)(j-1)+i,\hfill & \mathrm{for}\hfill & i=1,2,\cdots ,2n,\hfill \end{array}\right.$$

and so we obtain the following vertex-weights.

$${\omega }_f(x_i^j)=\left\{\begin{array}{ccc}n(2n+1)(2j-1),\hfill & \mathrm{for}\hfill & i=0,\hfill \\ (4n+2)j-2n+i,\hfill & \mathrm{for}\hfill & i=1,3,\cdots ,2n-1,\hfill \\ (4n+2)j-2(n+1)+i,\hfill & \mathrm{for}\hfill & i=2,4,\cdots ,2n,\hfill \end{array}\right.$$

where all the weights are distinct.

An example of a distance antimagic labeling for $4f_3$ can be viewed in Figure 5.  □

We conclude this section by considering the disjoint union of unicyclic graphs. A sun $S_n$ is a cycle on n vertices with a leaf attached to each vertex on the cycle. Let the vertex set of sun $V(S_n)=\{x_1,\dots ,x_n,y_1,\dots ,y_n\},$ where $d(x_i)=3$ and $d(y_i)=1$.

Theorem 8.

For $m\ge 1$ and $n\ge 1$, $m{S}_n$ is distance antimagic.

Proof. 

Let $V(m{S}_n)=\{x_i^j,y_i^j|i=1,\dots ,n,j=1,2,\dots ,m\}$. We define a vertex labeling f of $m{S}_n$ as follows.

$$f(x_i^j)=(m+j-1)n+i,\mathrm{for}i=1,2,\dots ,n,$$

and

$$f(y_i^j)=(j-1)n+i,\mathrm{for}i=1,2,\dots ,n.$$

Under the labeling f, the vertex-weights are

$${\omega }_f(y_i^j)=f(x_i^j)=(m+j-1)n+i,\mathrm{for}i=1,2,\dots ,n,$$

and

$${\omega }_f(x_i^j)=\left\{\begin{array}{cc}2n(m-1)+3+3nj,\hfill & \mathrm{for}i=1,\hfill \\ n(2m-3)+3(nj+i),\hfill & \mathrm{for}i=2,3,\dots ,n-1,\hfill \\ n(2m-1)+3nj,\hfill & \mathrm{for}i=n,\hfill \end{array}\right.$$

which are all distinct.

An example of a distance antimagic labeling for $3S_7$ is in Figure 6. □

With several examples that we have presented, more general questions are in the following.

Problem 2.

If G is a non-regular graph containing no $\left\{1\right\}$-twins, show that $nG$ is distance antimagic.

Problem 3.

If $G_1,G_2,\dots G_n$ are non-regular graphs containing no $\left\{1\right\}$-twins, show that ${\bigcup }_{i=1}^n{G}_i$ is distance antimagic.

4. Distance-D Graph and D-(Anti)magic Labeling

For any connected graph G, we denote by $G_k,1\le k\le diam(G)$, the distance-k graph of G, as the graph whose vertices are those of G and whose edges are the 2-subsets of vertices at mutual distance k in G [22]. In particular, $G_1=G$. On the other hand, the k-th power graph of a graph G, $G^k$, is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k [23]. Clearly, $G^{diam(G)}=K_v$.

We generalize the two aforementioned graphs by defining the distance-D graph of G, $G_D$, as the graph with the same vertices as G, where two vertices are adjacent when their distance in G is in D. Clearly, the distance-k graph $G_k=G_{\left\{k\right\}}$ and the kth power $G^k=G_{\{0,1,2,\dots ,k\}}$. (For examples, see Figure 7 and Figure 8.)

The next theorem shows that when G is D-(anti)magic, $G_D$ is either $\left\{1\right\}$-(anti)magic or $\{0,1\}$-(anti)magic.

Theorem 9.

Let G be a D-(anti)magic graph.

1. 

If D does not contain 0 then $G_D$ is $\left\{1\right\}$-(anti)magic.

2. 

If D contains 0 then $G_D$ is $\{0,1\}$-(anti)magic.

Proof. 

Suppose that f is an (anti)magic labeling of G. From the definition of $G_D$, for any x, $N(x)$ in $G_D$ is the same with $N_D(x)$ in G. If D does not contain 0, then ${\sum }_{y\in N(x)}f(x)$ in $G_D$ is the same with ${\sum }_{y\in N_D(x)}f(x)$ in G. On the other hand, if D contains 0, then $f(x)+{\sum }_{y\in N(x)}f(x)$ in $G_D$ is the same with ${\sum }_{y\in N_D(x)}f(x)$ in G. □

However, since it is relatively easier to find a distance (anti)magic labeling for a graph, the converse of Theorem 9 is more interesting for us. Let ${\mathcal{G}}_n$ be the set of graphs of order n. Define a function ${\mathcal{F}}_D:{\mathcal{G}}_n\to {\mathcal{G}}_n$, where ${\mathcal{F}}_D(G)=G_D$. It is clear that ${\mathcal{F}}_D$ is neither injective nor surjective. For instance, as depicted in Figure 9, ${(C_4)}_{\left\{2\right\}}$ is $2P_2$, however there is also another graph, in this case $P_4$, where ${(P_4)}_{\left\{2\right\}}=2P_2$. Notice that both $C_4$ and $P_4$ are $\left\{2\right\}$-antimagic with the same vertex labeling.

Despite the fact that ${\mathcal{F}}_D$ is not invertible, we can still state the following.

Theorem 10.

Suppose one of the following conditions holds:

1. 

Let D be a distance set not containing 0 and G be a $\left\{1\right\}$-(anti)magic graph.

2. 

Let D be a distance set containing 0 and G be a $\{0,1\}$-(anti)magic graph.

If there exists a graph H such that $G=H_D$, then H is D-(anti)magic.

Theorem 10 hints that if we manage to find a distance (anti)magic graph, we might as well find D-(anti)magic graphs for suitable sets of Ds.