DMGT

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

SURVEY OF CERTAIN VALUATIONS OF GRAPHS

Martin Bača

Department of Applied Mathematics
Technical University, Košice 042 00, Slovakia
e-mail: hollbaca@tuke.sk

J.A. MacDougall

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

Mirka Miller

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

Slamin

Department of Mathematical Education
Universitas Jember, Jember 68121, Indonesia
e-mail: slamin@cs.newcastle.edu.au

W.D. Wallis

Department of Mathematics
Southern Illinois University, Carbondale, IL 62901-4408, USA
e-mail: wdwallis@math.siu.edu

Abstract

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.

References

[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