Darmaji^a , S. Wahyudi^a , Rinurwati^a , S.W. Saputro^b

{darmaji, suhud, rinur}@matematika.its.ac.id; suhadi@math.itb.ac.id

Suppose G = (V, E) be a simple graph with p vertices and q edges. An edge-magic total labeling of G is a bijection f : V ∪ E → {1, 2, . . . , p + q} where there exists a constant r for every edge xy in G such that f(x) + f(y) + f(xy) = r. An edge-magic total labeling f is called a super edge-magic total labeling if for every vertex v ∈ V (G), f(v) ≤ p. The super edge-magic total graph is a graph which admits a super edge-magic total labeling. In this paper, we consider some families of super edge-magic total graph G. We construct several graphs from G by adding some vertices and edges such that the new graphs are also super edge-magic total graphs.

Keywords: edge-magic total labeling, super edge-magic total graph, super edge-magic total labeling Mathematics Subject Classification: 05C78

DOI: 10.5614/ejgta.2022.10.1.21

1. Introduction

We assume that all graphs in this paper are simple and finite. Let G = (V, E) be a graph with p vertices and q edges. Let f be a bijection function defined as f : V ∪E → {1, 2, . . . , p+q}. Ringel and Llado [16] provided the definition that the function f is called an edge-magic total labeling if there exists a constant r for every edge xy in G such that the weight of the edge f(x) + f(y) + f(xy) = r. We can say the constant r as a magic constant of f. Wallis [18] then called a graph G admitting an edge-magic labeling as an edge-magic total graph.

Received: 2 June 2021, Revised: 23 January 2022, Accepted: 12 April 2022.

^aDepartment of Mathematics, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia

^bDepartment of Mathematics, Institut Teknologi Bandung, Jl.Ganesa 10 Bandung, Indonesia

The edge-magic total concept was introduced by Kotzig and Rosa [10, 11]. They proved that complete bipartite graphs Km,n (m, n ≥ 1) and cycles Cⁿ (n ≥ 3) are edge-magic total graphs. They also proved that a complete graph Kⁿ is edge-magic total graph if and only if n = 1, 2, 3, 4, 5 or 6; and the disjoint union of n copies of P² has an edge-magic total labeling if and only if n is odd. Interested readers are referred to a number of relevant literature that are mentioned in the bibliography section, including [1, 8, 14, 16, 17].

In this paper, we consider an edge-magic total labeling of G where the p smallest labels are given to V (G). Enomoto et al. [3] defined this version of edge-magic total labeling as a super edge-magic total labeling. If there exists a super edge-magic total labeling in a graph G, then G is called as a super edge-magic total graph.

Enomoto et al. [3] proved that caterpillars are super edge-magic total. They also determined that a complete graph Kⁿ is super edge-magic total if and only if n = 1, 2, or 3; and a complete bipartite graph Km,n is super edge-magic total if and only if m = 1 or n = 1. Enomoto et al. also proved that odd cycles are super edge-magic total. Some other results on super edge-magic total graph can be seen in [4, 5, 6, 7, 8, 9, 15].

The following properties are useful to show whether a graph G is super edge-magic total or not. A graph G = (V, E) is super edge-magic total graph if there exists a vertex labeling that causes a consecutive labeling.

Lemma 1.1. [2, 6] A graph G is super edge-magic total if and only if there is a vertex labeling f such that f(V (G)) and {f(u) + f(v) | uv ∈ E(G)} are both consecutive.

In this case, in order to show that graph G is super edge-magic total graph, it is simply indicated by taking a bijection of vertex labeling f : V → {1, 2, . . . , p} where {f(u) + f(v) | uv ∈ E(G)} is consecutive. The vertex labeling f can be extended to be a total labeling by defining f(uv) = p + q + min{f(u) + f(v) | uv ∈ E(G)} − f(u) − f(v) for every edge uv ∈ E(G). So that, the total labeling f is a super edge-magic total labeling of G.

In this paper, we will construct some families of super edge-magic total graph which obtained from a known super edge-magic total graph. We obtain four results. First theorem is related to a path Pn. Lee and Lee [12] have provided a construction on a path P² such that a new graph is super edge-magic total. In this paper, we generalized such construction on a path P2ⁿ (n ≥ 1).

The second result is related to disjoint union graph and joint product graphs. For graphs G and H, a disjoint union graph G ∪ H is a graph with vertex set V (G) ∪ V (H) and an edge set E(G)∪E(H). A joint product graph of G and H, denoted by G+H, is a graph with V (G+H) = V (G) ∪ V (H) and E(G + H) = E(G) ∪ E(H) ∪ {uv | u ∈ V (G), v ∈ V (H)}. For any super edge-magic total graphs G, we construct a new graph from G by using disjoint union and joint product with some graphs, such that a new graph is also super edge-magic total.

For the third result, we define graph G(+)Pm(+)H where m ≥ 2 as a graph obtained by taking one copy of the graphs G and H and a path Pm, then connect an end point of P^m to all vertices of G and the other end point of P^m to all vertices of H. For any super edge-magic total graphs G, we provide some graphs H such that G(+)Pm(+)H is also super edge-magic total. The last result is a construction of a super edge-magic total graph from a super edge-magic total graph by considering a super edge-magic labeling of the origin graph.

2. Main Results

In this section, we provide some constructions to obtain a new super edge-magic total graph which obtained from a super edge-magic total graph.

First, we consider a path Pⁿ (n ≥ 2). Lopez et al. [13] have proved that paths are super edge- ´ magic total. Now, we define a graph (Pⁿ ∪ hK1)(+)2K¹ (h ≥ 1), which is a graph obtained by taking one copy of a path Pn, h copies of K1, and two isolated vertices (2K1), then connect all end points of Pⁿ and all vertices of h copies of K¹ to both two vertices of 2K1. We can say that V ((Pn∪hK1)(+)2K1) = V (Pn)∪V (hK1)∪V (2K1) and E((Pn∪hK1)(+)2K1) = E(Pn)∪{uv | u ∈ V (hK1) or u is an end point of Pn; v ∈ V (2K1)}. In [12], Lee and Lee have proved that (P² ∪ hK1)(+)2K¹ (h ≥ 1) are super edge-magic total. In the following theorem, we generalize Lee and Lee construction on a path P2ⁿ (n ≥ 1).

Theorem 2.1. For integers h, n ≥ 1, graphs (P2ⁿ ∪ hK1)(+)2K¹ are super edge-magic total.

Figure 1. Graph (P2ⁿ ∪ hK1)(+)2K1.

Proof of Theorem 2.1. Let V (hK1) = {xⁱ | 1 ≤ i ≤ h}, V (2K1) = {y1, y2}, V (P2n) = {zⁱ | 1 ≤ i ≤ 2n}, and E(P2n) = {zizi+1 | 1 ≤ i ≤ 2n − 1}. It is easy to verify that (P2ⁿ ∪ hK1)(+)2K¹ has 2n + h + 2 vertices and 2n + 2h + 3 edges.

Now, we define a vertex labeling f : V ((P2ⁿ ∪ hK1)(+)2K1) → {1, 2, . . . , 2n + h + 2} where for v ∈ V ((P2ⁿ ∪ hK1)(+)2K1),

\[f(v) = \begin{cases} 1, & \text{if } v = y_1, \\ 2n + h + 2, & \text{if } v = y_2, \\ 1 + i, & \text{if } v = z_{2i} \text{ with } 1 \le i \le n, \\ n + 1 + h + i, & \text{if } v = z_{2i-1} \text{ with } 1 \le i \le n, \\ n + 1 + i, & \text{if } v = x_i \text{ with } 1 \le i \le h. \end{cases}\]

By the labeling above, we obtain that for uv ∈ E((P2ⁿ ∪ hK1)(+)2K1):

• If u = y1, since v is an end point of P2ⁿ or an element of V (hK1) then {f(u) + f(v)} = {1 + f(v)} = {n + 2, n + 3, . . . , n + h + 3}.

• If u, v ∈ V (P2n), then {f(u)+f(v)} = {f(z2i−1)+f(z2i) | 1 ≤ i ≤ n}∪{f(z2i)+f(z2i+1) | 1 ≤ i ≤ n−1} = {n+h+4, n+h+6, . . . , 3n+h+2}∪{n+h+5, n+h+7, . . . , 3n+h+1} = {n + h + 4, n + h + 5, . . . , 3n + h + 2}.
• If u = y2, since v is an end point of P2ⁿ or an element of V (hK1) then {f(u) + f(v)} = {2n + h + 2 + f(v)} = {3n + h + 3, 3n + h + 4, . . . , 3n + 2h + 4}.

Therefore, {f(u) + f(v) | uv ∈ E((P2ⁿ ∪ hK1)(+)2K1)} is a consecutive sequence. By Lemma 1.1, the graph (P2ⁿ ∪ hK1)(+)2K¹ is a super edge-magic total graph.

Before we continue to the next constructions, we need to show the following property of a super edge-magic total labeling.

Lemma 2.1. Let G be a connected graph with m ≥ 2 vertices. Let f be a super edge-magic total labeling of G. Then max{f(u) + f(v) | uv ∈ E(G)} ≥ m + 1.

Proof. Suppose that max{f(u) + f(v) | uv ∈ E(G)} ≤ m. Since G is connected, a vertex u with f(u) = m will be adjacent to another vertex v. So, f(u) + f(v) = m + f(v) ≥ m + 1, a contradiction.

In the following theorem, we give a construction of a super edge-magic total graph obtained from any super edge-magic total graphs by applying disjoint union and joint product to an origin graph.

Theorem 2.2. Let G^m be a connected graph with m ≥ 3 vertices. Let f be a super edge-magic total labeling of Gm. If k = max{f(u) + f(v) | uv ∈ E(Gm)}, then (G^m ∪(k − m − 1)K1) + K¹ is a super edge-magic total graph.

Figure 2. Graph (G^m ∪ (k − m − 1)K1) + K¹ where: (a) k = m + 1; (b) k ≥ m + 2.

Proof. Let H = (G^m ∪(k−m−1)K1)+K1. By considering Lemma 2.1, we obtain k−m−1 ≥ 0. In case k − m − 1 = 0, we have H = (G^m ∪ (k − m − 1)K1) + K¹ = G^m + K1. We define V ((k − m − 1)K1) = {xⁱ | 1 ≤ i ≤ k − m − 1}. Note that (k − m − 1)K¹ is a graph

without edges. Thus, we can say that V (H) = V (Gm) ∪ V ((k − m − 1)K1) ∪ {y}. Meanwhile, E(H) = E(Gm) ∪ {uy | u ∈ V (G^m ∪ (k − m − 1)K1)}. It is easy to see that |V (H)| = k and |E(H)| = |E(Gm)| + k − 1.

Let f be a super edge-magic labeling of G^m where k = max{f(u) + f(v) | uv ∈ E(Gm)}. Note that for v ∈ V (Gm), f(v) ∈ {1, 2, . . . , m}. Now, we define a vertex labeling g : V (H) → {1, 2, . . . , k} where for v ∈ V (H),

\[g(v) = \begin{cases} f(v), & \text{if } v \in V(G_m), \\ k, & \text{if } v = y, \\ m+i, & \text{if } v = x_i \text{ with } 1 \le i \le k-m-1. \end{cases}\]

By the labeling above, we obtain that for uv ∈ E(H):

• If u, v ∈ V (Gm), since f is a super edge-magic labeling of Gm, then {g(u) + g(v)} = {f(u) + f(v)} is a consecutive sequence, whose greatest element is k.
• if u ∈ V (Gm) and v = y, then {g(u) + g(v)} = {g(u) + k} = {k + 1, k + 2, . . . , k + m}.
• if u ∈ V ((k − m − 1)K1) and v = y, then {g(u) + g(v)} = {g(u) + k} = {k + m + 1, k + m + 2, . . . , 2k − 1}.

Therefore, {g(u) + g(v) | uv ∈ E(H)} is a consecutive sequence. By Lemma 1.1, the graph H is a super edge-magic total graph.

Now, let us consider the graph G(+)Pm(+)H where m ≥ 2. Let u and v be two end points of the path Pm. Then we can write V (G(+)Pm(+)H) = V (G) ∪ V (Pm) ∪ V (H) and E(G(+)Pm(+)H) = E(G) ∪ E(Pm) ∪ E(H) ∪ {ux, vy | x ∈ V (G); y ∈ V (H)}. Thus, |V (G(+)Pm(+)H)| = |V (G)|+|V (Pm)|+|V (H)| and |E(G(+)Pm(+)H)| = |E(G)|+|E(Pm)|+ |E(H)| + |V (G)| + |V (H)|.

Theorem 2.3. Let G^m be a connected graph with m ≥ 3 vertices. Let f be a super edge-magic total labeling of G^m and m + k = max{f(u) + f(v) | uv ∈ E(Gm)}. Then for k ≥ 2 and n ≥ 1, the graph Gm(+)P2k−2(+)nK¹ is a super edge-magic total graph.

Figure 3. Graph Gm(+)P2k−2(+)nK1.

Proof of Theorem 2.3. Let \(H=G_m(+)P_{2k-2}(+)nK_1\) where \(n\geq 1\). It is easy to see that |V(H)|=m+n+2k-2 and \(|E(H)|=|E(G_m)|+m+n+2k-3\). We define \(V(nK_1)=\{x_i\mid 1\leq i\leq n\}\). Note that \(nK_1\) is a graph without edges. Let \(V(P_{2k-2})=\{z_i\mid 1\leq i\leq 2k-2\}\) and \(E(P_{2k-2})=\{z_iz_{i+1}\mid 1\leq i\leq 2k-3\}\). We assume that \(z_1\) and \(z_{2k-2}\) is adjacent to all vertices of \(G_m\) and \(nK_1\), respectively.

Let f be a super edge-magic labeling of \(G_m\). By considering Lemma 2.1, we have \(\max\{f(u)+f(v)\mid uv\in E(G_m)\}\geq m+1\). Now, we assume that \(\max\{f(u)+f(v)\mid uv\in E(G_m)\}=m+k\geq m+2\). Note that for \(v\in V(G_m),\ f(v)\in\{1,2,\ldots,m\}\). Define a vertex labeling \(g:V(H)\to\{1,2,\ldots,m+n+2k-2\}\) where for \(v\in V(H)\),

\[g(v) = \begin{cases} f(v), & \text{if } v \in V(G_m), \\ m+i, & \text{if } v = z_{2i} \text{ where } 1 \le i \le k-1, \\ m+k+i, & \text{if } v = z_{2i+1} \text{ where } 0 \le i \le k-2, \\ m+2k-2+i, & \text{if } v = x_i \text{ with } 1 \le i \le n. \end{cases}\]

By the labeling above, we obtain that for \(uv \in E(H)\):

• If \(u, v \in V(G_m)\), since f is a super edge-magic labeling of \(G_m\), then \(\{g(u) + g(v)\} = \{f(u) + f(v)\}\) is a consecutive sequence, whose greatest element is m + k.
• if \(u \in V(G_m)\) and \(v = z_1\), then \(\{g(u) + g(v)\} = \{g(u) + (m+k)\} = \{m+k+1, m+k+2, \ldots, 2m+k\}\).
• if \(u, v \in P_{2k-2}\), then \(\{g(u) + g(v)\} = \{2m + k + 1, 2m + k + 2, \dots, 2m + 3k 3\}\).
• if \(u \in V(nK_1)\) and \(v = z_{2k-2}\), then \(\{g(u) + g(v)\} = \{g(u) + (m+k-1)\} = \{2m+3k-2, 2m+2k-1, \ldots, 2m+3k-3+n\}\).

Therefore, \(\{g(u) + g(v) \mid uv \in E(H)\}\) is a consecutive sequence. By Lemma 1.1, the graph H is a super edge-magic total graph.

In the last theorem below, we will construct a super edge-magic total graph from a super edge-magic total graph by considering a super edge-magic labeling of the origin graph.

Theorem 2.4. Let \(G_m\) be a connected graph with \(m \geq 3\) vertices. Let f be a super edge-magic total labeling of \(G_m\). Let \(F = \{f(u) + f(v) \mid uv \in E(G_m)\}\). For \(ab \in E(G_m)\), let \(f(a) + f(b) = \min(F)\) where f(a) < f(b), \(\max(F) = m + k\), and for \(c \in V(G_m)\), f(c) = k.

• 1. For f(a) = 1, let \(G_m^*\) be a graph obtained by taking one copies of \(G_m\) and \(nK_1\) where \(n \ge 1\), then connect all vertices of \(nK_1\) to b. Then \(G_m^*\) is a super edge-magic total graph.
• 2. Let \(G_m^{**}\) be a graph obtained by taking one copies of \(G_m\) and \(nK_1\) where \(n \geq 1\), then connect all vertices of \(nK_1\) to c. Then \(G_m^{**}\) is a super edge-magic total graph.

Proof. Let f be a super edge-magic labeling of \(G_m\). Let \(F = \{f(u) + f(v) \mid uv \in E(G_m)\}\). For \(ab \in E(G_m)\), let \(f(a) + f(b) = \min(F)\) where f(a) < f(b). By considering Lemma 2.1, let \(\max(F) = m + k\) and for \(c \in V(G_m)\), f(c) = k.

We define \(V(nK_1)=\{x_i\mid 1\leq i\leq n\}\). Note that \(nK_1\) is a graph without edges. Let \(H\in\{G_m^*,G_m^{**}\}\). So, \(V(H)=V(G_m)\cup V(nK_1)\). It is easy to see that |V(H)|=m+n. In the other hand, \(E(G_m^*)=E(G_m)\cup\{bu\mid u\in V(nK_1)\}\) and \(E(G_m^{**})=E(G_m)\cup\{cu\mid u\in V(nK_1)\}\). Thus, we can verify that \(|E(H)|=|E(G_m)|+n\). We distinguish two cases. Case 1. \(H=G_m^*\)

So, f(a)=1. Now, we define a vertex labeling \(g:V(H)\to\{1,2,\ldots,m+n\}\) where for \(v\in V(H)\),

\[g(v) = \begin{cases} i, & \text{if } v = x_i, \\ f(v) + n, & \text{if } v \in V(G_m). \end{cases}\]

By the labeling above, we obtain that for \(uv \in E(H)\):

• If \(u \in V(nK_1)\) and v = b, then \(\{g(u) + g(v)\} = \{g(u) + (f(b) + n)\} = \{f(b) + n + 1, f(b) + n + 2, \dots, f(b) + 2n\}.\)
• If \(u, v \in V(G_m)\), since f is a super edge-magic labeling of \(G_m\), then \(\{g(u) + g(v)\} = \{(f(u) + n) + (f(v) + n)\} = \{f(u) + f(v) + 2n\}\) is a consecutive sequence, whose least element is f(b) + 2n + 1.

Therefore, \(\{g(u) + g(v) \mid uv \in E(H)\}\) is a consecutive sequence. By Lemma 1.1, the graph H is a super edge-magic total graph.

Case 2. \(H = G_m^{**}\)

Now, we define a vertex labeling \(h: V(H) \to \{1, 2, \dots, m+n\}\) where for \(v \in V(H)\),

\[h(v) = \begin{cases} f(v), & \text{if } v \in V(G_m), \\ m+i, & \text{if } v = x_i. \end{cases}\]

By the labeling above, we obtain that for \(uv \in E(H)\):

• If \(u, v \in V(G_m)\), since f is a super edge-magic labeling of \(G_m\), then \(\{g(u) + g(v)\} = \{f(u) + f(v)\}\) is a consecutive sequence, whose greatest element is m + k.
• If \(u \in V(nK_1)\) and v = c, then \(\{g(u) + g(v)\} = \{g(u) + k\} = \{m + k + 1, m + k + 2, \dots, m + k + n\}\).

Therefore, \(\{g(u) + g(v) \mid uv \in E(H)\}\) is a consecutive sequence. By Lemma 1.1, the graph H is a super edge-magic total graph.

An illustration of graphs \(G_m^*\) and \(G_m^{**}\) of a super edge-magic total graph \(G_m\) with \(m \geq 3\) vertices can seen in Figure 4 below. Let \(G_m\) be a super edge-magic total graph with \(m \geq 3\) vertices where \(V(G_m) = \{z_i \mid 1 \leq i \leq m\}\) and f be a super edge-magic labeling of \(G_m\). Let \(F = \{f(u) + f(v) \mid uv \in E(G_m)\}\). In figure below, we assume that \(f(z_p) + f(z_q) = \min(F)\) where \(f(z_p) < f(z_q)\). Thus, it is clear that \(a = z_p\) and \(b = z_q\). Let \(\max(F) = m + k\) and \(f(z_r) = k\). Therefore, we have \(c = z_r\). Note that it is possible to have either vertex c = a or c = b, where k = 1 or \(k = f(z_q)\), respectively.

Figure 4. Graphs \(G_m^*\) (left) and \(G_m^{**}\) (right).

Acknowledgement

This paper was partially supported by the Department of Mathematics, Faculty of Science and Data Analysis, Institut Teknologi Sepuluh Nopember, Ministry of Education, Culture, Research and Technology, No: 1586/PKS/ITS/2020 and by "Riset P2MI FMIPA ITB".

The authors are thankful to the anonymous referees for some comments that helped to improve the presentation of the manuscript.

References

• [1] J.B. Babujee and N. Rao, Edge-magic trees, Indian J. Pure Appl. Math., 33 (2002), 1837–1840.
• [2] Z. Chen, On super edge-magic graphs, J. Combin. Math. Combin. Comput., 38 (2001), 53-64.
• [3] H. Enomoto, A.S. Llado, T. Nakamigawa, and G. Ringel, Super edge-magic graphs, SUT J. Math., 34 (1998), 105–109.
• [4] R. Figueroa-Centeno, R. Ichishima, and F. Muntaner-Batle, Magical coronations of graphs, Australas. J. Combin., 26 (2002), 199–208.
• [5] R. Figueroa-Centeno, R. Ichisima, and F. Muntaner-Batle, On edge-magic labelings of certain disjoint unions of graphs, Australas. J. Combin., 32 (2005), 225–242.
• [6] R. Figueroa-Centeno, R. Ichishima, and F. Muntaner-Batle, On super edge-magic graphs, Ars Combin., 64 (2002), 81–95.

• [7] R. Figueroa-Centeno, R. Ichisima, F. Muntaner-Batle, and A. Oshima, A magical approach to some labeling conjectures, Discussiones Math. Graph Theory, 31 (2011), 79–113.
• [8] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., (2021) #DS6.
• [9] R. Ichishima, F.A. Muntaner-Batle, and A. Oshima, The consecutively super edge-magic deficiency of graphs and related concepts, Electron. J. Graph Theory Appl., 8 (1) (2020), 71–92.
• [10] A. Kotzig and A. Rosa, Magic valuations of complete graphs, Publications du Centre de Recherches Mathematiques Universite de Montreal, 175 (1972).
• [11] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull., 13 (1970), 451–461.
• [12] S.M. Lee and N.T. Lee, A., on super edge-magic graphs with many odd cycles, Congress. Numer., 163 (2003), 65–80.
• [13] S.C. Lopez, F.A. Muntaner-Batle, and M. Rius-Font, Enumerating super edge-magic label- ´ ings for some types of path-like trees, Util. Math., 96 (2015), 285–299.
• [14] A.A.G. Ngurah and E. T. Baskoro, On magic and antimagic total labelings of generalized Petersen graph, Util. Math., 63 (2003), 97–107.
• [15] A.A.G. Ngurah and R. Simanjuntak, On the super edge-magic deficiency of join product and chain graphs, Electron. J. Graph Theory Appl., 7 (1) (2019), 157–167.
• [16] G. Ringel and A. Llado, Another tree conjecture, Bull. ICA, 18 (1996), 83–85.
• [17] Slamin, M. Baca, Y. Lin, M. Miller, and R. Simanjuntak, Edge-magic total labeling of wheels, ˇ fans, and friendship graphs, Bull. ICA, 35 (2002), 89–98.
• [18] W.D. Wallis, Magic Graphs, Birkhauser, Boston (2001). ¨