Some Results on Super Edge-Magic Deficiency of Graphs


Download PDF

Authors: M. IMRAN, A. Q. BAIG AND A. S. FENOVCíKOVá

DOI: 10.46793/KgJMat2002.237I

Abstract:

An edge-magic total labeling of a graph G is a bijection f : V (G) E(G) →{1, 2,,|V (G)| + |E(G)|}, where there exists a constant k such that f(u) + f(uv) + f(v) = k, for every edge uv E(G). Moreover, if the vertices are labeled with the numbers 1, 2,,|V (G)| such a labeling is called a super edge-magic total labeling. The super edge-magic deficiency of a graph G, denoted by μs(G), is the minimum nonnegative integer n such that GnK1 has a super edge-magic total labeling or is defined to be if there exists no such n.

In this paper we study the super edge-magic deficiencies of two types of snake graph and a prism graph Dn for n 0 (mod 4). We also give an exact value of super edge-magic deficiency for a ladder Pn × K2 with 1 pendant edge attached at each vertex of the ladder, for n odd, and an exact value of super edge-magic deficiency for a square of a path Pn for n 3.



Keywords:

Super edge-magic total labeling, super edge-magic deficiency, block graph, snake graph, prism, corona of graphs, square of graph.



References:

[1]   B. D. Acharya and S. M. Hegde, Strongly indexable graphs, Discrete Math. 93 (1991), 123–129.

[2]   A. Q. Baig, E. T. Baskoro and A. Semaničová–Feňovčíková, On the super edge-magic deficiency of a star forest, Ars Combin. 115 (2014), 3–12.

[3]   H. Enomoto, A. S. Lladó, T. Nakamigawa and G. Ringel, Super edge-magic graphs, SUT J. Math. 34 (1998), 105–109.

[4]   R. M. Figueroa, R. Ichishima and F. A. Muntaner-Batle, The place of super edge-magic labeling among other classes of labeling, Discrete Math. 231 (2001), 153–168.

[5]   R. M. Figueroa-Centeno, R. Ichishima and F. A. Muntaner-Batle, On the super edge magic deficiency of graphs, Electron. Notes Discrete Math. 11 (2002), 299–314.

[6]   R. M. Figueroa-Centeno, R. Ichishima and F. A. Muntaner-Batle, Some new results on the super edge-magic deficiency of graphs, J. Combin. Math. Combin. Comput. 55 (2005), 17–31.

[7]   R. M. Figueroa-Centeno, R. Ichishima and F. A. Muntaner-Batle, On the super edge-magic deficiency of graphs, Ars Combin. 78 (2006), 33–45.

[8]   A. Kotzig and A. Rosa, Magic valuaton of finite graphs, Canad. Math. Bull. 13(4) (1970), 451–461.

[9]   A. A. G. Ngurah and E. T. Baskoro, On magic and antimagic total labelings of generalized Petersen graph, Util. Math. 63 (2003), 97–107.

[10]   A. A. G. Ngurah, R. Simanjuntak and E. T. Baskoro, On the super edge-magic deficiencies of graphs, Australas. J. Combin. 40 (2008), 3–14.

[11]   G. Santhosh and G. Singh, A note on the super edge-magic deficiency of graphs, Far East J. Appl. Math. 24 (2006), 233–242.