Super (a, d)-edge-antimagic total labelings of complete bipartite graphs

Abstract

An (a, d)-edge-antimagic total labeling of a graph G is a bijection f from V (G) ∪ E(G) onto {1, 2, . . . , |V (G)| +|E(G)|} with the property that the edge-weight set {f(x) + f(xy) + f(y) | xy ∈ E(G)} is equal to {a, a + d, a + 2d, . . . , a + (|E(G)| − 1)d} for two integers a>0 and d≥0. An (a, d)-edgeantimagic total labeling is called super if the smallest possible labels appear on the vertices. In this paper, we completely settle the problem of the super (a, d)-edge-antimagic total labeling of the complete bipartite graph Km,n and obtain the following results: the graph K_m,n has a super (a, d)-edge-antimagic total labeling if and only if either (i) m = 1, n = 1, and d≥0, or (ii) m = 1, n≥2 (or n= 1 and m≥2), and d ∈ {0, 1, 2}, or (iii) m = 1, n = 2 (or n = 1 and m = 2), and d = 3, or (iv) m, n≥2, and d= 1.

Key words： Graph K_m,n; ; super (a; d)-edge-antimagic total labeling; matrix

References

1 Băca M, Barrientos C. On super edge-antimagic total labelings of mK_n. Discrete Math, 2008, 308: 5032–5037

2 Băca M, Kov´aˇr P, Semaniˇcov´a-Fěnovˇćıkov´a A, Shafiq M K. On super (a, 1)-edgeantimagic total labelings of regular graphs. Discrete Math, 2010, 310: 1408–1412

3 Băca M, Lin Y, Miller M, Simanjuntak R. New constructions of magic and antimagic graph labelings. Util Math, 2001, 60: 229–239

4 Băca M, Lin Y, Miller M, Youssef M Z. Edge-antimagic graphs. Discrete Math, 2007, 307: 1232–1244

5 Băca M, Lin Y, Muntaner-Batle F A. Super edge-antimagic labelings of the path-like trees. Util Math, 2007, 73: 117–128

6 Dafik, Miller M, Ryan J, Băca M. On super (a, d)-edge-antimagic total labeling of disconnected graphs. Discrete Math, 2009, 309: 4909–4915

7 Enomoto H, Llad´o A S, Nakamigawa T, Ringel G. Super edge-magic graphs. SUT J Math, 1998, 34: 105–109

8 Figueroa-Centeno R M, Ichishima R, Muntaner-Batle F A. The place of super edgemagic labelings among other classes of labelings. Discrete Math, 2001, 231: 153–168

9 Gallian J A. A dynamic survey of graph labelings. Electron J Combin, 2013, 16: # DS6, http://www.combinatorics.org/surveys/ds6.pdf

10 Kotzig A, Rosa A. Magic valuations of finite graphs. Canad Math Bull, 1970, 13: 451–461

11 Simanjuntak R, Bertault F, Miller M. Two new (a, d)-antimagic graph labelings. In: Proceedings of 11th Australian Workshop of Combinatorial Algorithm. 2000, 179–189

12 Sugeng K A, Miller M, Slamin M, Băca. (a, d)-edge-antimagic total labelings of caterpillars. Lecture Notes in Comput Sci, Vol 3330. Berlin: Springer, 2005, 169–180