Electronic Journal of Graph Theory and Applications

Martin Bača^a, Ljiljana Brankovic^b, Marcela Lascsáková^a, Oudone Phanalasy^c, Andrea Semaničová–Feňovčíková^a

martin.baca@tuke.sk, ljiljana.brankovic@newcastle.edu.au, marcela.lascsakova@tuke.sk, oudone.phanalasy@newcastle.edu.au, andrea.fenovcikova@tuke.sk

The paper deals with the problem of labeling the vertices and edges of a plane graph in such a way that the labels of the vertices and edges surrounding that face add up to a weight of that face. A labeling of a plane graph is called d-antimagic if for every positive integer s, the s-sided face weights form an arithmetic progression with a difference d. Such a labeling is called super if the smallest possible labels appear on the vertices.

In the paper we examine the existence of such labelings for several families of plane graphs.

Keywords: plane graph, d-antimagic labeling, super d-antimagic labeling Mathematics Subject Classification: 05C78

1. Introduction

Let G=(V,E,F) be a finite connected plane graph without loops and multiple edges, where V, E and F are its vertex set, edge set and face set, respectively. Let |V(G)|=p, |E(G)|=q and |F(G)|=r be the number of the vertices, the edges and the faces, respectively.

A labeling of type (1, 1, 1) assigns labels from the set \(\{1, 2, \dots, p+q+r\}\) to the vertices, edges and faces of a plane graph G in such a way that each vertex, edge and face receives exactly one label and each number is used exactly once as a label.

Received: 31 March 2011, Revised: 28 July 2011, Accepted: 21 November 2012.

^&lt;sup>a</sup>Department of Applied Mathematics and Informatics, Technical University, Košice, Slovak Republic

^&lt;sup>b</sup>School of Electrical Engineering and Computer Science, The University of Newcatle, Australia

^&lt;sup>c</sup>Department of Mathematics, National University of Laos, Vientiane, Laos

A labeling of type (1, 1, 0) is a bijection from the set {1, 2, . . . , p + q} to the vertices and edges of a graph G.

The weight of a face under a labeling is the sum of labels (if present) carried by that face and the edges and vertices on its boundary.

A labeling of a plane graph G is called d-antimagic if for every positive integer s the set of s-sided face weights is W^s = {as, a^s + d, a^s + 2d, . . . , a^s + (r^s − 1)d} for some integers a^s and d ≥ 0, where r^s is the number of s-sided faces. We allow different sets W^s for different s.

If d = 0 then Ko-Wei Lih in [16] called such labeling magic. Ko-Wei Lih [16] described magic (0-antimagic) labelings of type (1, 1, 0) for the wheels, the friendship graphs and the prisms. The magic labelings of type (1, 1, 1) for the grid graphs and the honeycomb are given in [2] and [3], respectively.

The concept of the d-antimagic labeling of the plane graphs was defined in [10], where it was also proved that the prism Dⁿ has d-antimagic labelings of type (1, 1, 1) for d ∈ {2, 3, 4, 6} and n ≡ 3 (mod 4). The d-antimagic labelings of type (1, 1, 1) for the hexagonal planar maps, the generalized Petersen graph P(n, 2) and the grids can be found in [5], [7] and [8], respectively. Lin et al. in [17] showed that prism Dn, n ≥ 3, admits d-antimagic labelings of type (1, 1, 1) for d ∈ {2, 4, 5, 6}. The d-antimagic labelings of type (1, 1, 1) for Dⁿ and for several d ≥ 7 are described in [19].

A d-antimagic labeling is called super if the smallest possible labels appear on the vertices. The super d-antimagic labelings of type (1, 1, 1) for antiprisms and for d ∈ {0, 1, 2, 3, 4, 5, 6} are described in [4], and for disjoint union of prisms and for d ∈ {0, 1, 2, 3, 4, 5} are given in [1]. The existence of super d-antimagic labelings of type (1, 1, 1) for disconnected plane graphs and for plane graphs containing a special Hamilton path is examined in [6] and [12], respectively.

In this paper we examine the existence of super d-antimagic labelings of type (1, 1, 0) for several families of plane graphs. To label the vertices and edges of plane graphs we will use an edge-antimagic vertex labeling and an edge-antimagic total labeling.

Simanjuntak, Bertault and Miller in [18] define an (a, d)-edge-antimagic vertex labeling of a (p, q)-graph G = (V, E) as an injective mapping β : V (G) → {1, 2, . . . , p} such that the set of edge-weights {β(u) + β(v) : uv ∈ E(G)} is {a, a + d, a + 2d, . . . , a + (q − 1)d} for two non-negative integers a and d. A bijection α : V (G)∪E(G) → {1, 2, . . . , p+q} is called an (a, d) edge-antimagic total labeling of G if the edge-weights {α(u) + α(uv) + α(v) : uv ∈ E(G)} form an arithmetic sequence starting at a and having a common difference d, where a > 0 and d ≥ 0 are two fixed integers. An (a, d)-edge-antimagic total labeling is a natural extension of a notion of magic valuation defined by Kotzig and Rosa in [15].

An (a, d)-edge-antimagic total labeling is called super if the smallest possible labels appear on the vertices. A super (a, d)-edge-antimagic total labeling is a natural extension of a notion of super edge-magic labeling defined by Enomoto et al. in [13].

More comprehensive information on magic valuations and (a, d)-edge-antimagic total labelings can be found in [11], [14] and [20], respectively.

2. Edge-antimagic labelings of paths

Let Pⁿ be the path on n vertices. It is known (see [9]), that Pⁿ is super (a, d)-edge-antimagic total if and only if d ≤ 3. We denote the vertices of Pⁿ by v1, v2, . . . , vⁿ and describe these labelings α n d : V (Pn) ∪ E(Pn) → {1, 2, . . . , 2n − 1} in the following way.

a) The super (2n + d n 2 e + 1, 0)-edge-antimagic total labeling α n ⁰ of Pn:

\[\alpha_0^n(v_i) = \begin{cases} \frac{i+1}{2} & \text{for } i \equiv 1 \pmod{2} \text{ and } 1 \leq i \leq n, \\ \lceil \frac{n}{2} \rceil + \frac{i}{2} & \text{for } i \equiv 0 \pmod{2} \text{ and } 2 \leq i \leq n, \end{cases}\] \[\alpha_0^n(v_i v_{i+1}) = 2n - i & \text{for } i = 1, 2, \dots, n-1.\]

The common weight for all edges of Pⁿ is

\[w_{\alpha_0^n}(v_i v_{i+1}) = 2n + \left\lceil \frac{n}{2} \right\rceil + 1 = C_{\alpha,0}^n, \ i = 1, 2, \dots, n-1.\]

b) The super (2n + 2, 1)-edge-antimagic total labeling α n ¹ of Pn:

\[\alpha_1^n(v_i) = i\] for \(i = 1, 2, ..., n,\)
\(\alpha_1^n(v_i v_{i+1}) = 2n - i\) for \(i = 1, 2, ..., n - 1.\)

The set of edge-weights of Pⁿ consists of the consecutive integers

\[\{w_{\alpha_1^n}(v_iv_{i+1})=2n+1+i=C_{\alpha,1}^n+i:i=1,2,\ldots,n-1\}.\]

c) The super (n + d n 2 e + 3, 2)-edge-antimagic total labeling α n ² of Pn:

\[\alpha_2^n(v_i) = \begin{cases} \frac{i+1}{2} & \text{for } i \equiv 1 \pmod{2}, \\ \lceil \frac{n}{2} \rceil + \frac{i}{2} & \text{for } i \equiv 0 \pmod{2}, \end{cases}\]
\[\alpha_2^n(v_i v_{i+1}) = n + i & \text{for } i = 1, 2, \dots, n - 1.\]

The edge-weights of Pⁿ constitute the arithmetic progression of difference 2:

\[\{w_{\alpha_2^n}(v_iv_{i+1}) = n + \left\lceil \frac{n}{2} \right\rceil + 1 + 2i = C_{\alpha,2}^n + 2i : i = 1, 2, \dots, n-1\}.\]

d) The super (n + 4, 3)-edge-antimagic total labeling α n ³ of Pn:

\[\alpha_3^n(v_i) = i\] for \(i = 1, 2, ..., n,\)
\(\alpha_3^n(v_i v_{i+1}) = n + i\) for \(i = 1, 2, ..., n - 1.\)

The edge-weights of Pⁿ constitute the arithmetic progression of difference 3:

\[\{w_{\alpha_3^n}(v_iv_{i+1}) = n+1+3i = C_{\alpha,3}^n+3i : i=1,2,\ldots,n-1\}.\]

Now, we define the super (a, d)-edge-antimagic total labelings of Pⁿ also for negative differences d in the following way

\[\alpha_{-k}^{n}(v_i) = \alpha_k^{n}(v_{n+1-i})\] for \(i = 1, 2, ..., n,\)
\[\alpha_{-k}^{n}(v_i v_{i+1}) = \alpha_k^{n}(v_{n+1-i} v_{n-i})\] for \(i = 1, 2, ..., n-1,\)

where k = 0, 1, 2, 3.

In this paper we will use also (a, d)-edge-antimagic vertex labelings of Pⁿ for two differences d = 1 and d = 2. These labelings β n d : V (Pn) → {1, 2, . . . , n} we define in the following way:

e) The (d n 2 e + 2, 1)-edge-antimagic vertex labeling β n ¹ of Pn:

\[\beta_1^n(v_i) = \begin{cases} \frac{i+1}{2} & \text{for } i \equiv 1 \pmod{2}, \\ \lceil \frac{n}{2} \rceil + \frac{i}{2} & \text{for } i \equiv 0 \pmod{2}. \end{cases}\]

The set of edge-weights of Pⁿ consists of the consecutive integers

\[\{w_{\beta_1^n}(v_iv_{i+1}) = \lceil \frac{n}{2} \rceil + 1 + i = C_{\beta,1}^n + i : i = 1, 2, \dots, n-1\}.\]

f) The (3, 2)-edge-antimagic vertex labeling β n ² of Pn:

\[\beta_2^n(v_i) = i\] for \(i = 1, 2, ..., n\).

The edge-weights of Pⁿ constitute the arithmetic progression of difference 2:

\[\{w_{\beta_2^n}(v_iv_{i+1}) = 1 + 2i = C_{\beta,2}^n + 2i : i = 1, 2, \dots, n-1\}.\]

The (a, d)-edge-antimagic vertex labelings of Pⁿ for d negative we define as follows

\[\beta_{-l}^{n}(v_i) = \beta_{l}^{n}(v_{n+1-i})\] for \(i = 1, 2, ..., n\),

where l = 1, 2.

3. Partitions with determined differences

For construction of vertex and edge labelings of plane graphs we will use the partitions of a set of integers with determined differences.

Let n, k, d and i be positive integers. We will consider the partition P n k,d of the set {1, 2, . . . , kn} into n, n ≥ 2, k-tuples such that the difference between the sum of the numbers in the (i+1)th k-tuple and the sum of the numbers in the ith k-tuple is always equal to the constant d, where i = 1, 2, . . . , n − 1. Thus they form an arithmetic sequence with the difference d. By the symbol Pk,d(i) we denote the ith k-tuple in the partition with the difference d, where i = 1, 2, . . . , n.

Let PP n k,d(i) be the sum of the numbers in P n k,d(i). Evidently PP n k,d(i+ 1)− PP n k,d(i) = d. It is obvious that if there exists a partition of the set {1, 2, . . . , kn} with the difference d, there also

exists a partition with the difference -d. By the notation \(\mathcal{P}_{k,d}^n(i) \oplus c\) we mean that we add the constant c to every number in \(\mathcal{P}_{k,d}^n(i)\).

If k = 1 then only the following partition of the set \(\{1, 2, \dots, n\}\) is possible

\[\mathcal{P}_{1,1}^n(i) = \{i\} \text{ for } i = 1, 2, \dots, n.\]

If k=2 then we have several partitions of the set \(\{1,2,\ldots,2n\}\). Let us define the partitions into 2-tuples in the following way:

\[\mathcal{P}_{2,0}^{n}(i) = \{i, 2n+1-i\},\\] \[\sum \mathcal{P}_{2,0}^{n}(i) = 2n+1,\] for \(i = 1, 2, ..., n\). \[\mathcal{P}_{2,2}^{n}(i) = \{i, n+i\},\] \[\sum \mathcal{P}_{2,2}^{n}(i) = n+2i,\] for \(i = 1, 2, ..., n\). \[\mathcal{P}_{2,4}^{n}(i) = \{2i-1, 2i\},\] \[\sum \mathcal{P}_{2,4}^{n}(i) = 4i-1,\] for \(i = 1, 2, ..., n\).

Moreover, for \(3 \le n \equiv 1 \pmod{2}\)

\[\mathcal{P}^n_{2,1}(i) = \begin{cases} \left\{ \frac{n+1}{2} + \frac{i-1}{2}, n+1 + \frac{i-1}{2} \right\} & \text{for } i \equiv 1 \pmod{2}, \\ \left\{ \frac{i}{2}, n + \frac{n+1}{2} + \frac{i}{2} \right\} & \text{for } i \equiv 0 \pmod{2}, \end{cases}\]\[\sum \mathcal{P}^n_{2,1}(i) = n + \frac{n+1}{2} + i, & \text{for } i = 1, 2, \dots, n.\]

Note that we are also able to obtain the partitions into 2-tuples \(\mathcal{P}^n_{2,0}(i)\) and \(\mathcal{P}^n_{2,2}(i)\) as \(\mathcal{P}^n_{1,s}(i) \cup (\mathcal{P}^n_{1,t}(i) \oplus n)\), where \(s,t=\pm 1\). We can use this idea to construct the other partitions. More precisely,

\[\mathcal{P}_{k,d}^n(i) = \mathcal{P}_{l,s}^n(i) \cup (\mathcal{P}_{m,t}^n(i) \oplus ln),\]

where k = l + m.

For example, we are able to obtain \(\mathcal{P}^n_{3,d}(i)\) from the partitions \(\mathcal{P}^n_{1,s}(i)\), \(s=\pm 1\) and \(\mathcal{P}^n_{2,t}(i)\), \(t=0,\pm 2,\pm 4\) and also \(t=\pm 1\) for n odd. It means, \(\mathcal{P}^n_{3,d}\) exists for \(d=\pm 1,\pm 3,\pm 5\) and if \(n\equiv 1\pmod 2\) also for \(d=0,\pm 2\). Moreover, we are able to construct \(\mathcal{P}^n_{3,9}\) in the following way

\[\mathcal{P}_{3,9}^{n}(i) = \{3(i-1)+1, 3(i-1)+2, 3(i-1)+3\},\\] \[\sum \mathcal{P}_{3,9}^{n}(i) = 9i-3, \quad \text{for} \quad i = 1, 2, \dots, n.\]

Thus \(\mathcal{P}_{3,d}^n\) exists for \(d=\pm 1,\pm 3,\pm 5,\pm 9\) and if \(n\equiv 1\pmod 2\) also for \(d=0,\pm 2\). For the partition into 4-tuples we can use the following fact

\[\mathcal{P}_{4,d}^n(i) = \mathcal{P}_{l,s}^n(i) \cup \left(\mathcal{P}_{m,t}^n(i) \oplus ln\right),\]

where l = 3, m = 1 or l = 2, m = 2. Also

\[\mathcal{P}_{4,16}^{n}(i) = \{4(i-1)+1, 4(i-1)+2, 4(i-1)+3, 4(i-1)+4\},\\] \[\sum \mathcal{P}_{4,16}^{n}(i) = 16i-6, \quad \text{for} \quad i = 1, 2, \dots, n.\]

Thus P n ⁴,d exists for d = 0, ±2, ±4, ±6, ±8, ±10, ±16 and if n ≡ 1 (mod 2) also for d = ±1, ±3, ±5.

Let us note that each of the defined partition P n k,d has the property that

\[\sum \mathcal{P}_{k,d}^n(i) = C_{k,d}^n + di,\]

where C n k,d is a constant depending on the parameters k and d.

4. d-antimagic labelings for certain families of plane graphs

In this section, we shall use the edge-antimagic labelings of paths Pⁿ and the partitions of the set {1, 2, . . . , kn} with determined differences described in the previous two sections to examine the existence of a super d-antimagic labeling for several families of plane graphs.

The friendship graph Fⁿ is a set of n triangles having a common central vertex, say v, and otherwise disjoint. The friendship graph Fⁿ has 2n vertices of degree 2, say vⁱ , uⁱ for i = 1, 2, . . . , n, and 3n edges, say viv, uiv, viuⁱ for i = 1, 2, . . . , n. Let us define the 3-sided face fⁱ , i = 1, 2, . . . , n, as the face bounded by the edges vvⁱ , viuⁱ and uiv and let f be the external unbounded face.

Theorem 4.1. The friendship graph Fn, n ≥ 2, has a super d-antimagic labeling of type (1, 1, 0) for d ∈ {1, 3, 5, 7, 9, 11, 13}.

Moreover, if n ≡ 1 (mod 2) then the graph Fⁿ also admits a super d-antimagic labeling of type (1, 1, 0) for d ∈ {0, 2, 4, 6, 8, 10}.

Proof. We define the bijection g¹ : V (Fn) ∪ E(Fn) → {1, 2, . . . , 5n + 1} as follows:

\[\begin{aligned} \{g_1(v_i), g_1(u_i)\} &= \mathcal{P}_{2,k}^n(i), & i &= 1, 2, \dots, n, \\ g_1(v) &= 2n + 1, & i &= 1, 2, \dots, n, \\ \{g_1(v_iv), g_1(v_iu_i), g_1(u_iv)\} &= \mathcal{P}_{3,l}^n(i) \oplus (2n + 1) & i &= 1, 2, \dots, n, \end{aligned}\]

where k = 0, ±2, ±4 or for n ≡ 1 (mod 2) also k = ±1, and l = ±1, ±3, ±5, ±9 or for n ≡ 1 (mod 2) also l = 0, ±2.

It is not difficult to check that the vertices are labeled by the smallest possible numbers 1, 2, . . . , 2n + 1. Moreover, for the weight of the face fⁱ , i = 1, 2, . . . , n, we obtain

\[w_{g_1}(f_i) = (g_1(v_i) + g_1(u_i)) + g_1(v) + (g_1(v_iv) + g_1(v_iu_i) + g_1(u_iv))\] \[= \sum_{k} \mathcal{P}_{2,k}^n(i) + (2n+1) + \sum_{k} (\mathcal{P}_{3,l}^n(i) \oplus (2n+1))\] \[= (C_{2,k}^n + ki) + (2n+1) + (C_{3,l}^n + li + 3(2n+1))\] \[= C_{2,k}^n + C_{3,l}^n + 4(2n+1) + (k+l)i.\]

As k = 0, ±2, ±4 or for n ≡ 1 (mod 2) also k = ±1, and l = ±1, ±3, ±5, ±9 or for n ≡ 1 (mod 2) also l = 0, ±2, we obtain that k + l ∈ {1, 3, 5, 7, 9, 11, 13} and for n odd we also get k + l ∈ {0, 2, 4, 6, 8, 10}. Thus under the labeling g¹ the weights of the 3-sided faces form an arithmetic sequence with the desired difference, which completes the proof.

If we replace every edge viuⁱ , i = 1, 2, . . . , n, of the friendship graph Fⁿ by a path of length two with vertices vⁱ , wⁱ , uⁱ , then we obtain a graph, say Bn, with the vertex set V (Bn) = {vⁱ , wⁱ , uⁱ , v : i = 1, 2, . . . , n} and the edge set E(Bn) = {viv, uiv, viwⁱ , wiuⁱ : i = 1, 2, . . . , n}. Let us define the 4-sided face fⁱ , i = 1, 2, . . . , n, as the face bounded by the edges vvⁱ , viwⁱ , wiuⁱ and uiv and let f be the external unbounded face.

Theorem 4.2. The graph Bn, n ≥ 2, has a super d-antimagic labeling of type (1, 1, 0) for d ∈ {1, 3, 5, . . . , 21, 25}.

Moreover, if n ≡ 1 (mod 2) then the graph Bⁿ also admits a super d-antimagic labeling of type (1, 1, 0) for d ∈ {0, 2, 4, . . . , 18}.

Proof. We define the bijection g² : V (Bn) ∪ E(Bn) → {1, 2, . . . , 7n + 1} in the following way:

\[\begin{aligned} \{g_2(v_i), g_2(w_i), g_2(u_i)\} &= \mathcal{P}_{3,k}^n(i), & i &= 1, 2, \dots, n, \\ g_2(v) &= 3n + 1, & i &= 1, 2, \dots, n, \\ \{g_2(v_iv), g_2(v_iw_i), g_2(w_iu_i), g_2(u_iv)\} &= \mathcal{P}_{4,l}^n(i) \oplus (3n + 1), & i &= 1, 2, \dots, n. \end{aligned}\]

It is not difficult to see that the vertices are labeled by the numbers 1, 2, . . . , 3n + 1. Moreover, for the weight of the face fⁱ , i = 1, 2, . . . , n, we have

\[w_{g_2}(f_i) = (g_2(v_i) + g_2(w_i) + g_2(u_i)) + g_2(v)\] \[+ (g_2(v_iv) + g_2(v_iw_i) + g_2(w_iu_i) + g_2(u_iv))\] \[= \sum_{k=0}^{n} \mathcal{P}_{3,k}^n(i) + (3n+1) + \sum_{k=0}^{n} (\mathcal{P}_{4,l}^n(i) \oplus (3n+1))\] \[= (C_{3,k}^n + ki) + (3n+1) + (C_{4,l}^n + li + 4(3n+1))\] \[= C_{3,k}^n + C_{4,l}^n + 5(3n+1) + (k+l)i,\]

where k = ±1, ±3, ±5, ±9 or for n ≡ 1 (mod 2) also k = 0, ±2, and l = 0, ±2, ±4, ±6, ±8, ±10, ±16 or for n ≡ 1 (mod 2) also l = ±1, ±3, ±5. It means that g² is a super d-antimagic labeling of type (1, 1, 0) of Bn, for d = 1, 3, 5, . . . , 21, 25 and if n ≡ 1 (mod 2) then d = 0, 2, 4, . . . , 18.

A triangular snake Eⁿ is a triangular cactus whose block-cutpoint graph is a path, i.e. Eⁿ is obtained from a path v1, v2, . . . , vn+1 by joining vⁱ and vi+1 to a new vertex uⁱ , for i = 1, 2, . . . , n. Let fⁱ be the 3-sided face, i = 1, 2, . . . , n, bounded by the edges viuⁱ , uivi+1 and vivi+1. We denote the external unbounded face by the symbol f.

Theorem 4.3. The graph En, n ≥ 2, has a super d-antimagic labeling of type (1, 1, 0) for d ∈ {0, 1, 2, . . . , 12}.

Proof. Define the bijection g³ : V (En) ∪ E(En) → {1, 2, . . . , 5n + 1} as follows:

\[g_3(v_i) = \alpha_k^{n+1}(v_i), \qquad i = 1, 2, \dots, n+1,\]
\[g_3(u_i) = \alpha_k^{n+1}(v_i v_{i+1}), \qquad i = 1, 2, \dots, n,\]
\[\{g_3(v_i u_i), g_3(u_i v_{i+1}), g_3(v_{i+1} v_i)\} = \mathcal{P}_{3,l}^n(i) \oplus (2n+1), \qquad i = 1, 2, \dots, n.\]

The labeling g³ assigns the numbers 1, 2, . . . , 2n + 1 to the vertices of the graph En. For the weight of the face fⁱ , i = 1, 2, . . . , n, we have

\[w_{g_3}(f_i) = (g_3(v_i) + g_3(u_i) + g_3(v_{i+1})) + (g_3(v_iu_i) + g_3(u_iv_{i+1}) + g_3(v_{i+1}v_i))\] \[= w_{\alpha_k^{n+1}}(v_iv_{i+1}) + \sum_{l} \mathcal{P}_{3,l}^n(i) \oplus (2n+1)\] \[= (C_{\alpha,k}^{n+1} + ki) + (C_{3,l}^n + li + 3(2n+1))\] \[= C_{\alpha,k}^{n+1} + C_{3,l}^n + 3(2n+1) + (k+l)i,\]

where k = 0, ±1, ±2, ±3 and l = ±1, ±3, ±5, ±9, moreover for n ≡ 1 (mod 2) also l = 0, ±2. Analogously as in the proof of the previous theorem we obtain that for d ∈ {0, 1, 2, . . . , 12} the bijection g³ is a super d-antimagic labeling of type (1, 1, 0) of the graph En.

If we replace every edge vivi+1, i = 1, 2, . . . , n, of the triangular snake Eⁿ by a path of length two with vertices vⁱ , wⁱ , vi+1, then we obtain a graph, say Gn, with the vertex set V (Gn) = {v1, v2, . . . , vn+1, u1, u2, . . . , un, w1, w2, . . . wn} and the edge set E(Gn) = {viuⁱ , uivi+1, viwⁱ , wivi+1 : i = 1, 2, . . . , n}. Let us define the 4-sided face fⁱ , i = 1, 2, . . . , n, as the face bounded by the edges viuⁱ , uivi+1, viwⁱ and wivi+1 and let f be the external unbounded face.

Theorem 4.4. The graph Gn, n ≥ 2, has a super d-antimagic labeling of type (1, 1, 0) for d ∈ {0, 1, 2, . . . , 22}.

Proof. Define the bijection g⁴ : V (Gn) ∪ E(Gn) → {1, 2, . . . , 7n + 1} in the following way:

\[g_4(v_i) = \beta_k^{n+1}(v_i), \qquad i = 1, 2, \dots, n+1,\]
\[\{g_4(u_i), g_4(w_i)\} = \mathcal{P}_{2,l}^n(i) \oplus (n+1), \qquad i = 1, 2, \dots, n,\]
\[\{g_4(v_i u_i), g_4(u_i v_{i+1}), g_4(v_i w_i), g_4(w_i v_{i+1})\}\]
\[= \mathcal{P}_{4,m}^n(i) \oplus (3n+1), \qquad i = 1, 2, \dots, n.\]

It is easy to verify that the labeling g⁴ assigns integers 1, 2, . . . , 3n+ 1 to the vertices. By direct computation we obtain that the weight of the face fⁱ , i = 1, 2, . . . , n, admits a value

\[w_{g_4}(f_i) = (g_4(v_i) + g_4(v_{i+1})) + (g_4(u_i) + g_4(w_i)) + (g_4(v_iu_i) + g_4(u_iv_{i+1}) + g_4(v_iw_i) + g_4(w_iv_{i+1})) = w_{\beta_k^{n+1}}(v_iv_{i+1}) + \sum_{l} \mathcal{P}_{2,l}^n(i) \oplus (n+1) + \sum_{l} \mathcal{P}_{4,m}^n(i) \oplus (3n+1) = (C_{\beta,k}^{n+1} + ki) + (C_{2,l}^n + li + 2(n+1)) + (C_{4,m}^n + mi + 4(3n+1)) = C_{\beta,k}^{n+1} + C_{2,l}^n + C_{4,m}^n + 14n + 6 + (k+l+m)i,\]

where \(k = \pm 1, \pm 2, l = 0, \pm 2, \pm 4\) and \(m = 0, \pm 2, \pm 4, \pm 6, \pm 8, \pm 10, \pm 16\). After some manipulations we obtain that there exists a super d-antimagic labeling of the graph \(G_n\) for every difference \(d \in \{0, 1, 2, \dots, 22\}\).

Let ladder \(L_n\) be a Cartesian product \(L_n \simeq P_n \times P_2\) of a path on n vertices with a path on two vertices. Let \(V(L_n) = \{v_1, v_2, \ldots, v_n, u_1, u_2, \ldots, u_n\}\) be the vertex set and \(E(L_n) = \{v_i v_{i+1}, u_i u_{i+1} : i = 1, 2, \ldots, n-1\} \cup \{v_i u_i : i = 1, 2, \ldots, n\}\) be the edge set of ladder. Let us define the 4-sided face \(f_i\), \(i = 1, 2, \ldots, n\), as the face bounded by the edges \(v_i v_{i+1}\), \(v_{i+1} u_{i+1}\), \(u_i u_{i+1}\) and \(v_i u_i\) and let f be the external unbounded face.

Theorem 4.5. The ladder \(L_n \simeq P_n \times P_2\), \(n \geq 3\), admits a super d-antimagic labeling of type (1,1,0) for \(d \in \{0,1,2,\ldots,10\}\).

Proof. Construct the bijective function \(g_5: V(L_n) \cup E(L_n) \to \{1, 2, \dots, 5n-2\}\) as follows:

\[g_{5}(v_{i}) = \beta_{k}^{n}(v_{i}), \qquad i = 1, 2, \dots, n,\] \[g_{5}(u_{i}) = \beta_{l}^{n}(v_{i}) + n, \qquad i = 1, 2, \dots, n,\] \[g_{5}(v_{i}u_{i}) = \beta_{m}^{n}(v_{i}) + 2n, \qquad i = 1, 2, \dots, n,\] \[\{g_{5}(v_{i}v_{i+1}), g_{5}(u_{i}u_{i+1})\} = \mathcal{P}_{2,t}^{n-1}(i) \oplus (3n), \qquad i = 1, 2, \dots, n-1.\]

It is a routine procedure to verify that the vertices are labeled by the smallest possible numbers \(1, 2, \ldots, 2n\). Moreover, for the weight of the face \(f_i, i = 1, 2, \ldots, n-1\), we obtain

\[w_{g_5}(f_i) = (g_5(v_i) + g_5(v_{i+1})) + (g_5(u_i) + g_5(u_{i+1})) + (g_5(v_iu_i) + g_5(v_{i+1}u_{i+1}))\] \[+ (g_5(v_iv_{i+1}) + g_5(u_iu_{i+1}))\] \[= w_{\beta_k^n}(v_iv_{i+1}) + (w_{\beta_l^n}(v_iv_{i+1}) + 2n) + (w_{\beta_m^n}(v_iv_{i+1}) + 4n)\] \[+ \sum_{l=1}^{n} \mathcal{P}_{2,t}^{n-1}(i) \oplus (3n)\] \[= (C_{\beta,k}^n + ki) + (C_{\beta,l}^n + li + 2n) + (C_{\beta,m}^n + mi + 4n)\] \[+ (C_{2,t}^{n-1} + ti + 6n)\] \[= C_{\beta,k}^n + C_{\beta,l}^n + C_{\beta,m}^n + C_{2,t}^{n-1} + 12n + (k+l+m+t)i.\]

As \(k = \pm 1, \pm 2, \ l = \pm 1, \pm 2, \ m = \pm 1, \pm 2\) and \(t = 0, \pm 2, \pm 4\) we obtain that \(k + l + m + t \in \{0, 1, 2, 3, \dots, 10\}\). This completes the proof.

Another variation of a ladder graph is specified as follows. A ladder \(\mathbb{L}_n\), \(n \geq 2\), is a graph obtained by completing the ladder \(L_n \simeq P_n \times P_2\) by n-1 edges such that \(V(\mathbb{L}_n) = \{v_1, v_2, \dots, v_{2n}\}\) is the vertex set and \(E(\mathbb{L}_n) = \{v_1v_2, v_2v_3, \dots, v_{2n-1}v_{2n}, v_1v_3, v_2v_4, \dots, v_{2n-2}v_{2n}\}\) is the edge set.

Theorem 4.6. The graph \(\mathbb{L}_n\), \(n \geq 2\), admits a super d-antimagic labeling of type (1,1,0) for \(d \in \{0,1,2,\ldots,6\}\).

Proof. Construct the bijective function \(g_6:V(\mathbb{L}_n)\cup E(\mathbb{L}_n)\to \{1,2,\ldots,6n-1\}\) in the following way:

On d-antimagic labelings of plane graphs | Martin Baca et al. ˇ

\[g_{6}(v_{i}) = i, i = 1, 2, \dots, 2n,\]
\[g_{6}(v_{i}v_{i+1}) = \beta_{k}^{2n-1}(v_{i}) + 2n, i = 1, 2, \dots, 2n - 1,\]
\[g_{6}(v_{i}v_{i+2}) = \mathcal{P}_{1,l}^{2n-2}(i) \oplus (4n - 1), i = 1, 2, \dots, 2n - 2.\]

The reader can easily verify that the labeling g⁶ assigns integers 1, 2, . . . , 2n to the vertices and a weight of the face fⁱ , i = 1, 2, . . . , 2n − 2, is

\[w_{g_6}(f_i) = (g_6(v_i) + g_6(v_{i+1}) + g_6(v_{i+2})) + (g_6(v_iv_{i+1}) + g_6(v_{i+1}v_{i+2})) + g_6(v_iv_{i+2})\] \[= (i + (i+1) + (i+2)) + (w_{\beta_k}^{2n-1}(v_iv_{i+1}) + 4n) + \sum_{l=1}^{n} \mathcal{P}_{1,l}^{2n-2}(i) \oplus (4n-1)\] \[= (3+3i) + (C_{\beta,k}^{2n-1} + ki + 4n) + (C_{1,l}^{2n-2} + li + (4n-1))\] \[= C_{\beta,k}^{2n-1} + C_{1,l}^{2n-2} + 8n + 2 + (3+k+l)i.\]

Since k = ±1, ±2, and l = ±1 we are able to show that 3 + k + l ∈ {0, 1, 2, . . . , 6}. This implies that the labeling g⁶ is a super d-antimagic labeling of type (1, 1, 0) for d ∈ {0, 1, 2, . . . , 6} of the graph Ln.

If we replace every edge vivi+1 (respectively, every edge uiui+1), i = 1, 2, . . . , n−1, of the ladder Lⁿ ' Pⁿ × P² by a path of length two with vertices vⁱ , wⁱ , vi+1 (respectively, uⁱ , wn−1+ⁱ , ui+1) then we obtain a graph, say Hn, with the vertex set V (Hn) = {v1, v2, . . . , vn, u1, u2, . . . , un, w1, w2, . . . , w2n−2} and the edge set E(Hn) = {viwⁱ , wivi+1, uiwn−1+ⁱ , wn−1+iui+1 : i = 1, 2, . . . , n− 1} ∪ {viuⁱ : i = 1, 2, . . . , n}.

Let us define the 6-sided face fⁱ , i = 1, 2, . . . , n − 1, as the face bounded by the edges viwⁱ , wivi+1, vi+1ui+1, ui+1wn−1+ⁱ , wn−1+iuⁱ , uivⁱ and let f be the external unbounded face.

Theorem 4.7. The graph Hn, n ≥ 2, admits a super d-antimagic labeling of type (1, 1, 0) for d ∈ {0, 1, 2, . . . , 26}.

Proof. We define the bijection g⁷ : V (Hn) ∪ E(Hn) → {1, 2, . . . , 9n − 2} in the following way:

\[g_{7}(v_{i}) = \beta_{k}^{n}(v_{i}), \qquad i = 1, 2, ..., n,\] \[g_{7}(u_{i}) = \beta_{l}^{n}(v_{i}), \qquad i = 1, 2, ..., n,\] \[\{g_{7}(w_{i}), g_{7}(w_{n-1+i})\} = \mathcal{P}_{2,m}^{n-1}(i) \oplus (2n), \qquad i = 1, 2, ..., n-1,\] \[g_{7}(v_{i}u_{i}) = \beta_{t}^{n}(v_{i}) + 4n - 2, \qquad i = 1, 2, ..., n-1,\] \[\{g_{7}(v_{i}w_{i}), g_{7}(w_{i}v_{i+1}), g_{7}(u_{i}w_{n-1+i}), g_{7}(w_{n-1+i}u_{i+1})\}\] \[= \mathcal{P}_{4,s}^{n-1}(i) \oplus (5n - 2), \qquad i = 1, 2, ..., n-1.\]

It is easy to see that the vertices of Hⁿ are labeled by the smallest possible integers 1, 2, . . . , 4n − 2. For the weight of the face fⁱ , i = 1, 2, . . . , n − 1, we get

\[w_{g_{7}}(f_{i}) = (g_{7}(v_{i}) + g_{7}(v_{i+1})) + (g_{7}(u_{i}) + g_{7}(u_{i+1})) + (g_{7}(w_{i}) + g_{7}(w_{n-1+i}))\] \[+ (g_{7}(v_{i}u_{i}) + g_{7}(v_{i+1}u_{i+1})) + (g_{7}(v_{i}w_{i}) + g_{7}(w_{i}v_{i+1}) + g_{7}(u_{i}w_{n-1+i})\] \[+ g_{7}(w_{n-1+i}u_{i+1}))\] \[= w_{\beta_{k}^{n}}(v_{i}v_{i+1}) + (w_{\beta_{l}^{n}}(v_{i}v_{i+1}) + 2n) + \sum_{j} \mathcal{P}_{2,m}^{n-1}(i) \oplus (2n)\] \[+ (w_{\beta_{t}}^{n}(v_{i}v_{i+1}) + 8n - 4) + \sum_{j} \mathcal{P}_{4,s}^{n-1}(i) \oplus (5n - 2)\] \[= (C_{\beta,k}^{n} + ki) + (C_{\beta,l}^{n} + li + 2n) + (C_{2,m}^{n-1} + mi + 2(2n))\] \[+ (C_{\beta,t}^{n} + ti + 8n - 4) + (C_{4,s}^{n-1} + si + 4(5n - 2))\] \[= C_{\beta,k}^{n} + C_{\beta,l}^{n} + C_{\beta,t}^{n} + C_{2,m}^{n-1} + C_{4,s}^{n-1} + 34n - 12 + (k+l+m+t+s)i.\]

Since k = ±1, ±2, l = ±1, ±2, m = 0, ±2, ±4, t = ±1, ±2 and s = 0, ±2, ±4, ±6, ±8, ±10, ±16 we get that k + l + m + t + s ∈ {0, 1, 2, . . . , 26}. Thus g⁷ is the required super d-antimagic labeling of type (1, 1, 0) of the graph Hn. This completes the proof.

5. Concluding Remarks

In the foregoing section we studied the super d-antimagic labelings for the seven families of plane graphs. We have shown that there exist super d-antimagic labelings of type (1, 1, 0) for these graphs for wide variety of difference d. We conclude with the following open problems.

Problem 1. Find the upper bound for the feasible values of the difference d which makes a super d-antimagic labelings of type (1, 1, 0) possible for the studied families of plane graphs.

Problem 2. Find other feasible values of the difference d and the corresponding super d-antimagic labelings of type (1, 1, 0) for the studied families of plane graphs.

Acknowledgement

The work was supported by Slovak VEGA Grant 1/0130/12.

• [1] G. Ali, M. Baca, F. Bashir and A. Semani ˇ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, On face antimagic labelings of ´ disjoint union of prisms, Utilitas Math. 85 (2011), 97–112.
• [2] M. Baca, On magic labelings of grid graphs, ˇ Ars Combin. 33 (1992), 295–299.
• [3] M. Baca, On magic labelings of honeycomb, ˇ Discrete Math. 105 (1992), 305–311.
• [4] M. Baca, F. Bashir and A. Semani ˇ cov ˇ a, Face antimagic labelings of antiprisms, ´ Utilitas Math. 84 (2011), 209–224.
• [5] M. Baca, E.T. Baskoro, S. Jendrol ˇ ' and M. Miller, Antimagic labelings of hexagonal planar maps, Utilitas Math. 66 (2004), 231–238.

• [6] M. Baca, L. Brankovic and A. Semani ˇ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, Labelings of plane graphs contain- ´ ing Hamilton path, Acta Math. Sinica - English Series 27 (4) (2011), 701–714.
• [7] M. Baca, S. Jendrol ˇ ', M. Miller and J. Ryan, Antimagic labelings of generalized Petersen graphs that are plane, Ars Combin. 73 (2004), 115–128.
• [8] M. Baca, Y. Lin and M. Miller, Antimagic labelings of grids, ˇ Utilitas Math. 72 (2007), 65–75.
• [9] M. Baca, Y. Lin, F.A. Muntaner-Batle, Super edge-antimagic labelings of the path-like trees, ˇ Utilitas Math. 73 (2007), 117–128.
• [10] M. Baca and M. Miller, On ˇ d-antimagic labelings of type (1, 1, 1) for prisms, J. Combin. Math. Combin. Comput. 44 (2003), 199–207.
• [11] M. Baca and M. Miller, ˇ Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions, BrownWalker Press, Boca Raton, Florida, 2008.
• [12] M. Baca, M. Miller, O. Phanalasy and A. Semani ˇ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, Super d-antimagic la- ´ belings of disconnected plane graphs, Acta Math. Sinica - English Series 26 (12) (2010), 2283–2294.
• [13] H. Enomoto, A.S. Llado, T. Nakamigawa and G. Ringel, Super edge-magic graphs, ´ SUT J. Math. 34 (1998), 105–109.
• [14] J. Gallian, A dynamic survey of graph labeling. The Electronic J. Combin. 17 (2010), #DS6.
• [15] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull. 13 (1970), 451–461.
• [16] Ko-Wei Lih, On magic and consecutive labelings of plane graphs, Utilitas Math. 24 (1983), 165–197.
• [17] Y. Lin, Slamin, M. Baca and M. Miller, On d-antimagic labelings of prisms, ˇ Ars Combin. 72 (2004), 65–76.
• [18] R. Simanjuntak, F. Bertault and M. Miller, Two new (a, d)-antimagic graph labelings. Proc. of Eleventh Australasian Workshop on Combinatorial Algorithms (2000), 179–189.
• [19] K.A. Sugeng, M. Miller, Y. Lin and M. Baca, Face antimagic labelings of prisms, ˇ Utilitas Math. 71 (2006), 269–286.
• [20] W.D. Wallis, Magic Graphs, Birkhauser, Boston Basel Berlin, 2001. ¨