ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

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

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 20(2) (2000) 219-229
DOI: 10.7151/dmgt.1121


Martin Bača

Department of Applied Mathematics
Technical University, Košice 042 00, Slovakia


J.A. MacDougall

Department of Mathematics
The University of Newcastle, NSW 2308, Australia


Mirka Miller

Department of Computer Science and Software Engineering
The University of Newcastle, NSW 2308, Australia



Department of Mathematical Education
Universitas Jember, Jember 68121, Indonesia


W.D. Wallis

Department of Mathematics
Southern Illinois University, Carbondale, IL 62901-4408, USA



The study of valuations of graphs is a relatively young part of graph theory. In this article we survey what is known about certain graph valuations, that is, labeling methods: antimagic labelings, edge-magic total labelings and vertex-magic total labelings.

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

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


[1] M. Bača and I. Holländer, On (a,d)-antimagic prisms, Ars Combinatoria 48 (1998) 297-306.
[2] M. Bača, Antimagic labelings of antiprisms, JCMCC, to appear.
[3] M. Bača, Special face numbering of plane quartic graphs, Ars Combinatoria, to appear.
[4] M. Bača, Face-antimagic labelings of convex polytopes, Utilitas Math. 55 (1999) 221-226.
[5] M. Bača, Consecutive-magic labeling of generalized Petersen graphs, Utilitas Math., to appear.
[6] M. Bača and Mirka Miller, Antimagic face labeling of convex polytopes based on biprisms, JCMCC, to appear.
[7] G.S. Bloom, A chronology of the Ringel-Kotzig conjecture and the continuing quest to call all trees graceful, Ann. N.Y. Acad. Sci. 326 (1979) 32-51, doi: 10.1111/j.1749-6632.1979.tb17766.x.
[8] G.S. Bloom and S.W. Golomb, Applications of numbered undirected graphs, Proc. IEEE 65 (1977) 562-570, doi: 10.1109/PROC.1977.10517.
[9] R. Bodendiek and G. Walther, Arithmetisch antimagische graphen, in: K. Wagner and R. Bodendiek, eds., Graphentheorie III (BI-Wiss.Verl., Mannheim, 1993).
[10] R. Bodendiek and G. Walther, On number theoretical methods in graph labelings, Res. Exp. Math. 21 (1995) 3-25.
[11] R. Bodendiek and G. Walther, On (a,d)-antimagic parachutes, Ars Combinatoria 42 (1996) 129-149.
[12] R. Bodendiek and G. Walther, On (a,d)-antimagic parachutes II, Ars Combinatoria 46 (1997) 33-63.
[13] M. Borowiecki and L.V. Quintas, Magic digraphs, in: 33. Intern. Wiss. Koll. TH Ilmenau (1988) 163-166.
[14] H. Enomoto, A.S. Llado, T. Nakamigawa and G. Ringel, Super edge-magic graphs, SUT J. Math. 2 (1998) 105-109.
[15] R. Frucht and J.A. Gallian, Labeling prisms, Ars Combinatoria 26 (1988) 69-82.
[16] J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Combinatorics 5 (1998) #DS6.
[17] N. Hartsfield and G Ringel, Pearls in Graph Theory (Academic Press, 1990).
[18] R.H. Jeurissen, Magic graphs, a characterization, Report 8201, Mathematisch Instituut, Katholieke Universiteit Nijmegen, 1982.
[19] S. Jezný and M. Trenkler, Characterization of magic graphs, Czechoslovak Math. J. 33 (1983) 435-438.
[20] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull. 13 (1970) 451-461, doi: 10.4153/CMB-1970-084-1.
[21] A. Kotzig and A. Rosa, Magic valuations of complete graphs, Publ. CRM 175 (1972).
[22] J.A. MacDougall, Mirka Miller, Slamin and W.D. Wallis, Vertex-magic total labellings of graphs, submitted.
[23] Mirka Miller, J.A. MacDougall, Slamin and W.D. Wallis, Problems in magic total graph labellings, in: Proceedings of the tenth AWOCA (1999) 19-25.
[24] Mirka Miller and M. Bača, Antimagic valuations of generalized Petersen graphs, Australasian J. Combin. 22 (2000) 135-139.
[25] Mirka Miller, M. Bača and Y. Lin, On two conjectures concerning (a,d)-antimagic labellings of antiprisms, JCMCC, to appear.
[26] Mirka Miller, M. Bača and J. A. MacDougall, Vertex-magic total labeling of the generalized Petersen graphs and convex polytopes, submitted.
[27] G. Ringel, Problem 25, Theory of Graphs and its Applications, in: Proc. Symposium Smolenice 1963 (Prague, 1964) 162.
[28] G. Ringel and A.S. Llado, Another tree conjecture, Bull. ICA 18 (1996) 83-85.
[29] A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs (Internat. Symposium, Rome, July 1966; Gordon and Breach, N.Y. and Dunod Paris, 1967) 349-355.
[30] J. Sedlácek, Problem 27, in: Theory of Graphs and its Applications, Proc. Symposium Smolenice 1963 (Prague, 1964) 163-164.
[31] B.M. Stewart, Supermagic complete graphs, Canad. J. Math. 19 (1967) 427-438, doi: 10.4153/CJM-1967-035-9.
[32] W.D. Wallis, E.T. Baskoro, Mirka Miller and Slamin, Edge-magic total labelings, submitted.
[33] M.E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969) 152-164, doi: 10.1016/S0021-9800(69)80116-X.
[34] D.B. West, An Introduction to Graph Theory (Prentice-Hall, 1996).

Received 22 November 1999
Revised 18 October 2000