Vertex-antimagic total labelings of graphs

• Autorzy: Martin Bača , James A. MacDougall , François Bertault , Mirka Miller , Rinovia Simanjuntak , Slamin
• Języki publikacji: EN

Abstrakty

EN

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.

EN

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

Słowa kluczowe

EN

super-magic labeling; (a,d)-vertex-antimagic total labeling; (a,d)-antimagic labeling

Kategorie tematyczne

• 05C05: Trees
• 05C38: Paths and cycles
• 05C78: Graph labelling (graceful graphs, bandwidth, etc.)

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2003
• Tom: 23
• Numer: 1
• Strony: 67-83

Daty

wydano

2003

otrzymano

2001-06-15

poprawiono

2001-10-20

Twórcy

autor

Martin Bača

• Department of Applied Mathematics, Technical University, 04200 Košice, Slovak Republic

autor

James A. MacDougall

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

autor

François Bertault

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

autor

Mirka Miller

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

autor

Rinovia Simanjuntak

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

autor

Slamin

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

Bibliografia

• [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).

Identyfikatory

DOI

10.7151/dmgt.1186