How to construct new super edge-magic graphs from some old ones E.T. Baskoro1? , I W. Sudarsana2?? and Y.M. Cholily1 2 1 Department of Mathematics Institut Teknologi Bandung (ITB), Jalan Ganesa 10 Bandung 40132, Indonesia {ebaskoro, yus}@dns.math.itb.ac.id Department of Mathematics, Tadulako University, Jalan Sukarno-Hatta Palu, Indonesia [email protected] Abstract. In this paper, we study the property of super edge-magic total graphs. We give some further necessary conditions for such graphs. Based on this condition we provide some algorithms to contruct new super edge-magic total graphs from some old ones. Keywords : super, edge-magic total labeling 1 Introduction All graphs, in this paper, are finite and simple. A general reference for graph-theoretic ideas can be seen in [4]. For a graph G with vertex-set V (G) and edge-set E(G) an edge-magic total labeling is a bijection λ: V (G)∪E(G) → {1, 2, · · · , |V (G)∪E(G)|} with satisfying the property that there exists an integer k such that λ(x) + λ(xy) + λ(y) = k, for any edge xy in G. We call λ(x)+λ(xy)+λ(y) the edge sum of xy, and k the magic constant of graph G. In particular, if λ(V (G)) = {1, 2, · · · , |V (G)|} then λ is called super edge-magic total labeling. A graph is called (super) edge-magic total if it admits any (super) edge-magic total labeling. The notion of edge-magic total graphs was introduced and studied by Kotzig and Rosa [5] with a different name as graphs with magic valuations, while the term of super edge-magic total graphs was firstly introduced by Enomoto et al. [1]. They showed that a ? ?? Supported by Hibah Bersaing XII DP3M-DIKTI Indonesia, 2004, DIP Number: 004/XXIII/1/–/2004. Supported by Hibah Pekerti DP3M-DIKTI Indonesia, 2004. 2 E.T. Baskoro, I W. Sudarsana and Y.M. Cholily star Sn+1 = K1,n is the only complete bipartite graph which is super edge-magic total. They also showed that any odd cycle is super edge-magic total, but any wheel is not. Since then, a number of papers have studied super edge-magic property in graphs. For instances, Figueroa-Centeno et al. [3] and [2] derived a necessary and sufficient condition for a graph to be super edge-magic total and they also showed several class of graphs, such as fans fn ∼ = Pn +K1 with n ≤ 6, ladders Ln ∼ = Pn ×P2 for odd n, and the generalized prism G ∼ C × P for odd m and n ≥ 2, are super = m n edge-magic. They also studied the relationships between super edgemagic labeling with other labelings. However, a conjecture ”Every tree is super edge-magic total” proposed by Enomoto et al. [1] still remains open. In this paper, we study super edge-magic total labelings. We derive more necessary conditions to be able to know more deeply the property of such labelings. Based on this condition we give some algorithms to contruct a new super edge-magic labeling from some old ones. By using these algorithms we can provide more evidence to support the correctness of the conjecture proposed by Enomoto et al. 2 Some further necessary conditions Several necessary conditions for a graph to be super edge-magic have been derived by several authors. Enomoto et al. [1] showed that if a nontrivial graph G is super edge-magic then |E(G)| ≤ 2|V (G)| − 3. Furthermore, Figueroa-Centeno et al. [3] provide a neccessary and sufficient condition for a graph being super edge-magic as in the following lemma. Lemma 1. A (p, q)-graph G is super edge-magic if and only if there exists a bijective function f : V (G) → {1, 2, · · · , p} such that the set S = {f (u) + f (v) : uv ∈ E(G)} consists of q consecutive integers. In such a case, f extends to a super edge-magic labeling of G with the magic constant k = p+q +s, where s = min(S) and S = {f (u) + f (v) : uv ∈ E(G)} = {k − (p + 1), k − (p + 2), · · · , k − (p + q)}. How to construct new super edge-magic graphs 3 Further, in order to know what possible values of k 0 s for graph G to be super, we add the following neccessary conditions. Lemma 2. Let a (p, q)-graph G be super edge-magic total. Then, the magic constant k of G satisfies p + q + 3 ≤ k ≤ 3p. Proof. Since G is super edge-magic total then the vertices of G receive labels 1, 2, · · · , p and the edges receive p + 1, p + 2, · · · , p + q so that by Lemma 1 S = {f (u) + f (v) : uv ∈ E(G)} consists of consecutive integers a, a + 1, · · · , a + q − 1 for some positive integer a. The smallest possible magic constant of G obtained if a = 3. In this case the vertices of G with labels 1 and 2 are adjacent and the magic constant for this case must be k = (a + q − 1) + (p + 1) = p + q + 3. If the vertices of labels p − 1 and p are adjacent in G then we obtain the biggest possible magic constant of G , namely k = (p−1)+p+(p+1) = 3p. Therefore we obtain p+q +3 ≤ k ≤ 3p. u t The lower and upper bounds in Lemma 2 are tight, since the super edge-magic labelings λ1 and λ2 on a star Sn of n vertices shown in Fig. 1 have the magic constant 2n + 2 and 3n, respectively. 2 3 n 2n-2 2n-1 λ1 1 1 n+1 2 n-1 2n-2 2n-1 n n+1 λ2 Fig. 1. A star graph achieves the lower and upper bounds of k. Corollary 1 If k is the magic constant of a tree with p vertices then 2p + 2 ≤ k ≤ 3p. Furthermore, the magic constant of a (p, q)-graph G with c components ranges between 2p − c + 3 to 3p. 4 E.T. Baskoro, I W. Sudarsana and Y.M. Cholily Proof. The first statement holds, since in any tree the number of edges is one less than the number of vertices. If a (p, q)-graph G has c components then in each component Gi (i = 1, 2, · · · , c) we have E(Gi ) ≥ V (Gi ) − 1. Thus, |E(G)| ≥ |V (G)| − c and by Lemma 2 it implies that 2p − c + 3 ≤ k ≤ 3p. u t 3 Duality in super edge-magic labeling Given any edge-magic total labeling λ on a (p, q)-graph G, Wallis et al. [6] define the dual labeling λ0 of labeling λ as follows. λ0 (vi ) = M − λ(vi ), ∀vi ∈ V (G), and λ0 (x) = M − λ(x), ∀x ∈ E(G), where M = p + q + 1. It is easy to see that if λ is edge-magic total with the magic constant k then λ0 is edge-magic total with the magic constant k 0 = 3M − k. It is also easy to see that if λ is super edge-magic total then λ0 is no longer super edge-magic total. In the next theorem, we introduce another dual property which preserve the superness of edge-magic total labelings. Theorem 1. Let a (p, q)-graph G be super edge-magic total. Let λ be a super edge-magic total labeling of G with the magic constant k. Then, the labeling λ0 defined: λ0 (vi ) = p + 1 − λ(vi ), ∀vi ∈ V (G), and λ0 (x) = 2p + q + 1 − λ(x), ∀x ∈ E(G) is a super edge-magic total labeling with the magic constant k 0 = 4p + q + 3 − k. Proof. Let uv ∈ E(G). Then, λ0 (u) + λ0 (uv) + λ0 (v) = (p + 1 − λ(u)) + (2p + q + 1 − λ(uv)) + (p + 1 − λ(v)) = 4p + q + 3 − (λ(u) + λ(uv) + λ(v)) = 4p + q + 3 − k a constant. Therefore, λ0 is a super edge-magic total labeling of G with magic constant k 0 = 4p + q + 3 − k. u t The labeling λ0 in Theorem 1 is called the dual super labeling of λ on G. How to construct new super edge-magic graphs 4 5 Construction of new labelings In this section, we give algorithms to construct new super edge-magic graphs by extending the old ones. Theorem 2. From any super edge-magic (p, q)-graph G with the magic constant k, we can construct a new super edge-magic total graph from G by adding one pendant incident to vertex x of G whose label k − 2p − 1. The magic constant of the new graph is k 0 = k + 2. Proof. In the new graph, define a labeling in the following. Preserve all vertices labels of G. Increase the labels of all edges (except the new one) by 2. Label the new vertex and edge by p + 1 and p + 2 respectively. It can be verified that the resulting labeling on the new graph is super edge-magic total labeling with magic constant k = k + 2. Since 2p + 2 ≤ k ≤ 3p (by Lemma 2), the proposition holds for any value of k. u t Theorem 3. Let a (p, q)-graph G be super edge-magic total with the magic constant k and k ≥ 2p + 3. Then, a new graph formed from G by adding exactly two pendants incident to two distinct vertices x and y of G whose labels k − 2p and k − 2p − 2 respectively is super edge-magic total with the magic constant k 0 = k + 4. Proof. In the new graph denote by u and v the new vertices adjacent to x and y, respectively. Then, define a labeling in the new graph as follows. Preserve labels of all the vertices of G. Add all edge labels (except the new ones) by 4. Label vertices x and y by p+1 and p+2, respectively and label two new edges xu and yv by p + 3 and p + 4, respectively. For the new edges, clearly we have the edge sum of each is k + 4. Since each label of old edge increased by 4 then we get the edge sum of each old edge is also k + 4. Therefore, the new graph is super edge-magic total labeling. This process works only if k − 2p − 2 ≥ 1. This implies that k ≥ 2p + 3. u t Theorem 4. Let a (p, q)-graph G be super edge-magic total with the magic constant k and k ≥ 2p + 3. Then, a new graph formed from G by adding exactly three pendants incident to three distinct vertices x , y and z of G whose labels k −2p, k −2p−1 and k −2p−2 respectively is super edge-magic total with the magic constant k 0 = k + 6. Proof. In the new graph, define a labeling as follows. Preserve all vertex labels of G in the new graph. Increase all edge labels (except 6 E.T. Baskoro, I W. Sudarsana and Y.M. Cholily the new ones) by 6 in the new graph. Label the three new vertices u which adjacent to x, y and z by using the second row of either matrix A or B. Label the corresponding new edge e by using the third row from A or B. x y z x y z A = u : p + 1 p + 3 p + 2 , B = u : p + 2 p + 1 p + 3 e: p+4 p+6 p+5 e: p+5 p+4 p+6 For the new edges, clearly we have the edge sum of each is k + 6 (from the above matrix). Since each label of old edge increased by 6 then we get the edge sum of each old edge in the new graph is k + 6. Therefore, the new graph is super edge-magic total. Note that this process works only if k −2p−2 ≥ 1. This implies that k ≥ 2p+3. u t Alternatively, we have the following theorem for adding three pendants. Theorem 5. Let a (p, q)-graph G be super edge-magic total with the magic constant k and k ≥ 2p + 4. Then, a new graph formed from G by adding exactly three pendants incident to three distinct vertices x , y and z of G whose labels k − 2p + 1, k − 2p − 1 and k − 2p − 3 respectively is super edge-magic total with the magic constant k 0 = k + 6. Proof. The proof is similar with the one of Theorem 4 by using the following matrix C. u t x y z C = u : p + 1 p + 2 p + 3 e: p+4 p+5 p+6 Theorem 6. Let p be an odd integer. Let a (p, q)-graph G be super edge-magic total with the magic constant k = (5p + 3)/2. Then, a new graph formed from G by adding exactly p pendants incident to all vertices of G is also super edge-magic total with the magic constant k = (9p + 3)/2. Proof. In the new graph, define a labeling as follows. Preserve all vertex labels of G in the new graph. Increase all edge labels (except the new ones) by 2p in the new graph. Label each new vertex u which adjacent to the old vertex v by using the second row of the following matrix. Label the corresponding new edge e = vu by using the third row. How to construct new super edge-magic graphs 7 p+1 p+3 v: 1 2 · · · p−1 · · · p − 1 p 2 2 2 u : 3p+3 3p+5 · · · 2p p + 1 p + 2 · · · 3p−1 3p+1 2 2 2 2 e : 3p − 1 3p − 3 · · · 2p + 2 3p 3p − 2 · · · 2p + 3 2p + 1 For the new edges, clearly we have the edge sum of each is 9p+3 2 (from the above matrix). Since each label of old edge increased by 2p then we get the edge sum of each old edge in the new graph is k + 2p = 9p+3 . Therefore, the new graph is super edge-magic total. 2 u t Note that the (extension) construction method in Theorem 6 only works for a super edge-magic total graph with the magic constant k = (5p + 3)/2. There are several graphs of p vertices known to have the magic constant (5p + 3)/2, such as odd cycles and paths with odd number of vertices. Let C(n, s) be a graph contructed from path Pn of n vertices by adding s pendants to each vertex of Pn . Let us call C(n, s) by a caterpillar with s legs. We know that C(n, s) is super edge-magic total [5]. The following corollary shows one way how to label this graph so that super edge-magic total. Corollary 2 For odd n and s ≥ 1, the graph C(n, s) is super edgemagic total. Proof. Take a super edge-magic total labeling for path Pn , for odd n, with the magic constant (5n + 3)/2, namely label the vertices in the odd positions of Pn from left to right consecutively by 1, 2, · · · , (n + 1)/2; And then label the even positions from left to right consecutively by (n + 3)/2, (n + 5)/2, · · · , n; Next, it is easy to label all the edges of Pn so that we have a super edge-magic total labeling. Apply Theorem 6 to Pn . Denote the resulting graph by C(n, 1). For i = 1, 2, · · · , s − 1, apply Theorem 6 repeatedly to graph C(n, i) and denote the resulting graph by C(n, i + 1). In the final result, we have a super edge-magic labeling for C(n, s). u t Let Tp be a tree of p vertices, for p ≥ 3. For h ≥ 1 we denote by Tn + Ah a graph which is obtained by adding h pendants to one vertex of tree Tp . Then, we have: Theorem 7. From any super edge-magic total tree Tp with the magic constant k = 2p + 1 + s, for some s ∈ {1, 2, · · · , p}, we can construct a new super edge-magic total tree Tp + Ah . 8 E.T. Baskoro, I W. Sudarsana and Y.M. Cholily Proof. Apply Theorem 2 to Tp h times by attaching a new pendant each to vertex whose label k − 2p − 1. By using Theorem 7 we can obtain a class of trees which is super edge-magic total from just one super edge-magic total tree. For instances, the tree in Fig. 2(b) is obtained by applying Theorem 7 to the tree in (a). This theorem provides more facts to support the correctness of the Conjecture proposed by Enomoto et al. [1]. 1 9 8 6 10 2 4 7 5 11 3 (a) 1 2h+11 2h+10 6 2 2h+12 4 2h+9 5 2h+13 (b) 3 h+8 2h+8 2h+7 7 h+7 8 Fig. 2. The tree in (b) is formed from the tree in (a) by using Theorem 7. References 1. H. Enomoto, A.S. Llado, T. Nakamigawa and G. Ringel: Super edge-magic graphs, SUT J. Math. 2 (1998), 105-109. 2. R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On super edgemagic graphs, Ars Combin., 64 (2002) 81-95. 3. R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, The place of super edge-magic labelings among other classes of labelings, Discrete Math., 231 (2001) 153-168. 4. N. Hartsfield and G. Ringel: Pearls in Graph Theory (Academic Press, 1990). 5. A. Kotzig and A. Rosa: Magic valuations of finite graphs, Canad. Math. Bull. 13 (1970), 451-461. 6. W. D. Wallis, E. T. Baskoro, M. Miller and Slamin: Edge-magic total labelings, Australasian Journal of Combinatorics 22 (2000) 177-190.

© Copyright 2020