
Magic Labelings of GraphsTalk on the defence of my Ph.D. thesis at V©B  Technical University of Ostrava. AbstractA graph labeling is a mapping from the set of edges, vertices, or both to a set of labels. Usually the labels are positive integers. Magic labelings were introduced more than forty years ago by Sedláček. In this thesis we focus on three magictype labelings. A vertex magic total labeling λ assigns distinct consecutive integers starting at 1 to both vertices and edges of a given graph G so that the sum (weight)
w_{λ}(x) = λ(x) + Σ_{y ∈ N(x)} λ(xy)
is constant for all vertices in the graph.
Vertex antimagic total labelings require the weights to form an arithmetic progression.
Supermagic labelings assign labels only to edges of G and again we require the weight
w_{λ}(x) = Σ_{y ∈ N(x)} λ(xy)
to be equal for every vertex in G.
After a summary of known results we give a general result on (s,d)vertex antimagic total labelings of cycles. The notion of magic labelings is generalized to use labels from Z and generalized labelings are used to find vertex magic total labelings of products of regular graphs G × H. Often to construct one magictype labeling we use the same or a different magictype labeling of the graphs G and H of the product. Often a "pattern" plays an important role in constructing a vertex magic total labeling of regular graphs. The "patterns" which proved to be useful are based on Kotzig arrays. The second part of the thesis explores constructions based on Kotzig arrays of various magictype labelings of copies and products of regular graphs. If we find a decomposition of a graph G into certain magictype factors F_{i}, we can combine the known labelings of F_{i} to obtain a magictype labeling of G. Special cases of such general theorems are used to find vertex magic total labelings and supermagic labelings of compositions of graphs. A conjecture by MacDougall et al. says that any regular graph other than K_{2} or 2K_{3} is vertex magic total. In the last section we support the conjecture and give constructions of vertex magic total labelings for certain general classes of regular graphs. Talk given atTalk "On VMT Labelings of graphs", V©B  TU Ostrava, (20th December, 2004).
