Risma Yulina Wulandari^a , Rinovia Simanjuntak^∗,b,c

^aMaster's Program in Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia

^bCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences,

Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia

^cCentre for Research Collaboration in Graph Theory and Combinatorics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia

rismayulina2107@gmail.com, rino@math.itb.ac.id

A graph G is distance antimagic if there is a bijection f : V (G) → {1, 2, . . . , |V (G)|} such that for every pair of distinct vertices x and y applies w(x) ̸= w(y), where w(x) = P z∈N(x) f(z) and N(x) is the neighbourhood of x, i.e., the set of all vertices adjacent to x. It was conjectured that a graph is distance antimagic if and only if each vertex in the graph has a distinct neighbourhood. In this paper, we study the truth of the conjecture by posing sufficient conditions and constructing distance antimagic product graphs; the products under consideration are join, corona, and Cartesian.

Keywords: distance antimagic labeling, join product, corona product, Cartesian product

Mathematics Subject Classification: 05C55, 05D10

DOI: 10.5614/ejgta.2023.11.1.9

1. Introduction

Let G = G(V, E) be a finite, simple, and undirected graph with v vertices and e edges. In 1994, Vilfred introduced the concept of a distance magic graph in his Ph.D. thesis [10]. A graph G is called distance magic if there exists a bijection f : V (G) → {1, 2, . . . , v} such that at any vertex

Received: 2 July 2022, Revised: 9 October 2022, Accepted: 6 December 2022.

^∗ corresponding author

x, the weight of x, \(\omega(x) = \sum_{y \in N(x)} f(y)\) is constant, where N(x) is the open neighbourhood of x, i.e., the set of vertices adjacent to x. In 2013, Kamatchi and Arumugam [7] introduced the concept of a distance antimagic graph. A graph G is said to be distance antimagic if there is a bijection \(f: V(G) \to \{1, 2, \dots, v\}\) such that for every pair of distinct vertices x and y applies \(w(x) \neq w(y)\). In this case, the bijection f is called antimagic labeling of G. In the same paper, Kamatchi and Arumugam conjectured the following.

Conjecture 1.1. [7] A graph G is distance antimagic if and only if G does not have two vertices with the same neighbourhood.

In this paper, we study the truth of the conjecture for some product graphs. We pose sufficient conditions such that the join product of an arbitrary graph with a complete graph is distance antimagic (Section 2). We also prove that the corona product of two complete graphs is distance antimagic and poses sufficient conditions for the corona product of two arbitrary graphs to be distance antimagic (Section 3). To conclude, we provide sufficient conditions for the Cartesian product of an arbitrary graph with a \(K_2\) to be distance antimagic and prove that the Cartesian product of two complete graphs is distance antimagic (Section 4).

We start by providing the definitions and notations of graph products studied in this paper.

Definition 1.1. [9] The join product of G and H, denoted by G + H, is the graph \(G \cup H\) together with all the edges joining V(G) and V(H).

Definition 1.2. [3] The corona product of G and H, denoted by \(G \odot H\), is the graph obtained by taking a copy of G and |V(G)| copies of H and joining the i-th vertex of G to every vertex in the i-th copy of H.

Definition 1.3. [6] The Cartesian product of G and H, denoted by \(G \square H\), is the graph with \(V(G \square H) = V(G) \times V(H)\) and two vertices (u, u') and (v, v') are adjacent if and only if either 1. u = v and u' is adjacent to v' in H, or 2. u' = v' and u is adjacent to v in G.

Notice that throughout the paper we will use \(w_G(x)\) as the weight of a vertex x in the graph G, while w(x) is the weight of a vertex x in the product graph.

2. Distance Antimagic Labelings of Join Product Graphs

In their seminal paper, Kamatchi and Arumugam [7] proved that the wheel, \(C_n + K_1\), and \(rK_2 + K_1\) are distance antimagic. They also posed the following problem.

Problem 2.1. [7] If G is distance antimagic, is it true that the graph \(G + K_1\) and \(G + K_2\) are distance antimagic?

In the following two theorems, we provide sufficient conditions such that the answer to the previous problem is affirmative.

Theorem 2.1. Let G be a graph on n vertices with maximum degree \(\Delta\). If \(G = K_n\) or G is distance antimagic with \(n \geq \Delta + 1 + \left\lfloor \frac{1 + \sqrt{8\Delta + 9}}{2} \right\rfloor\) then \(G + K_1\) is also distance antimagic.

Proof. If \(G = K_n\), then \(G + K_1 = K_{n+1}\) which is obviously distance antimagic.

Now, consider G a distance antimagic graph with \(n \ge \Delta + 1 + \left\lfloor \frac{1 + \sqrt{8\Delta + 9}}{2} \right\rfloor\). Let g be the distance antimagic labeling of G and \(V(K_1) = \{u\}\).

Define \(f: V(G + K_1) \to \{1, 2, ..., n + 1\}\) with

\[f(x) = \begin{cases} g(x), & \text{for every } x \in V(G), \\ n+1, & \text{for } x = u. \end{cases}\]

Let x, y be two distinct vertices in G. Since \(w_G(x) \neq w_G(y)\) then

\[w_G(x) + n + 1 \neq w_G(y) + n + 1,\]

that is \(w(x) \neq w(y)\).

Next, we will prove that \(w(x) \neq w(u)\), for every \(x \in V(G)\). Note that

\[w(u) = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.\]

Assume that there is \(x \in V(G)\) such that w(x) = w(u), then

\[w_G(x) + n + 1 = \frac{n(n+1)}{2}\]
\(w_G(x) = (n+1)(\frac{n}{2} - 1).\)

Since G is a graph with maximum degree \(\Delta\), then the weights of all vertices a bounded above by the sum of \(\Delta\) largest labels.

\[w_G(x) \le n + (n-1) + (n-2) + \dots + (n-\Delta+1)\]\[(n+1)(\frac{n}{2}-1) \le n\Delta - \frac{\Delta(\Delta-1)}{2}\]\[n^2 - (1+2\Delta)n - 2 + \Delta(\Delta-1) \le 0.\]

Thus,

\[\Delta + \frac{1 - \sqrt{8\Delta + 9}}{2} \le n \le \Delta + \frac{1 + \sqrt{8\Delta + 9}}{2},\]

a contradiction, and so there is no \(x \in G\) such that w(x) = w(u).

Some examples of Theorem 2.1 are in the following.

Example 2.1. 1. For \(n \ge 2\), \(K_n + K_1\) is distance antimagic.

• 2. Let G be a distance antimagic disjoint union of paths. For \(n \geq 6\), \(G + K_1\) is distance antimagic.
• 3. Let G be a 2-regular graph. For \(n \geq 6\), \(G + K_1\) is distance antimagic.

We obtain the following result using the same proof technique as in Theorem 2.1.

Theorem 2.2. Let G be graph on n vertices with maximum degree \(\Delta\). If \(G \cong K_n\) or G is distance antimagic with \(n \geq \Delta + 1 + \left\lfloor \frac{1 + \sqrt{8\Delta + 17}}{2} \right\rfloor\), then \(G + K_2 \cong (G + K_1) + K_1\) is also distance antimagic.

We have the following examples for the application of Theorem 2.2.

Example 2.2. 1. For \(n \ge 2\), \(K_n + K_2\) is distance antimagic.

• 2. Let G be a distance antimagic disjoint union of paths. For \(n \geq 6\), \(G + K_2\) is distance antimagic.
• 3. Let G be a 2-regular graph. For \(n \geq 6\), \(G + K_2\) is distance antimagic.
• 4. Let G be a distance antimagic 3-regular graph. For \(n \geq 7\), \(G + K_2\) is distance antimagic.

Furthermore, the previous two theorems can be generalized inductively, and we obtain the following.

Theorem 2.3. Let m be a positive integer. Let G be a graph on n vertices with maximum degree \(\Delta\). If \(G \cong K_n\) or G is distance antimagic with \(n \geq \Delta + 1 + \left\lfloor \frac{1 + \sqrt{8(\Delta + m) + 1}}{2} \right\rfloor\), then \(G + K_m\) is also distance antimagic.

Proof. The proof will be by induction on m. For m=1, the statement is true by Theorem 2.1. Now, assume that the statement is true for m=p-1, and we shall show that the statement is also true for m=p.

If \(G=K_n\), then \(G+K_m=K_{n+1}\) which is obviously distance antimagic. Thus consider G as a distance antimagic graph with \(n\geq \Delta+1+\left\lfloor\frac{1+\sqrt{8(\Delta+p)+1}}{2}\right\rfloor\). Let g be a distance antimagic labeling of G and \(V(K_p)=\{u_1,u_2,\ldots,u_p\}\). Define \(f:V(G+K_p)\to\{1,2,\ldots,n+p\}\) with f(x)=g(x) for \(x\in V(G)\) and \(f(u_i)=n+i\) for \(i\in\{1,2,\ldots,p\}\). For two distinct vertices x,y in \(G,w(x)\neq w(y)\) since \(w_G(x)\neq w_G(y)\) and \(w_G(x)+np+\frac{p(p+1)}{2}\neq w_G(y)+np+\frac{p(p+1)}{2}\). For two distinct vertices \(u_i,u_j\) in \(K_p\), it is clear that \(w(u_i)\neq w(u_j)\).

Based on the induction hypothesis, \(w(x) \neq w(u_i)\), for every \(x \in V(G)\) and \(i \in \{1, 2, \dots, p-1\}\). The proof is complete if \(w(x) \neq w(u_p)\), for every \(x \in V(G)\). We shall show this by using contradiction. For the contrary, assume that there exists a vertex x in G such that \(w(x) = w(u_p)\). This leads to

\[w_G(x) + np + \frac{p(p+1)}{2} = \frac{n(n+1)}{2} + \frac{p(p-1)}{2} + n(p-1)\]\[w_G(x) = \frac{n^2 - n - 2p}{2}.\]

Since G has a maximum degree \(\Delta\), then

\[w_G(x) \le n + (n - 1) + \dots + (n - \Delta + 1)\]\[\frac{n^2 - n - 2p}{2} \le n\Delta - \frac{\Delta(\Delta - 1)}{2}\]\[n^2 - (1 + 2\Delta)n - 2p + \Delta^2 + \Delta \le 0.\]

\[\Delta + \frac{1 - \sqrt{8(\Delta + p) + 1}}{2} \le n \le \Delta + \frac{1 + \sqrt{8(\Delta + p) + 1}}{2},\]

a contradiction.

In the following, we can see examples of the application of Theorem 2.3.

Example 2.3. 1. For \(n \ge 2\), \(K_n + K_m\) is distance antimagic.

• 2. Let G be a distance antimagic disjoint union of paths. For \((n \ge 7 \text{ and } 4 \le m \le 7)\) or \((n \ge 8 \text{ and } 4 \le m \le 7)\)and \(8 \le m \le 12\)), \(G + K_m\) is distance antimagic.
• 3. Let G be a 2-regular graph. For \((n \ge 7 \text{ and } 4 \le m \le 7)\) or \((n \ge 8 \text{ and } 8 \le m \le 12)\), \(G + K_m\) is distance antimagic.

Note that if G does not contain two vertices with the same neighborhood, then neither does \(G + K_m\). Considering Conjecture 1.1, it is natural to suspect that the sufficient conditions in Theorem 2.3 are not necessary, so we pose the following question.

Problem 2.2. Let m be a positive integer. Let G be a graph on n vertices with maximum degree \(\Delta\) and \(\Delta + 2 \leq n \leq \Delta + \left\lfloor \frac{1 + \sqrt{8(\Delta + m) + 1}}{2} \right\rfloor\). If G is distance antimagic, is \(G + K_m\) also distance

3. Distance Antimagic Labelings of Corona Product Graphs

In [7], Kamatchi and Arumugam proved that the \(G \odot K_1\) is distance antimagic for arbitrary graf G. Thus \(G \odot \overline{K_n}\) is distance antimagic if and only if n=1 [8]. Other results for corona product graphs are sufficient conditions for \(K_1 \odot G\), \(\overline{K_2} \odot G\), \(G \odot P_2\), and \(P_2 \odot G\) to be distance antimagic [8].

Our first result for corona product graphs is constructing a distance antimagic labeling for the corona product of two complete graphs. To do so, we shall utilize the elements of the following matrix.

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

Notice that the sum of each column in A is equal to \(\frac{(m+1)(nm+n+1)}{(2)}\).

Theorem 3.1. If n and m are integers with odd m, then \(K_n \odot K_m\) is distance antimagic.

Proof. Let \(V(K_n \odot K_m) = \{v_1, v_2, \dots, v_n\} \cup \{v_{i,j} | i = 1, 2, \dots, n, j = 1, 2, \dots, m\}\) where \(\{v_1, v_2, \dots, v_n\} = V(K_n)\) and \(E(K_n \odot K_m) = E(K_n) \cup \{v_i v_{i,j} | i = 1, 2, \dots, n; j = 1, 2, \dots, m\} \cup \{v_{i,a} v_{i,b} | i = 1, 2, \dots, n; a, b = 1, 2, \dots, m; a \neq b\}.\)

Define \(f: V(K_n \odot K_m) \to \{1, 2, \dots n(m+1)\}\) with \(f(v_i) = a_{1,i}\) and \(f(v_{i,j}) = a_{j+1,i}\) for \(i = 1, 2, \dots, n\).

Since the sum of each column in A is \(\frac{(m+1)(nm+n+1)}{2}\), then \(w(v_i) = \frac{n(n+1)}{2} + \frac{(m+1)(nm+n+1)}{2} - 2f(v_i)\), and so \(w(v_i) \neq w(v_j)\). Additionally, since \(w(v_{i,j}) = \frac{(m+1)(nm+n+1)}{2} - f(v_{i,j})\) and \(f(v_{a,b}) \neq f(v_{c,d})\) for every \(v_{a,b} \neq v_{c,d}\), then \(\frac{(m+1)(nm+n+1)}{2} - f(v_{a,b}) \neq \frac{(m+1)(nm+n+1)}{2} - f(v_{c,d})\), or \(w(v_{a,b}) \neq w(v_{c,d})\).

Next, we will prove that \(w(v_i) \neq w(v_{a,b})\) for every \(v_i, v_{a,b}\). Denote by \(\alpha = min\{w(v_i)\} = \frac{n(n+1)}{2} + \frac{(m+1)(nm+n+1)}{2} - 2f(v_i) - 2n = \text{and } \beta = max\{w(v_{a,b})\} = \frac{(m+1)(nm+n+1)}{2} - (n+1)\). We shall prove that \(\alpha > \beta\). For the contrary, suppose that \(\beta > \alpha\). Thus,

\[\frac{(m+1)(nm+n+1)}{2}-(n+1)\geq \frac{n(n+1)}{2}+\frac{(m+1)(nm+n+1)}{2}-2n, \text{ or } 1>\frac{(n+1)}{2},\]

a contradiction with \(n \ge 1\). This completes the proof.

Theorem 3.1 only provides distance antimagic labelings \(K_n \odot K_m\) only when m is odd, so we ask the following question.

Problem 3.1. Is \(K_n \odot K_m\) a distance antimagic graph for even m?

In [5], Handa et al. provided sufficient conditions for the corona product of arbitrary two graphs to be distance antimagic, as stated in the following theorem. One condition is for one of the graphs to be arbitrarily distance antimagic.

For a bijection \(f:V(G)\to\{1,2,\ldots,n\}\) and a positive integer k, define a bijection \(f_k:V(G)\to\{k+1,k+2,\ldots,k+n\}\) by \(f_k(x)=f(x)+k\). A graph G of order n is said to be arbitrarily distance antimagic if there exists a bijection \(f:V(G)\to\{1,2,\ldots,n\}\) such that for any \(k\geq 0\), \(w_{f_k}(x)\neq w_{f_k}(y)\) for any two distinct vertices x and y. To conclude this section, we present Theorem 3.3 that provides other sufficient conditions for the corona product of arbitrary two graphs to be distance antimagic.

Theorem 3.2. [5] Suppose that \(G_1\) is a distance magic graph of order \(n_1\) with magic constant k and \(G_2\) is an 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. If \(k + \frac{n_2}{2}(n_2 + 2n_1 + 1) > n_1 r(1 + \frac{(n_1 - 1)n_2}{n_1}) + (K + n_1)\) then \(G_1 \odot G_2\) is distance antimagic.

We shall utilize the following definition that was introduced in [8]. Although originally defined as monoton, in this paper, we use the notion of monotonic increasing to avoid confusion with monotonic decreasing, which will be used in the next section.

Definition 3.2. Let G be a graph on n vertices. G is said to be monotonic increasing if there exists a bijection \(g: V(G) \to \{1, 2, ..., n\}\) such that \(w_G(x) \ge w_G(y)\) for every g(x) > g(y).

Figure 1. An example of a monotonic increasing graph. The weights of the vertices are written in brackets.

Theorem 3.3. Let n, m, r be integers with \(n \ge 2\). Let G be a graph on n vertices that is monotonic increasing under a bijection g and let H be an r-regular graph on m vertices, which is distance antimagic. Denote by k and K the minimum and maximum weight of a vertex in G under the bijection g, respectively. If

\[m > rn - r + \frac{-1 + \sqrt{4r^2n^2 - 8r^2n + 4rn + 8n + 8r - 8k + 1}}{2} \text{ or }\] \[r + 1 \le m < \frac{-2n - 1 + \sqrt{4n^2 + 20n + 7 + (8 - 16n)K + 16rn^2 + 8r^2n - 4r^2 - 4r}}{4n - 2},\]

then \(G \odot H\) is distance antimagic.

Proof. Let \(V(G) = \{v_1, v_2, \dots, v_n\}\), \(V(H) = \{u_1, u_2, \dots, u_m\}\), and h be a distance antimagic labeling on H.

Denote by \(V(G \odot H) = V(G) \cup \{v_{i,j} | i = 1, 2, \dots, n, j = 1, 2, \dots, m\}\) and \(E(G \odot H) = E(G) \cup \{(v_i, v_{i,j}) | i = 1, 2, \dots, n; j = 1, 2, \dots, m\} \cup \{(v_{i,j}, v_{i,k}) | i = 1, 2, \dots, n; j, k \text{ where } (u_j, u_k) \in E(H)\}\). Define \(f: V(G \odot H) \rightarrow \{1, 2, \dots, n(m+1)\}\) by \(f(v_i) = g(v_i)\) and \(f(v_{i,j}) = n + (i-1)m + h(u_j)\) for \(i = 1, 2, \dots, n\) and \(j = 1, 2, \dots, m\).

Due to the fact that \((v_i, v_{i,j}) \in E(G \odot H)\), then \(w(v_i) = w_G(v_i) + m(n + (i-1)m) + \frac{m(m+1)}{2}\). Since g is monotonic increasing and \(m(n+(i-1)m) + \frac{m(m+1)}{2}\) is distinct for every i then \(w(v_1) < w(v_2) < \ldots < w(v_n)\). The fact that for any distinct vertices x, y in H, \(w_H(x) \neq w_H(y)\), leads to \(r(n+(i-1)m) + w_H(x) + i \neq r(n+(i-1)m) + w_H(y) + i\) or \(w(v_{i,x}) \neq w(v_{i,y})\).

Denote by \(x_{min}\) and \(x_{max}\) the vertices in H with minimum and maximum weight under the labeling h, respectively. Thus, it is clear that \(w_H(x_{max}) - w_H(x_{min}) \le rm - r^2 < rm + 1\), and so

\[\begin{split} w_H(x_{max}) - rm &< w_H(x_{min}) + 1, \\ r(n + (i-1)m) + w_H(x_{max}) + i &< r(n + (i)m) + w_H(x_{min}) + i + 1, \text{for every } i \\ \max\{w(v_{i,j})\} &< \min\{w(v_{i+1,j})\}, \text{for every } i, \end{split}\]

which means \(w(v_{a,b}) \neq w(v_{c,d})\) for any two distinct vertices \(v_{a,b}, v_{c,d}, 1 \leq a \leq c \leq n\) and \(1 \leq b < d \leq m\).

Lastly, we will prove that \(w(v_i) \neq w(v_{a,b})\), for any \(i, a \in \{1, 2, ..., n\}\) and \(b \in \{1, 2, ..., m\}\). We consider the following two cases.

Case 1. \(m > rn - r + \frac{-1 + \sqrt{4r^2n^2 - 8r^2n + 4rn + 8n + 8r - 8k + 1}}{2}\). Denote by \(\alpha = \min\{w(v_i)\} = w(v_1) = w_G(v_1) + mn + \frac{m(m+1)}{2} = k + mn + \frac{m(m+1)}{2}\) and by \(\beta = \max\{w(v_{a,b})|a=1,2,\ldots,n,b=1,2,\ldots,m\} = \max\{w(v_{n,b})|b=1,2,\ldots,m\} \le 1\)

\(r(n+(n-1)m)+n+nm-\frac{r(r-1)}{2}\). We will prove that \(\alpha>\beta\). For the contrary, assume that \(\alpha\leq\beta\), and so

\[2k + m^2 + m + \le 2rn + 2rnm - 2rm + 2n - r^2 + r\], or \(m^2 + (1 - 2rn + 2r)m + 2k - 2rn - 2n + r^2 - r \le 0\).

Thus, \(rn-r+\frac{-1-\sqrt{4r^2n^2-8r^2n+4rn+8n+8r-8k+1}}{2} \leq m \leq rn-r+\frac{-1+\sqrt{4r^2n^2-8r^2n+4rn+8n+8r-8k+1}}{2}\) Since

\[rn - r + \frac{-1 - \sqrt{4r^2n^2 - 8r^2n + 4rn + 8n + 8r - 8k + 1}}{2} < r + 1,\]

then \(r+1 \le m \le rn-r+\frac{-1+\sqrt{4r^2n^2-8r^2n+4rn+8n+8r-k+1}}{2}\), a contradiction.

Case 2. \[r+1 \leq m < \frac{-2n-1+\sqrt{4n^2+20n+7+(8-16n)K+16rn^2+8r^2n-4r^2-4r}}{4n-2}\]. Denote by \(\theta = \max\{w(v_i)|i=1,2,\ldots,n\} = w(v_n) = K + m(n+(n-1)m) + \frac{m(m+1)}{2}\) and \(\gamma = m(n+1)\)

Denote by \(\theta = \max\{w(v_i)|i=1,2,\ldots,n\} = w(v_n) = K + m(n+(n-1)m) + \frac{m(m+1)}{2}\) and \(\gamma = \min\{w(v_{a,b})|a=1,2,\ldots,n,b=1,2,\ldots,m\} = \min\{w(v_{1,b})|b=1,2,\ldots,m\} \ge rn+1+\frac{r(r+1)}{2}\). We will show that \(\theta < \gamma\) by contradiction, which leads to the following.

\[K + m(n + (n-1)m) + \frac{m(m+1)}{2} \ge rn + 1 + \frac{r(r+1)}{2}\], or \[(2n-1)m^2 + (2n+1)m - 2rn + 2K - 2 - r^2 - r \ge 0.\]

Thus,

\[m \le \frac{-2n - 1 - \sqrt{4n^2 + 20n + 7 + (8 - 16n)K + 16rn^2 + 8r^2n - 4r^2 - 4r}}{4n - 2} \text{ or }\]

\[m \ge \frac{-2n - 1 + \sqrt{4n^2 + 20n + 7 + (8 - 16n)K + 16rn^2 + 8r^2n - 4r^2 - 4r}}{4n - 2}.\]

Since \(\frac{-2n-1-\sqrt{4n^2+20n+7+(8-16n)K+16rn^2+8r^2n-4r^2-4r}}{4n-2} < 0\) then

\[m \ge \frac{-2n - 1 + \sqrt{4n^2 + 20n + 7 + (8 - 16n)K + 16rn^2 + 8r^2n - 4r^2 - 4r}}{4n - 2},\]

a contradiction.

The following are some examples of corona product graphs that are distance antimagic due to Theorem 3.3.

Example 3.1. Let G be a 2-regular graph with order m.

• 1. For \(m \geq 12\), \(C_4 \odot G\) is distance antimagic.
• 2. For \(m \geq 8\), \(P_3 \odot G\) is distance antimagic.

4. Distance Antimagic Labelings of Cartesian Product Graphs

In this last section, we present our results for Cartesian product graphs. Recall that Kamatchi and Arumugam [7] asked the following question.

Problem 4.1. [7] If G is distance antimagic, is it true that the Cartesian product \(G \square K_2\) is distance antimagic?

Partial answers for the problem were given in [1] and [8], where it was proved that \(P_n \square K_2\), for \(n \neq 2\), \(C_n \square K_2\), and \(K_{n,n} \square K_2\), for \(n \neq 1\), are distance antimagic. We shall provide a more general answer to the question in Theorem 4.1. To do so, we shall utilize the following definition of a monotonic decreasing graph.

Definition 4.1. Let G be a graph on n vertices. G is said to be monotonic decreasing graph if there exists a bijection \(g: V(G) \to \{1, 2, ..., n\}\) such that \(w_G(x) \ge w_G(y)\) for every g(x) < g(y).

An obvious example of a monotonic decreasing graph is the complete graph \(K_n\) that is monotonic decreasing for any bijection on \(K_n\).

Theorem 4.1. Let n, r be integers with \(r > \sqrt{2n-1}\). Let G be an r-regular graph on n vertices. If G is monotonic decreasing then \(G \square K_2\) is distance antimagic.

Proof. Let g be a bijection from V(G) to \(\{1, 2, \ldots, n\}\) with \(g(v_i) = i\) for every \(i = 1, 2, \ldots, n\) such that \(w_G(v_1) \geq w_G(v_2) \geq \ldots \geq w_G(v_n)\). Denote by \(V(G \square K_2) = \{v_i | 1 \leq i \leq n\} \cup \{v_i' | 1 \leq i \leq n\}\) and \(E(G \square K_2) = E(G) \cup \{(v_i, v_i') | 1 \leq i \leq n\} \cup \{(v_i', v_j') | 1 \leq i < j \leq n \text{ where } (v_i, v_j) \in E(G)\}\). Define a bijection \(f: V(G \square K_2) \to \{1, 2, \ldots, 2n\}\) with \(f(v_i) = g(v_i) = i\) and \(f(v_i') = 2n + 1 - i\). It is clear that, \(w(v_i) = w_G(v_i) + f(v_i') = w_G(v_i) + 2n + 1 - i\) and

\[w(v_i') = \sum_{(v_i', x) \in G \square K_2} f(x) = \sum_{(v_i, v_j) \in V(G)} f(v_j') + f(v_i) = r(2n+1) - w_G(v_i) + i.\]

Since \(w_G(v_i) \ge w_G(v_{i+1})\), then \(w_G(v_i) + 2n + 1 - i > w_G(v_{i+1}) + 2n + 1 - (i+1)\), or \(w(v_i) > w(v_{i+1})\). Similarly, \(r(2n+1) - w_G(v_i) + i < r(2n+1) - w_G(v_{i+1}) + i + 1\), or \(w(v_i') < w(v_{i+1}')\), for \(1 \le i \le n-1\).

To complete the proof, we will show that \(w(v_i) \neq w(v'_j)\) for \(i \neq j\). For the contrary, assume that there exist \(i \neq j\) such that \(w(v_i) = w(v'_i)\). Thus,

\[w_G(v_i) + 2n + 1 - i = r(2n+1) - w_G(v_j) + j\]
\[w_G(v_i) + w_G(v_j) = r(2n+1) - (2n+1) + i + j = 2nr + r - 2n - 1 + i + j.\]

Since \(w_G(v_i) + w_G(v_j) \le 2nr - r^2 + r\), then

\[2nr + r - 2n - 1 + i + j \le 2nr - r^2 + r\]\[r^2 - 2n - 1 + (i + j) \le 0.\]

Due to the fact that \(2 \le i + j\), we have \(r^2 - 2n + 1 \le 0\), or \(r \le \sqrt{2n - 1}\), a contradiction. \(\square\)

An example of the application of the previous theorem is presented in the following.

Example 4.1. For \(n \ge 4\), \(K_n \square K_2\) is distance antimagic.

Note that the sufficient conditions in Theorem 4.1 are not necessary as it has been shown that \(C_n \square K_2\) is distance antimagic, although the cycle \(C_n\) is not monotonic decreasing. Therefore it is natural to ask the following.

Problem 4.2. Find necessary and sufficient conditions for G such that \(G \square K_2\) is distance antimagic.

Other results for the Cartesian product graphs are presented in [8] and [2], where it was proved that \(P_m \square K_3\) is distance antimagic, for \(m \ge 1\), and \(C_m \square K_3\) is distance antimagic, for any odd integer \(m \ge 3\). There is also a result for the Cartesian product of two complete graphs of the same order as presented in the following theorem. We conclude by generalizing this result in Theorem 4.3.

Theorem 4.2. [2] \(K_n \square K_n\) is distance antimagic if and only if \(n \neq 2\).

Theorem 4.3. For m, n positive integers, \(K_n \square K_m\) is distance antimagic if and only if \(m \neq 2\) and \(n \neq 2\).

Proof. For n=1 or m=1, it is clear that \(K_n \square K_m\) is distance antimagic. For \(n \geq 4\), \(K_n \square K_2\) is distance antimagic (Example 4.1). Now, consider \(n \geq 3\) and \(m \geq 3\). Let \(V(K_n \square K_m) = \{v_{i,j} | 1 \leq i \leq m, 1 \leq j \leq n\}\) and \(E(K_n \square K_m) = \{(v_{i,j}, v_{i,k}) | 1 \leq i \leq m; 1 \leq j, k \leq n, j \neq k\} \cup \{(v_{i,j}, v_{h,j}) | 1 \leq i, h \leq m; i \neq h; 1 \leq j \leq n\}\). Define \(f: V(K_n \square K_m) \to \{1, 2, \dots, nm\}\) with \(f(v_{i,j}) = (i-1)n+j\), for odd i and \(f(v_{i,j}) = in+1-j\), for even i. Case 1. For even m.

\[\sum_{h=1}^{m} = f(v_{1,j}) + f(v_{2,j}) + \dots + f(v_{m,j})\] \[= j + (2n+1-j) + (2n+j) + (4n+1-j) + \dots + (m-2)n+j+mn+1-j\] \[= \frac{m}{2}(mn+1).\]

Thus the vertex weights are as follows. For odd i,

\[w(v_{i,j}) = \sum_{k \neq j} f(v_{i,k}) + \sum_{h \neq i} f(v_{h,j})\] \[= \sum_{k=1}^{n} f(v_{i,k}) - f(v_{i,j}) + \sum_{h=1}^{m} f(v_{h,j}) - f(v_{i,j})\] \[= n((i-1)n) + \frac{n(n+1)}{2} + \frac{m}{2}(mn+1) - 2((i-1)n+j).\]

For even i,

\[w(v_{i,j}) = \sum_{k \neq j} f(v_{i,k}) + \sum_{h \neq i} f(v_{h,j})\] \[= \sum_{k=1}^{n} f(v_{i,k}) - f(v_{i,j}) + \sum_{h=1}^{m} f(v_{h,j}) - f(v_{i,j})\] \[= n(in+1) - \frac{n(n+1)}{2} + \frac{m}{2}(mn+1) - 2(in+1-j).\]

Therefore, it is clear that w(vi,j ) ̸= w(vh,k) for every distint i, h with the same parity.

Next, we will prove that w(vi,j ) ̸= w(vh,k) for every 1 ≤ i, h ≤ m and 1 ≤ j, k ≤ n with (i, j) ̸= (h, k).

Case 1.1 For n = 3.

Suppose that there are (i, j) ̸= (h, k) such that w(vi,j ) = w(vh,k), then i, h must be of a different parity. WLOG, suppose that i is odd and h is even, then

\[n((i-1)n) + \frac{n(n+1)}{2} - 2((i-1)n+j) = n(hn+1) - \frac{n(n+1)}{2} - 2(hn+1-k),\]\[3(i-h-1) + 11 = 2j + 2k.\]

Because i is odd and h is even then i − h − 1 is even. Since 3(i − h − 1) + 11 is odd, then j + k is not an integer, a contradiction.

Case 1.2 For n ≥ 4.

Note that max{w(vi,j} − min{w(vi+1,j} = −n ² + 4n − 2. Since n ≥ 4, then −n ² + 4n − 2 < 0, and so max{w(vi,j} − min{w(vi+1,j} < 0.

Case 2. For odd m.

Note that,

\[\sum_{h=1}^{m} f(v_{h,j}) = f(v_{1,j}) + f(v_{2,j}) + \dots + f(v_{m,j})\] \[= j + (2n+1-j) + (2n+j) + (4n+1-j) + \dots + (m-1)n + 1 - j + mn + j\] \[= \frac{m-2}{2}(mn-n+1) + mn + j.\]

Then the vertex weights are as follows.

For odd i,

\[w(v_{i,j}) = \sum_{k \neq j} f(v_{i,k}) + \sum_{h \neq i} f(v_{h,j})\] \[= \sum_{k=1}^{n} f(v_{i,k}) - f(v_{i,j}) + \sum_{h=1}^{m} f(v_{h,j}) - f(v_{i,j})\] \[= n((i-1)n) + \frac{n(n+1)}{2} + \frac{m-2}{2}(mn-n+1) + mn + j - 2f(v_{i,j})\] \[= (n-2)(i-1)n + \frac{n(n+1)}{2} + \frac{m-2}{2}(mn-n+1) + mn - j.\]

For even i,

\[w(v_{i,j}) = \sum_{k \neq j} f(v_{i,k}) + \sum_{h \neq i} f(v_{h,j})\] \[= \sum_{k=1}^{n} f(v_{i,k}) - f(v_{i,j}) + \sum_{h=1}^{m} f(v_{h,j}) - f(v_{i,j})\] \[= n(in+1) - \frac{n(n+1)}{2} + \frac{m-2}{2}(mn-n+1) + mn + j - 2f(v_{i,j})\] \[= (n-2)(in+1) - \frac{n(n+1)}{2} + \frac{m-2}{2}(mn-n+1) + mn + 3j.\]

Therefore w(vi,j ) ̸= w(vh,k) for every i ̸= h with the same parity. Next, we will prove that w(vi,j ) ̸= w(vh,k) for every 1 ≤ i, h ≤ m and 1 ≤ j, k ≤ n where (i, j) ̸= (h, k). Note that max{w(vi,j} − min{w(vi+1,j} = −n ² − 2n − 6. Since n ≥ 3, then −n ² + 4n − 2 < 0, and so max{w(vi,j} − min{w(vi+1,j} < 0. This complete the proof.

Acknowledgment

R. Simanjuntak is supported by Riset Unggulan ITB 2022.

References

• [1] S. Arumugam and N. Kamatchi, On (a,d)-distance antimagic graphs, Australas. J. Combin. 54 (2012), 279–288.
• [2] N.J. Cutinho, S. Sudha, and S. Arumugam, Distance antimagic labelings of Cartesian product of graphs, AKCE Int. J. Graphs Comb. 17(2020), 940–942.
• [3] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Mathematicae 4 (1970).
• [4] A.K. Handa, A. Godinho and T. Singh, Some distance antimagic labeled graphs, CALDAM (2016).

• [5] A.K. Handa, A. Godinho, T. Singh, and S. Arumugam, Distance antimagic labeling of join and corona of two graphs, AKCE Int. J. Graphs Comb. 14 (2017). 172–177.
• [6] W. Imrich, R.H. Hammack and S.Klavzar, Handbook of Product Graphs, CRC Press, inc., (2011).
• [7] N. Kamatchi and S. Arumugam, Distance Antimagic Graphs, J. Combinat. Math. Combinat. Comput. 64 (2013), 61–67.
• [8] R. Simanjuntak and A. Tritama, Distance Antimagic Product Graphs, Symmetry 14 (7) (2022), 1411.
• [9] F. Susanto, K. Wijaya, I.W. Sudarsana and Slamin, Non-inclusive and inclusive distance irregularity strength for the join product of graphs, Electron. J. Graph Theory Appl. 10 (1) (2022), 1–13.
• [10] V. Vilfred, Sigma labelled graphs and circulant graphs, Ph.D. Thesis, University of Kerala, India (1994).40-942.