Download PDF - Survey of certain valuations of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Survey of certain valuations of graphs

Authors 1, 2, 3, 4, 5

Affiliations

  1. Department of Applied Mathematics, Technical University, Košice, Slovakia
  2. Department of Mathematics, The University of Newcastle, Australia
  3. Department of Computer Science and Software Engineering, The University of Newcastle, Australia
  4. Department of Mathematical Education, Universitas Jember, Indonesia
  5. Department of Mathematics, Southern Illinois University, USA

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

ENG
(a,d)-antimagic labeling, (a,d)-face antimagic labeling, edge-magic total labeling, vertex-magic total labeling

Bibliography

  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).
Discussiones Mathematicae Graph Theory
2000/20/2
Export to PBN, Opens in new tab
Pages:
219-229
Main language of publication
English
Received
1999-11-22
Accepted
2000-10-18
Published
2000

DOI: 10.7151/dmgt.1121

Exact and natural sciences