Czasopismo
Tytuł artykułu
Treść / Zawartość
Pełne teksty:
Warianty tytułu
Języki publikacji
Abstrakty
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.
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.
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
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
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
67-83
Opis fizyczny
Daty
wydano
2003
otrzymano
2001-06-15
poprawiono
2001-10-20
Twórcy
autor
- Department of Applied Mathematics, Technical University, 04200 Košice, Slovak Republic
autor
- Department of Mathematics, University of Newcastle, NSW 2308, Australia
autor
- Department of Computer Science and Software Engineering, University of Newcastle, NSW 2308, Australia
autor
- Department of Computer Science and Software Engineering, University of Newcastle, NSW 2308, Australia
autor
- Department of Computer Science and Software Engineering, University of Newcastle, NSW 2308, Australia
autor
- 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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1186