DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 23(1) (2003) 67-83
DOI: 10.7151/dmgt.1186

VERTEX-ANTIMAGIC TOTAL LABELINGS OF GRAPHS

Martin Bača

Department of Applied Mathematics
Technical University, 04200 Košice, Slovak Republic
e-mail: Martin.Baca@tuke.sk

James A. MacDougall

Department of Mathematics
University of Newcastle, NSW 2308, Australia
e-mail: jmacd@math.newcastle.edu.au

François Bertault

Department of Computer Science and Software Engineering
University of Newcastle, NSW 2308, Australia
e-mail: francois@cs.newcastle.edu.au

Mirka Miller, Rinovia Simanjuntak and Slamin

Department of Computer Science and Software Engineering
University of Newcastle, NSW 2308, Australia
e-mail: mirka@cs.newcastle.edu.au, rino@cs.newcastle.edu.au,
slamin@cs.newcastle.edu.au

Abstract

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.

Keywords: super-magic labeling, (a,d)-vertex-antimagic total labeling, (a,d)-antimagic labeling.

2000 Mathematics Subject Classification: 05C78, 05C05, 05C38. 

 

Open problem 1 For the paths Pn and the cycles Cn, 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.

References

[1] M. Bača, I. Holländer and Ko-Wei Lih, Two classes of super-magic quartic graphs, JCMCC 13 (1997) 113-120.
[2] M. Bača and I. Holländer, On (a,d)-antimagic prisms, Ars. Combin. 48 (1998) 297-306.
[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).
[4] M. Doob, Generalizations of magic graphs, J. Combin. Theory (B) 17 (1974) 205-217, doi: 10.1016/0095-8956(74)90027-6.
[5] J.A. Gallian, A dynamic survey of graph labeling, Electronic. J. Combin. 5 (1998) #DS6.
[6] N. Hartsfield and G. Ringel, Pearls in Graph Theory (Academic Press, Boston-San Diego-New York-London, 1990).
[7] R.H. Jeurissen, Magic graphs, a characterization, Report 8201 (Mathematisch Instituut, Katholieke Universiteit Nijmegen, 1982).
[8] S. Jezný and M. Trenkler, Charaterization of magic graphs, Czechoslovak Math. J. 33 (1983) 435-438.
[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.
[10] J.A. MacDougall, M. Miller, Slamin, and W.D. Wallis, Vertex-magic total labelings of graphs, Utilitas Math., to appear.
[11] M. Miller and M. Bača, Antimagic valuations of generalized Petersen graphs, Australasian J. Combin. 22 (2000) 135-139.
[12] J. Sedlácek, Problem 27 in Theory of Graphs and its Applications, Proc. Symp. Smolenice, June 1963, Praha (1964), p. 162.
[13] B.M. Stewart, Supermagic complete graphs, Can. J. Math. 19 (1967) 427-438, doi: 10.4153/CJM-1967-035-9.
[14] W.D. Wallis, E.T. Baskoro, M. Miller and Slamin, Edge-magic total labelings of graphs, Australasian J. Combin. 22 (2000) 177-190.
[15] D.B. West, An Introduction to Graph Theory (Prentice-Hall, 1996).

Received 15 June 2001
Revised 20 October 2001