On distance labelings of 2-regular graphs

Anak Agung Gede Ngurah^a , Rinovia Simanjuntak^b

^aDepartment of Civil Engineering, Universitas Merdeka Malang Jalan Terusan Raya Dieng 62 – 64 Malang, Indonesia ^bCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia

aag.ngurah@unmer.ac.id, rino@math.itb.ac.id

Let G be a graph with |V (G)| vertices and ψ : V (G) −→ {1, 2, 3, · · · , |V (G)|} be a bijective function. The weight of a vertex v ∈ V (G) under ψ is wψ(v) = P ^u∈N(v) ψ(u). The function ψ is called a distance magic labeling of G, if wψ(v) is a constant for every v ∈ V (G). The function ψ is called an (a, d)-distance antimagic labeling of G, if the set of vertex weights is a, a + d, a + 2d, . . . , a + (|V (G)| − 1)d. A graph that admits a distance magic (resp. an (a, d) distance antimagic) labeling is called distance magic (resp. (a, d)-distance antimagic). In this paper, we characterize distance magic 2-regular graphs and (a, d)-distance antimagic some classes of 2-regular graphs.

Keywords: distance magic labeling, (a, d)-distance antimagic labeling, 2-regular graph

Mathematics Subject Classification: 05C78

DOI: 10.5614/ejgta.2021.9.1.3

1. Introduction

Let G = G(V, E) be a graph without isolated vertices. A vertex labeling of G is a one-to-one function with domain the set of all vertices and co-domain the set {1, 2, · · · , |V (G)|}. A vertex weight of a vertex v under a vertex labeling is the sum of all vertex labels of the vertices adjacent to v. If every vertex has the same vertex weights, then it is called a distance magic labeling of G. If all vertices have distinct vertex weights, then it is called a distance antimagic labeling of G. In particular, if vertex weights of all vertices are an arithmetic sequence with the first term a and a

Received: 15 June 2019, Revised: 23 April 2020, Accepted: 5 May 2020.

common difference d then it is called an (a, d)-distance antimagic labeling of G. Formally, these concepts can be stated as the following definitions.

Definition 1. A distance magic (DM) labeling of a graph G is a vertex labeling ψ of G such that |{wψ(v) = P ^u∈N(v) ψ(u) : v ∈ V (G)}| = 1, where N(v) = {u : uv ∈ E(G)}. A graph that admits a DM labeling is called a DM graph.

Definition 2. Let a > 0 and d ≥ 0 be fixed integers. An (a, d)-distance antimagic (DA) labeling of a graph G is a vertex labeling ψ of G such that {wψ(v) = P ^u∈N(v) ψ(u) : v ∈ V (G)} is the set {a, a + d, a + 2d, . . . , a + (|V (G)| − 1)d. Any graph which admits such a labeling is called an (a, d)-DA graph

The concept of a DM labeling of a graph independently was introduced by Vilfred [12] and Miller et al. [8]. Vilfred [12] called this labeling as a sigma labeling and Miller et al. [8] called it as an 1-vertex magic vertex labeling. The term a DM labeling for this concept introduced by Sugeng et al. [11]. Meanwhile, the notion of an (a, d)-DA labeling was introduced by Arumugam and Kamatchi [1], in 2012.

Several papers on DM labelings have been published. Many classes of graphs have been shown to be DM, see for instance [2, 8, 11, 12]. Additionally, a generalization of DM labeling to an any set D ⊆ {1, 2, . . . , diam(G)} is introduced in [9, 10]. Another generalization of DM labeling can be seen in [3]. Meanwhile, some results on DA labelings can be seen in, for instance, [1, 4, 5, 7]. For more results in these subjects, we refer the readers to Gallian's paper, dynamic survey of graph labelings [6]. In this paper, we study these labelings for 2-regular graphs.

2. DM labeling of 2-regular graphs

In [8], Miler et al. provided some necessary conditions for graphs to have no DM labeling. One of them is given in Lemma 2.1.

Lemma 2.1. [8] Let G be a graph and x, y ∈ V (G). If |N(x)∩N(y)| = |N(x)|−1 = |N(y)|−1, then G is not DM.

They also gave the following result.

Theorem 2.1. [8] The graph C^m has a DM labeling iff m = 4.

We now generalize this result as follows:

Theorem 2.2. The 2-regular graph G is a DM graph iff G = tC⁴ for any positive integer t.

Proof. Suppose G contains a component Cⁿ where n 6= 4. Then by Lemma 2.1, G is not DM. Conversely, define G = tC⁴ as a graph with V (G) = {xi,j : 1 ≤ i ≤ t, 1 ≤ j ≤ 4} and E(G) = {xi,jxi,j+1 : 1 ≤ i ≤ t, 1 ≤ j ≤ 3} ∪ {xi,4xi,¹ : 1 ≤ i ≤ t}. Next, Let A = {{xi,1, xi,3}, {xi,2, xi,4} : 1 ≤ i ≤ t} and B = {{i, 4t + 1 − i} : 1 ≤ i ≤ 2t}. It is clear that ∪ 2t ⁱ=1{i, 4t + 1 − i} is a partition of {1, 2, 3, . . . , 4t} and |A| = |B|. Also, it can be checked that any bijective function f : A −→ B is a DM labeling of G.

3. DA labeling of 2-regular graphs

In [1], Arumugam and Kamatchi proved the existence of an (a, d)-DA labeling for some graphs and they provided the following results.

Lemma 3.1. [1] If G is an (a, d)-DA graph with n vertices, then

\[d \le \frac{2n\Delta - \Delta(\Delta - 1) - \delta(\delta + 1)}{2(n - 1)}.\]

Corollary 3.1. [1] Let G be a 2-regular graph with n vertices. If G is (a, d)-DA, then a = n+3 2 and d = 1.

Theorem 3.1. [1] Let t ≥ 1 be an integer. The graph Cⁿ is (a, d)-DA iff n = 2t + 1 and d = 1.

They also posed the following problem.

Problem 1. [1] Find the necessary and sufficient conditions such that disconnected 2-regular graphs are (a, d)-DA.

In this section, we give a partial answer to Problem 1 by characterizing some classes of disconnected 2-regular (a, d)-DA graphs.

It is clear that if a graph has two vertices u and v such that N(u) = N(v), then it is not a DA graph. Thus, a forbidden subgraph for 2-regular graphs to be DA is C4. By this fact and Corollary 3.1, we have the following result.

Lemma 3.2. Let t > 1 be an integer and G = ∪ t ⁱ=1Cⁿⁱ . If G is (a, d)-DA, then P^{t i}=1 nⁱ is odd, nⁱ 6= 4 for 1 ≤ i ≤ t, and d = 1.

To present the next three theorems, we use the following 3 × (2t + 1) matrix A,

\[\mathbf{A} = [a_{i,j}] = \begin{bmatrix} 1 & 2 & \dots & t & t+1 & \dots & 2t & 2t+1 \\ t+2 & t+3 & \dots & 2t+1 & 1 & \dots & t & t+1 \\ 2t & 2t-2 & \dots & 2 & 2t+1 & \dots & 3 & 1 \end{bmatrix}.\]

We can check that {a1,i+a2,i : 1 ≤ i ≤ 2t+1} = {a1,i+a3,i : 1 ≤ i ≤ 2t+1} = {a2,i+a3,i : 1 ≤ i ≤ 2t + 1} = {t + 2, t + 3, . . . , 3t + 1, 3t + 2}. As we show later, this property of A preserves the antimagic properties of (a, d)-DA labelings of 2-regular graphs mCn. The matrix A is obtained by increasing 1 each entry of the following 3 × (2t + 1) Kotzig array.

\[\begin{bmatrix} 0 & 1 & \dots & t-1 & t & \dots & 2t-1 & 2t \\ t+1 & t+2 & \dots & 2t & 0 & \dots & t-1 & t \\ 2t-1 & 2t-3 & \dots & 1 & 2t & \dots & 2 & 0 \end{bmatrix}.\]

Additionally, we use the notation b+{aⁱ : 1 ≤ i ≤ t} = {b+aⁱ : 1 ≤ i ≤ t}. Also, in each figure, the numbers at the outside of the cycles are the labels of the vertices and the bold number inside of the cycles are the weights of the corresponding vertices.

The next theorem gives necessary and sufficient conditions of the disjoint union of odd numbers of Cⁿ to be an (a, d)-DA graph.

Theorem 3.2. Let m and n be positive integers. The graph mCⁿ is (a, d)-DA iff m, n are odd and d = 1.

Proof. Let mCⁿ be an (a, d)-DA graph. Then by Corollary 3.1, a = 1 2 (mn+ 3) and d = 1. Hence, m and n should be odd integers. Conversely, let m and n be odd integers. For 1 ≤ i ≤ m, define mCⁿ as a graph with

\[V(mC_n) = \{u_{i,j} : 1 \le j \le n\}\]

and

\[E(mC_n) = \{u_{i,j}u_{i,j+1} : 1 \le j \le n-1\} \cup \{u_{i,n}u_{i,1}\}.\]

Set m = 2t + 1 and, for 1 ≤ i ≤ 2t + 1, define a vertex labeling f of (2t + 1)Cⁿ as follows:

\[f(u_{i,j}) = \begin{cases} \frac{1}{4}(j-1)(2t+1) + a_{1,i}, & \text{if } j \equiv 1 \text{ (mod 4)}, \\ \frac{1}{4}(2n-1+j)(2t+1) + a_{2,i}, & \text{if } j \equiv 3 \text{ (mod 4)}, \\ \frac{1}{2}(n-1)(2t+1) + a_{3,i}, & \text{if } j = n-1, \\ \frac{1}{4}(n-1+j)(2t+1) + a_{1,i}, & \text{if } n \equiv 1 \text{ (mod 4) and } n-1 \neq j \equiv 0 \text{ (mod 4)}, \\ \frac{1}{4}(3n-1+j)(2t+1) + a_{2,i}, & \text{if } n \equiv 1 \text{ (mod 4) and } j \equiv 2 \text{ (mod 4)}, \\ \frac{1}{4}(3n-1+j)(2t+1) + a_{2,i}, & \text{if } n \equiv 3 \text{ (mod 4) and } j \equiv 0 \text{ (mod 4)}, \\ \frac{1}{4}(n-1+j)(2t+1) + a_{1,i}, & \text{if } n \equiv 3 \text{ (mod 4) and } n-1 \neq j \equiv 2 \text{ (mod 4)}. \end{cases}\]

The vertex weights of all vertices are as follows:

For n − 2, n 6= j ≡ 1, 3 (mod 4),

\[w_f(u_{i,j}) = \frac{1}{2}(2n - 1 + j)(2t + 1) + \mathfrak{F},\]

for j ≡ 0, 2 (mod 4),

\[w_f(u_{i,j}) = \frac{1}{2}(n-1+j)(2t+1) + \mathfrak{F},\]

for j = n − 2,

\[w_f(u_{i,j}) = \frac{1}{2}(3n-3)(2t+1) + \mathfrak{F},\] and

for j = n,

\[w_f(u_{i,j}) = \frac{1}{2}(n-1)(2t+1) + \mathfrak{F},\]

where F = {t + 2, t + 3, . . . , 3t + 2}. Thus, for 1 ≤ i ≤ 2t + 1, {w^f (ui,j ) : 1 ≤ j ≤ n} = { (2t+1)n+3 2 , (2t+1)n+5 2 . . . , 3(2t+1)n+1 2 }. So, f is an ( mn+3 2 , 1)-DA labeling of mCn.

Figure 1. shows the labeling in the proof of Theorem 3.2 for m = 3 and n = 11.

Theorem 3.3. The graph tC⁶ ∪ C³ is a (3t + 3, 1)-DA graph for every positive integer t.

Proof. First, define tC⁶ ∪ C³ as a graph with V (tC⁶ ∪ C3) = {xi,1, xi,2, xi,3, yi,1, yi,2, yi,³ : 1 ≤ i ≤ t} ∪ {z1, z2, z3} and E(tC⁶ ∪ C3) = {xi,1yi,1, xi,2yi,2, xi,3jyi,³ : 1 ≤ i ≤ t} ∪ {yi,1xi,2, xi,2yi,³ : 1 ≤ i ≤ t} ∪ {yi,3xi,¹ : 1 ≤ i ≤ t} ∪ {z1z2, z2z3, z3z1}.

Figure 1. A (18, 1)-DA labeling of 3C11.

Next, for 1 ≤ i ≤ t, consider g : V (tC⁶ ∪ C3) −→ {1, 2, 3, . . . , 6t + 3} which is defined by

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

where ai,j is the entry of the matrix A.

Clearly, f is a bijective function. We now can check that {wg(xi,1) : 1 ≤ i ≤ t} = {6t + 4, 6t + 5, 6t + 6, . . . , 7t + 3}, {wg(xi,2) : 1 ≤ i ≤ t} = {3t + 5, 3t + 7, 3t + 9, . . . , 5t + 3}, {wg(xi,3) : 1 ≤ i ≤ t} = {7t + 5, 7t + 6, 7t + 7, . . . , 8t + 4}, {wg(yi,1) : 1 ≤ i ≤ t} = {3t + 4, 3t + 6, 3t + 8, . . . , 5t + 2}, {wg(yi,2) : 1 ≤ i ≤ t} = {8t + 6, 8t + 7, 8t + 8, . . . , 9t + 5}, {wg(yi,3) : 1 ≤ i ≤ t} = {5t + 4, 5t + 5, 5t + 6, . . . , 6t + 3}, and {wg(z^j ) : 1 ≤ j ≤ 3} = {3t + 3, 7t + 4, 8t + 5}. Hence, g is a (3t + 3, 1)-DA labeling of tC⁶ ∪ C3.

Theorem 3.4. The graph tC¹⁰ ∪ C⁵ is a (5t + 4, 1)-DA graph for every positive integer t.

Proof. Let V (tC10∪C5) = {xi,1, xi,2, xi,2, xi,4, xi,5, yi,1, yi,2, yi,3, yi,4, yi,⁵ : 1 ≤ i ≤ t}∪{z1, z2, z3, z4, z5} and E(tC10∪C5) = {xi,1yi,1, xi,2yi,2, xi,3yi,3, xi,4yi,4, xi,5yi,⁵ : 1 ≤ i ≤ t}∪{yi,1xi,2, xi,2yi,3, xi,3yi,4, xi,4yi,⁵ : 1 ≤ i ≤ t} ∪ {yi,5xi,¹ : 1 ≤ i ≤ t} ∪ {z1z2, z2z3, z3z4, z4z5, z5z1}.

For 1 ≤ i ≤ t, define a bijective function h : V (tC¹⁰ ∪ C5) −→ {1, 2, 3, . . . , 10t + 5} as the following formula:

\[h(u) = \begin{cases} a_{1,i}, & \text{if } u = x_{i,1}, \\ 6t + 3 + a_{2,i}, & \text{if } u = x_{i,2}, \\ 2t + 1 + a_{1,i}, & \text{if } u = x_{i,3}, \\ 8t + 4 + a_{2,i}, & \text{if } u = x_{i,4}, \\ 4t + 2 + a_{3,i}, & \text{if } u = x_{i,5}, \\ a_{1,t+i}, & \text{if } u = y_{i,1}, \\ 6t + 3 + a_{2,t+i}, & \text{if } u = y_{i,2}, \\ 2t + 1 + a_{1,t+i}, & \text{if } u = y_{i,3}, \\ 8t + 4 + a_{2,t+i}, & \text{if } u = y_{i,4}, \\ 4t + 2 + a_{3,t+i}, & \text{if } u = x_{1,5}, \\ a_{1,2t+1}, & \text{if } u = x_{1,5}, \\ 4t + 2 + a_{3,2t+1}, & \text{if } u = x_{2,5}, \\ 2t + 1 + a_{1,2t+1}, & \text{if } u = x_{2,5}, \end{cases}\]

Notice that ai,j in this formula is the entry of the matrix A. Under the labeling h, we can verify that {wh(xi,1) : 1 ≤ i ≤ t} = {6t + 5, 6t + 6, . . . , 7t + 3, 7t + 4}, {wh(xi,2) : 1 ≤ i ≤ t} = {7t + 5, 7t + 7, . . . , 9t + 1, 9t + 3}, {wh(xi,3) : 1 ≤ i ≤ t} = {9t + 6, 9t + 8, . . . , 11t + 2, 11t + 4}, {wh(xi,4) : 1 ≤ i ≤ t} = {11t + 7, 11t + 9, . . . , 13t + 3, 13t + 5}, and {wh(xi,5) : 1 ≤ i ≤ t} = {13t + 9, 13t + 10, . . . , 14t + 7, 14t + 8}. Also, {wh(yi,1) : 1 ≤ i ≤ t} = {7t+ 6, 7t+ 8, . . . , 9t+ 2, 9t+ 4}, {wh(yi,2) : 1 ≤ i ≤ t} = {9t+ 7, 9t+ 9, . . . , 11t+ 3, 11t+ 5}, {wh(yi,3) : 1 ≤ i ≤ t} = {11t + 8, 11t + 10, . . . , 13t + 4, 13t + 6}, {wh(yi,4) : 1 ≤ i ≤ t} = {14t+9, 14t+10, . . . , 15t+7, 15t+8}, {wh(yi,5) : 1 ≤ i ≤ t} = {5t+4, 5t+5, . . . , 6t+2, 6t+3}, and {wh(z^j ) : 1 ≤ j ≤ 5} = {6t+4, 9t+5, 11t+6, 13t+7, 13t+8}. Hence, h is a (5t+4, 1)-DA labeling of tC¹⁰ ∪ C5.

In the next results, we characterize the graphs tC2ⁿ ∪ Cⁿ to be (a, d)-DA for 1 ≤ t ≤ 3.

Theorem 3.5. The graph C2ⁿ ∪ Cⁿ is (a, d)-DA iff n ≥ 3 is odd and d = 1.

Proof. By Corollary 3.1, if C2ⁿ ∪ Cⁿ is an (a, d)-DA graph then a = 3n+3 2 , d = 1 and thus n is odd. Conversely, we will show that C2ⁿ ∪ Cⁿ admits a ( 3n+3 2 , 1)-DA labeling. The graphs C⁶ ∪ C³ and C¹⁰ ∪ C⁵ admit the labeling by Theorems 3.3 and 3.4, respectively. For odd n ≥ 7, let V (C2ⁿ ∪ Cn) = {xⁱ , yⁱ , zⁱ : 1 ≤ i ≤ n} and E(C2ⁿ ∪ Cn) = {xiyⁱ : 1 ≤ i ≤ n} ∪ {yixi+1 : 1 ≤ i ≤ n − 1} ∪ {ynx1} ∪ {zizi+1 : 1 ≤ i ≤ n − 1} ∪ {znz1}. Next, define ψ : V (C2ⁿ ∪ Cn) −→ {1, 2, 3, . . . , 3n} as follows:

\[\psi(u) = \begin{cases} \frac{1}{2}(3i-1), & \text{if } u = x_i, \ n \neq i \equiv 1 \ (\text{mod } 2), \\ \frac{1}{2}(3n+1), & \text{if } u = x_i, \ i \equiv 0 \ (\text{mod } 2), \\ \frac{1}{2}(3i+1), & \text{if } u = y_i, \ n \neq i \equiv 1 \ (\text{mod } 2), \\ \frac{3}{2}(n+1), & \text{if } u = y_n, \\ \frac{1}{2}(3n-1+3i), & \text{if } u = y_i, \ i \equiv 0 \ (\text{mod } 2), \\ \frac{3}{4}(i+3), & \text{if } u = z_i, \ i \equiv 1 \ (\text{mod } 4), \\ \frac{1}{4}(6n+5+3i), & \text{if } u = z_i, \ i \equiv 3 \ (\text{mod } 4), \\ \frac{1}{2}(3n-1), & \text{if } u = z_n, \\ \frac{3}{4}(n+3+i), & \text{if } u = z_i, \ n \equiv 1 \ (\text{mod } 4) \ \text{and } n-1 \neq i \equiv 0 \ (\text{mod } 4), \\ \frac{1}{4}(9n+5+3i), & \text{if } u = z_i, \ n \equiv 1 \ (\text{mod } 4) \ \text{and } i \equiv 2 \ (\text{mod } 4), \\ \frac{1}{4}(9n+5+3i), & \text{if } u = z_i, \ n \equiv 3 \ (\text{mod } 4) \ \text{and } i \equiv 0 \ (\text{mod } 4), \\ \frac{3}{4}(n+3+i), & \text{if } u = z_i, \ n \equiv 3 \ (\text{mod } 4) \ \text{and } i \equiv 2 \ (\text{mod } 4). \end{cases}\]

The weights of all vertices are given by

\[w_{\psi}(u) = \begin{cases} \frac{1}{2}(3n+7), & \text{if } u = x_1, \\ \frac{1}{2}(3n-3+6i), & \text{if } u = x_i, \ 2 \leq i \leq n-1, \\ \frac{1}{2}(9n-1), & \text{if } u = x_n, \\ \frac{1}{2}(3n+5+6i), & \text{if } u = y_i, \ 1 \leq i \leq n-2, \\ \frac{1}{2}(9n+1), & \text{if } u = y_{n-1}, \\ \frac{1}{2}(3n+3), & \text{if } u = y_n, \\ \frac{1}{2}(3n+7+3i), & \text{if } u = z_i, \ i \text{ is even}, \\ \frac{1}{2}(6n+7+3i), & \text{if } u = z_i, \ n-2, n \neq i \text{ is odd}, \\ \frac{1}{2}(9n-3), & \text{if } u = z_{n-2}, \\ \frac{1}{2}(3n+5), & \text{if } u = z_n. \end{cases}\]

Thus, ψ is a ( 3n+3 2 , 1)-DA of C2ⁿ ∪ Cn.

Next, we consider the graph 2C2ⁿ ∪ Cⁿ with V (2C2ⁿ ∪ Cn) = {x1,j , x2,j , y1,j , y2,j : 1 ≤ j ≤ n}∪{z^j : 1 ≤ j ≤ n} and E(2C2n∪Cn) = {x1,jy1,j , x2,jy2,j : 1 ≤ j ≤ n}∪{y1,jx1,j+1, y2,jx2,j+1 : 1 ≤ j ≤ n − 1} ∪ {y1,nx1,1, y2,nx2,1} ∪ {zjzj+1 : 1 ≤ j ≤ n − 1} ∪ {znz1}. By Theorems 3.3 and 3.4, 2C2ⁿ ∪ Cⁿ is (a, 1)-DA for n = 3 and 5. So, it is enough to consider n ≥ 7.

Theorem 3.6. For n ≥ 7, the graph 2C2ⁿ ∪ Cⁿ is (a, d)-DA iff n is odd and d = 1.

Proof. By Corollary 3.1, n is odd and d = 1, if 2C2ⁿ ∪ Cⁿ is an (a, d)-DA graph. Conversely, for odd n ≥ 7 and i = 1, 2, define f : V (2C2ⁿ ∪ Cn) −→ {1, 2, 3, . . . , 5n} as follows:

\[f(u) = \begin{cases} \frac{1}{2}(5j - 7 + 4i), & \text{if } u = x_{i,j}, \ n \neq j \equiv 1 \ (\text{mod } 2), \\ \frac{1}{2}(5n + 1 + 2i), & \text{if } u = x_{i,n}, \\ \frac{1}{2}(5n + 5j + 9 - 6i), & \text{if } u = x_{i,j}, \ j \equiv 0 \ (\text{mod } 2), \\ \frac{1}{2}(5j - 5 + 4i), & \text{if } u = y_{i,j}, \ n \neq j \equiv 1 \ (\text{mod } 2), \\ \frac{1}{2}(5n - 3 + 2i), & \text{if } u = y_{i,n}, \\ \frac{1}{2}(5n + 5j + 11 - 6i), & \text{if } u = y_{i,j}, \ j \equiv 0 \ (\text{mod } 2). \end{cases}\]

\[f(z_j) = \begin{cases} \frac{1}{4}(5j+15), & \text{if } j \equiv 1 \text{ (mod 4)}, \\ \frac{1}{4}(10n+7+5j), & \text{if } j \equiv 3 \text{ (mod 4)}, \\ \frac{1}{2}(5n-3), & \text{if } j = n-1, \\ \frac{1}{4}(5n+15+5j), & \text{if } n \equiv 1 \text{ (mod 4) and } n-1 \neq j \equiv 0 \text{ (mod 4)}, \\ \frac{1}{4}(15n+7+5j), & \text{if } n \equiv 1 \text{ (mod 4) and } j \equiv 2 \text{ (mod 4)}, \\ \frac{1}{4}(15n+7+5j), & \text{if } n \equiv 3 \text{ (mod 4) and } j \equiv 0 \text{ (mod 4)}, \\ \frac{1}{4}(5n+15+5j), & \text{if } n \equiv 3 \text{ (mod 4) and } n-1 \neq j \equiv 2 \text{ (mod 4)}. \end{cases}\]

Clearly, f is a bijective function. Also it is easy to verify that the weights of all vertices are as follows:

\[w_f(u) = \begin{cases} \frac{1}{2}(5n+3), & \text{if } u = x_{1,1}, \\ \frac{1}{2}(5n-1+10j), & \text{if } u = y_{1,n-1}, \\ \frac{1}{2}(5n+5), & \text{if } u = y_{1,n}, \\ \frac{1}{2}(5n+5+10j), & \text{if } u = y_{1,j}, \ j \neq n-1, n, \\ \frac{1}{2}(5n+9), & \text{if } u = x_{2,1}, \\ \frac{1}{2}(5n-3), & \text{if } u = x_{2,n}, \\ \frac{1}{2}(5n-3), & \text{if } u = x_{2,j}, \ j \neq 1, n, \\ \frac{1}{2}(5n+11), & \text{if } u = y_{2,n-1}, \\ \frac{1}{2}(5n+3+10j), & \text{if } u = y_{2,n}, \\ \frac{1}{2}(5n+3), & \text{if } u = y_{2,n}, \\ \frac{1}{2}(5n+7), & \text{if } u = z_{n-2}, \\ \frac{1}{2}(5n+7), & \text{if } u = z_{n}, \\ \frac{1}{2}(10n+11+5j), & \text{if } u = z_{j}, \ n-2, n \neq j \equiv 1 \ (mod \ 2), \\ \frac{1}{2}(5n+11+5j), & \text{if } u = z_{j}, \ j \equiv 0 \ (mod \ 2). \end{cases}\]

Hence, f is a ( ⁵n+3 2 , 1)-DA labeling of 2C2ⁿ ∪ Cⁿ .

Figure 2. shows the labeling defined in the proof of Theorem 3.6 for n = 7.

Figure 2. A (19, 1)-DA labeling of 2C¹⁴ ∪ C7.

Now, we consider the graphs 3C2n∪Cn, n ≥ 7, where V (3C2n∪Cn) = {x1,j , x2,j , x3,j , y1,j , y2,j , y3,j : 1 ≤ j ≤ n} ∪ {z^j : 1 ≤ j ≤ n} and E(2C2ⁿ ∪ Cn) = {x1,jy1,j , x2,jy2,j , x3,jy3,j : 1 ≤ j ≤ n} ∪ {y1,jx1,j+1, y2,jx2,j+1, y3,jx3,j+1 : 1 ≤ j ≤ n − 1} ∪ {y1,nx1,1, y2,nx2,1, y3,nx3,1} ∪ {zjzj+1 : 1 ≤ j ≤ n − 1} ∪ {znz1}.

Theorem 3.7. For n ≥ 7, the graph 3C2ⁿ ∪ Cⁿ is (a, d)-DA iff n is odd and d = 1.

Proof. From Corollary 3.1, if 3C2n∪Cⁿ is an (a, d)-DA graph then n is odd and d = 1, Conversely, for odd n ≥ 7 and i = 1, 2, 3, define g : V (3C2ⁿ ∪ Cn) −→ {1, 2, 3, . . . , 7n} as follows:

\[g(u) = \begin{cases} \frac{1}{2}(7j - 7 + 2i), & \text{if } u = x_{i,j}, \ n \neq j \equiv 1 \ (\text{mod } 2), \\ \frac{1}{2}(7n + 9 - 4i), & \text{if } u = x_{i,n}, \\ \frac{1}{2}(7n + 7j + 1 + 2i), & \text{if } u = x_{i,j}, \ j \equiv 0 \ (\text{mod } 2), \\ \frac{1}{2}(7j + 1 + 2i), & \text{if } u = y_{i,j}, \ n \neq j \equiv 1 \ (\text{mod } 2), \\ \frac{1}{2}(7n + 7 - 4i), & \text{if } u = y_{i,n}, \\ \frac{1}{2}(7n + 7j - 5 + 2i), & \text{if } u = y_{i,j}, \ j \equiv 0 \ (\text{mod } 2). \end{cases}\]

\[g(z_j) = \begin{cases} \frac{1}{4}(7j+9), & \text{if } j \equiv 1 \text{ (mod 4)}, \\ \frac{1}{4}(14n-3+7j), & \text{if } j \equiv 3 \text{ (mod 4)}, \\ \frac{1}{2}(7n+7), & \text{if } j = n-1, \\ \frac{1}{4}(7n+9+7j), & \text{if } n \equiv 1 \text{ (mod 4) and } n-1 \neq j \equiv 0 \text{ (mod 4)}, \\ \frac{1}{4}(21n-3+7j), & \text{if } n \equiv 1 \text{ (mod 4) and } j \equiv 2 \text{ (mod 4)}, \\ \frac{1}{4}(21n-3+7j), & \text{if } n \equiv 3 \text{ (mod 4) and } j \equiv 0 \text{ (mod 4)}, \\ \frac{1}{4}(7n+9+7j), & \text{if } n \equiv 3 \text{ (mod 4) and } n-1 \neq j \equiv 2 \text{ (mod 4)}. \end{cases}\]

Clearly, g is a bijective function. Also it is easy to verify that, for i = 1, 2, 3,

\[w_g(u) = \begin{cases} \frac{1}{2}(7n+15-2i), & \text{if } u = x_{i,1}, \\ \frac{1}{2}(21n-5-2i), & \text{if } u = x_{i,n}, \\ \frac{1}{2}(7n+14j-11+4i), & \text{if } u = x_{i,j}, \ j \neq 1, n, \\ \frac{1}{2}(7n+9-2i), & \text{if } u = y_{i,n}, \\ \frac{1}{2}(21n+3-2i), & \text{if } u = y_{i,n-1}, \\ \frac{1}{2}(7n+14j+1+4i), & \text{if } u = y_{i,j}, \ j \neq n-1, n, \\ \frac{1}{2}(21n-5), & \text{if } u = z_{n-2}, \\ \frac{1}{2}(7n+15), & \text{if } u = z_n, \\ \frac{1}{2}(14n+3+7j), & \text{if } u = z_j, \ n-2, n \neq j \equiv 1 \ (mod \ 2), \\ \frac{1}{2}(7n+3+7j), & \text{if } u = z_j, \ j \equiv 0 \ (mod \ 2). \end{cases}\]

Hence, g is a ( ⁷n+3 2 , 1)-DA labeling of 3C2ⁿ ∪ Cn.

Based on Theorems 3.3 – 3.7, we propose the following conjecture:

Conjecture 1. For every positive integer t, the graph tC2ⁿ ∪ Cⁿ is (a, d)-DA if and only if n is odd and d = 1.

Next, we consider two classes of 2-regular graphs with two components.

Theorem 3.8. For \(n \geq 7\), the graph \(C_6 \cup C_n\) is (a, d)-DA iff n is odd and d = 1.

Proof. As an immediate consequence of Corollary 3.1, if \(C_6 \cup C_n\) is an (a,d)-DA graph then n is odd and d=1. Next, for odd \(n \geq 7\), let \(V(C_6 \cup C_n) = \{u_1, u_2, u_3, u_4, u_5, u_6\} \cup \{v_j : 1 \leq j \leq n\}\) and \(E(C_6 \cup C_n) = \{u_1u_2, u_2u_3, u_3u_4, u_4u_5, u_5u_6, u_6u_1\} \cup \{v_jv_{j+1} : 1 \leq j \leq n-1\} \cup \{v_nv_1\}\). Define \(h: V(C_6 \cup C_n) \longrightarrow \{1, 2, 3, \dots, n+6\}\) as follows: Case \(n \equiv 1 \pmod{4}\)

\(h([u_1, u_2, u_3, u_4, u_5, u_6]) = [\frac{n-1}{2}, \frac{3n+17}{4}, \frac{n+3}{2}, \frac{3n+21}{4}, \frac{n+5}{2}, \frac{3n+13}{4}].\)

\[h(v_j) = \begin{cases} \frac{1}{4}(j+3), & \text{if } n-4, n \neq j \equiv 1 \text{ (mod 4)}, \\ \frac{1}{4}(3n+9), & \text{if } j = n-4, \\ \frac{1}{4}(2n+11+j), & \text{if } n-2 \neq j \equiv 3 \text{ (mod 4)}, \\ \frac{1}{4}(n+3), & \text{if } j = n-2. \end{cases}\]

Sub case \(n \equiv 1 \pmod{8}\)

If n = 9, \(h([v_1, v_2, v_3, \dots, v_9]) = [1, 15, 13, 3, 2, 9, 14, 8, 5]\). If \(n \ge 17\),

\[h(v_j) = \begin{cases} \frac{1}{4}(n-3+j), & \text{if } n-7 \neq j \equiv 2 \text{ (mod 8)}, \\ \frac{1}{2}(n+1), & \text{if } j=n-7, \\ \frac{1}{4}(3n+21+j), & \text{if } n-5 \neq j \equiv 4 \text{ (mod 8)}, \\ n+5, & \text{if } j=n-5, \\ \frac{1}{4}(n+5+j), & \text{if } n-3 \neq j \equiv 6 \text{ (mod 8)}, \\ \frac{1}{2}(n-5), & \text{if } j=n-3, \\ \frac{1}{4}(3n+29+j), & \text{if } n-9, n-1 \neq j \equiv 0 \text{ (mod 8)}, \\ n+6, & \text{if } j=n-9, \\ n+4, & \text{if } j=n-1, \\ \frac{1}{4}(3n+29), & \text{if } j=n. \end{cases}\]

Sub case \(n \equiv 5 \pmod{8}\)

\[h(v_j) = \begin{cases} \frac{1}{4}(n-3+j), & \text{if } j \equiv 2 \text{ (mod 8)}, \\ \frac{1}{4}(3n+29+j), & \text{if } n-1 \neq j \equiv 4 \text{ (mod 8)}, \\ n+4, & \text{if } j=n-1, \\ \frac{1}{4}(n+5+j), & \text{if } n-7 \neq j \equiv 6 \text{ (mod 8)}, \\ \frac{1}{2}(n+1), & \text{if } j=n-7, \\ \frac{1}{4}(3n+21+j), & \text{if } n-5 \neq j \equiv 0 \text{ (mod 8)}, \\ n+6, & \text{if } j=n-5, \\ \frac{1}{4}(3n+25), & \text{if } j=n. \end{cases}\]

It can be checked that h is a bijective function. When n=9, \(\{w_h(u_i): 1 \le j \le 6\} = \{10,11,13,21,22,23\}\) and \(\{w_h(v_j): 1 \le j \le 9\} = \{9,12,14,15,16,17,18,19,20\}\). When \(n \ne 9\), \(w_h(v_2) = \frac{n+9}{2}\), \(w_h(u_3) = \frac{3n+19}{2}\), and the weights of other vertices are consecutive integers from \(\frac{n+11}{2}\) to \(\frac{3n+17}{2}\).

Case \(n \equiv 3 \pmod{4}\)

\[h([u_1, u_2, u_3, u_4, u_5, u_6]) = [\frac{n+1}{2}, \frac{3n+11}{4}, \frac{n+3}{2}, \frac{3n+15}{4}, \frac{n+5}{2}, \frac{3n+19}{4}].\]

\[h(v_j) = \begin{cases} \frac{1}{4}(j+3), & \text{if } j \equiv 1 \pmod{4}, \\ \frac{1}{4}(2n+15+j), & \text{if } n-4, n \neq j \equiv 3 \pmod{4}, \\ \frac{1}{4}(3n+23), & \text{if } j = n-4, \\ \frac{1}{4}(3n+27), & \text{if } j = n, \\ \frac{1}{4}(n+3+j), & \text{if } n-1 \neq j \equiv 2 \pmod{4}, \\ \frac{1}{2}(n+7), & \text{if } j = n-1, \\ \frac{1}{4}(3n+27+j), & \text{if } j \equiv 0 \pmod{4}. \end{cases}\]

It can be checked that h is a bijective function, \(w_h(v_n) = \frac{n+9}{2}\), \(w_h(v_{n-2}) = \frac{3n+19}{2}\), and the weights of the remaining vertices are consecutive integers from \(\frac{n+11}{2}\) to \(\frac{3n+17}{2}\).

Theorem 3.9. For \(n \geq 5\), the graph \(C_8 \cup C_n\) is (a, d)-DA iff n is odd and d = 1.

Proof. As a direct consequence of Corollary 3.1, if \(C_8 \cup C_n\) is (a,d)-DA then n is odd and d=1. Conversely, For odd \(n \geq 5\), let \(V(C_8 \cup C_n) = \{u_i : 1 \leq i \leq 8\} \cup \{v_j : 1 \leq j \leq n\}\) and \(E(C_8 \cup C_n) = \{u_i u_{i+1} : 1 \leq i \leq 7\} \cup \{u_8 u_1\} \cup \{v_j v_{j+1} : 1 \leq j \leq n-1\} \cup \{v_n v_1\}\). Define \(f: V(C_8 \cup C_n) \longrightarrow \{1, 2, 3, \ldots, n+8\}\) as follows:

\[f([u_1, u_2, u_3, u_4, u_5, u_6, u_7, u_8]) = [1, 3, \frac{n+9}{2}, \frac{n+15}{2}, 2, 5, \frac{n+13}{2}, \frac{n+17}{2}].\]

Case \(n \equiv 1 \pmod{4}\)

When n = 5, \(f([v_1, v_2, v_3, v_4, v_5]) = [4, 6, 8, 13, 12]\). When \(n \ge 9\) define f as the following formula:

\[f(v_j) = \begin{cases} 4, & \text{if } j = 1, \\ \frac{1}{4}(4n + 41 - j), & \text{if } 1 < j \equiv 1 \text{ (mod 8)}, \\ \frac{1}{2}(n + 11), & \text{if } j = 3, \\ \frac{1}{4}(2n + 17 - j), & \text{if } 3 < j \equiv 3 \text{ (mod 8)}, \\ \frac{1}{4}(4n + 33 - j), & \text{if } j \equiv 5 \text{ (mod 8)}, \\ \frac{1}{2}(n + 7), & \text{if } j = 7, \\ \frac{1}{4}(2n + 25 - j), & \text{if } n \equiv 1 \text{ (mod 8) and } j \equiv 2 \text{ (mod 8)}, \\ \frac{1}{4}(3n + 33 - j), & \text{if } n \equiv 1 \text{ (mod 8) and } j \equiv 4 \text{ (mod 8)}, \\ \frac{1}{4}(n + 25 - j), & \text{if } n \equiv 1 \text{ (mod 8) and } j \equiv 6 \text{ (mod 8)}, \\ \frac{1}{4}(3n + 41 - j), & \text{if } n \equiv 1 \text{ (mod 8) and } j \equiv 6 \text{ (mod 8)}, \\ \frac{1}{4}(n + 25 - j), & \text{if } n \equiv 5 \text{ (mod 8) and } j \equiv 2 \text{ (mod 8)}, \\ \frac{1}{4}(n + 25 - j), & \text{if } n \equiv 5 \text{ (mod 8) and } j \equiv 4 \text{ (mod 8)}, \\ \frac{1}{4}(3n + 41 - j), & \text{if } n \equiv 5 \text{ (mod 8) and } j \equiv 6 \text{ (mod 8)}, \\ \frac{1}{4}(3n + 33 - j), & \text{if } n \equiv 5 \text{ (mod 8) and } j \equiv 6 \text{ (mod 8)}, \\ \frac{1}{4}(3n + 33 - j), & \text{if } n \equiv 5 \text{ (mod 8) and } j \equiv 6 \text{ (mod 8)}. \end{cases}\]

Case \(n \equiv 3 \pmod{4}\)

When n = 7, \(f([v_1, v_2, v_3, v_4, v_5, v_6, v_7]) = [4, 13, 15, 9, 6, 14, 7]\). When \(n \ge 11\),

f(v_j) = \begin{cases} 4, & \text{if } j = 1, \\ \frac{1}{2}(n+14-j), & \text{if } j = 3,7,11,, \\ n+7, & \text{if } j = 5, \\ n+8, & \text{if } j = 9, \\ n+6, & \text{if } j = 13, \\ \frac{1}{4}(4n+33-j), & \text{if } 17 \leq j \equiv 1 \pmod{8}, \\ \frac{1}{4}(4n+41-j), & \text{if } 21 \leq j \equiv 5 \pmod{8}, \\ 6, & \text{if } j = n-3, \\ \frac{1}{4}(2n+17-j), & \text{if } n \equiv 3 \pmod{8} \text{ and } 19 \leq j \equiv 3 \pmod{8}, \\ \frac{1}{4}(n+20-j), & \text{if } n \equiv 3 \pmod{8} \text{ and } 15 \leq j \equiv 7 \pmod{8}, \\ \frac{1}{4}(n+25-j), & \text{if } n \equiv 3 \pmod{8} \text{ and } j \equiv 2 \pmod{8}, \\ \frac{1}{4}(n+25-j), & \text{if } n \equiv 3 \pmod{8} \text{ and } j \equiv 6 \pmod{8}, \\ \frac{1}{4}(n+17-j), & \text{if } n \equiv 3 \pmod{8} \text{ and } j \equiv 6 \pmod{8}, \\ \frac{1}{4}(2n+41-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } 19 \leq j \equiv 3 \pmod{8}, \\ \frac{1}{4}(2n+25-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } 15 \leq j \equiv 7 \pmod{8}, \\ \frac{1}{4}(3n+33-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } 15 \leq j \equiv 7 \pmod{8}, \\ \frac{1}{4}(3n+33-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } j \equiv 2 \pmod{8}, \\ \frac{1}{4}(n+17-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } j \equiv 2 \pmod{8}, \\ \frac{1}{4}(n+17-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } j \equiv 6 \pmod{8}, \\ \frac{1}{4}(n+25-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } j \equiv 6 \pmod{8}, \\ \frac{1}{4}(n+25-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } j \equiv 6 \pmod{8}, \\ \frac{1}{4}(n+25-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } j \equiv 6 \pmod{8}, \\ \frac{1}{4}(n+25-j), & \text{if } n \equiv 7 \pmod{8} \text{ and } j \equiv 0 \pmod{8}. \end{cases}

Clearly, f is a bijective function. When n=5 and 7, \(\{w_f(x):x\in V(C_8\cup C_n)\}\) is \(\{8,9,10,\ldots,20\}\) and \(\{9,10,11,\ldots,23\}\), respectively. When \(n\geq 9\), it can be checked that the weights of all vertices are consecutive integers with the first term \(w_f(u_2)=\frac{n+11}{2}\) and the last term \(w_f(v_4)=\frac{3n+25}{2}\).

Figure 3. shows the labeling defined in the proof of Theorem 3.9 for n = 15.

Figure 3. A (13, 1)-DA labeling of \(C_8 \cup C_{15}\).

Based on Theorems 3.8 and 3.9, we have the following conjecture:

Conjecture 2. Let \(k, n \ge 5\) be positive integers. The graph \(C_{2k} \cup C_n\) is (a, d)-DA if and only if n is odd and d = 1.

Acknowledgement

The authors would like to thank the referee for his/her valuable comments.

The first author has been supported by "Penelitian Dasar 2019" from the Directorate General of Higher Education, Indonesia.

References

• [1] S. Arumugam and N. Kamatchi, On (a, d)-distance antimagic graphs, Australas. J. Combin. 54 (2012), 279–287.
• [2] S. Beena, On P and P⁰ labelled graphs, Discrete Math. 309 (2009), 1783–1787.
• [3] B. Freyberg and M. Keranen, Orientable Zn-distance magic labeling of the Cartesian product of many cycles, Electron. J. Graph Theory Appl. 5 (2) (2017), 304–311.
• [4] D. Froncek, Handicap distance antimagic graphs and incomplete tournaments, AKCE Int. J. Graphs Combin., 10 (2013), 119 – 127.
• [5] D. Froncek and A. Shepanik, Regular handicap graphs of order n ≡ 0 (mod 8), Electron. J. Graph Theory Appl. 6 (2) (2018), 208–218.
• [6] J. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2019), #DS6.
• [7] A.K. Handa, A. Godinho, and T. Singh, Distance antimagic labeling of the ladder graph, Electron. Notes Discrete Math., 63 (2017), 317–322.
• [8] M. Miller, C. Rodger and R. Simanjuntak, Distance magic labelings of graphs, Australas. J. Combin., 28 (2003), 305–315.
• [9] A. O'Neal and P. Slater, An introduction to distance D-magic graphs, J. Indones. Math. Soc., Special Edition (2011), 89–107.
• [10] A. O'Neal and P. Slater, Uniqueness of vertex magic constants, SIAM J. Discrete Math., 27 (2013), 708–716.
• [11] K.A. Sugeng, D. Froncek, M. Miller, J. Ryan, and J. Walker, On distance magic labeling of graphs, J. Combin. Math. Combin. Comput. 71 (2009), 39 – 48.
• [12] V. Vilfred, P-labelled graph and circulant graphs, Ph.D. Thesis, University of Kerala, Trivandrum, India, 1994.