In this paper we introduce a new type of graph labeling for a graph G(V,E) called an (a,d)-vertex-antimagic total labeling. In this labeling we assign to the vertices and edges the consecutive integers from 1 to |V|+|E| and calculate the sum of labels at each vertex, i.e., the vertex label added to the labels on its incident edges. These sums form an arithmetical progression with initial term a and common difference d. We investigate basic properties of these labelings, show their relationships with several other previously studied graph labelings, and show how to construct labelings for certain families of graphs. We conclude with several open problems suitable for further research.
Open problem 1. For the paths Pₙ and the cycles Cₙ, determine if there is a vertex-antimagic total labeling for every feasible pair (a,d). Open problem 2. Apart from duality, how can a vertex-antimagic total labeling for a graph be used to construct another vertex-antimagic total labeling for the same graph, preferably with different a and d? Open problem 3. In Theorem 3, we found a way to construct VATL for a graph G from a vertex-magic total labeling of G. Are there other ways to do this? Open problem 4. Find, if possible, some structural characteristics of a graph which make a vertex-antimagic total labeling impossible
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1186,
author = {Martin Ba\v ca and James A. MacDougall and Fran\c cois Bertault and Mirka Miller and Rinovia Simanjuntak and Slamin},
title = {Vertex-antimagic total labelings of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {23},
year = {2003},
pages = {67-83},
zbl = {1054.05086},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1186}
}
Martin Bača; James A. MacDougall; François Bertault; Mirka Miller; Rinovia Simanjuntak; Slamin. Vertex-antimagic total labelings of graphs. Discussiones Mathematicae Graph Theory, Tome 23 (2003) pp. 67-83. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1186/
[000] [1] M. Bača, I. Holländer and Ko-Wei Lih, Two classes of super-magic quartic graphs, JCMCC 13 (1997) 113-120. | Zbl 0876.05085
[001] [2] M. Bača and I. Holländer, On (a,d)-antimagic prisms, Ars. Combin. 48 (1998) 297-306.
[002] [3] R. Bodendiek and G. Walther, Arithmetisch antimagische graphen, in: K. Wagner and R. Bodendiek, Graphentheorie III, (BI-Wiss. Verl., Mannheim-Leipzig-Wien-Zürich, 1993).
[003] [4] M. Doob, Generalizations of magic graphs, J. Combin. Theory (B) 17 (1974) 205-217, doi: 10.1016/0095-8956(74)90027-6. | Zbl 0271.05128
[004] [5] J.A. Gallian, A dynamic survey of graph labeling, Electronic. J. Combin. 5 (1998) #DS6. | Zbl 0953.05067
[005] [6] N. Hartsfield and G. Ringel, Pearls in Graph Theory (Academic Press, Boston-San Diego-New York-London, 1990). | Zbl 0703.05001
[006] [7] R.H. Jeurissen, Magic graphs, a characterization, Report 8201 (Mathematisch Instituut, Katholieke Universiteit Nijmegen, 1982). | Zbl 0657.05065
[007] [8] S. Jezný and M. Trenkler, Charaterization of magic graphs, Czechoslovak Math. J. 33 (1983) 435-438. | Zbl 0571.05030
[008] [9] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull. 13 (1970) 451-461, doi: 10.4153/CMB-1970-084-1. | Zbl 0213.26203
[009] [10] J.A. MacDougall, M. Miller, Slamin, and W.D. Wallis, Vertex-magic total labelings of graphs, Utilitas Math., to appear. | Zbl 1008.05135
[010] [11] M. Miller and M. Bača, Antimagic valuations of generalized Petersen graphs, Australasian J. Combin. 22 (2000) 135-139. | Zbl 0971.05098
[011] [12] J. Sedlácek, Problem 27 in Theory of Graphs and its Applications, Proc. Symp. Smolenice, June 1963, Praha (1964), p. 162.
[012] [13] B.M. Stewart, Supermagic complete graphs, Can. J. Math. 19 (1967) 427-438, doi: 10.4153/CJM-1967-035-9. | Zbl 0162.27801
[013] [14] W.D. Wallis, E.T. Baskoro, M. Miller and Slamin, Edge-magic total labelings of graphs, Australasian J. Combin. 22 (2000) 177-190. | Zbl 0972.05043
[014] [15] D.B. West, An Introduction to Graph Theory (Prentice-Hall, 1996). | Zbl 0845.05001