Magic Labelings of Graphs
Talk on the defence of my Ph.D. thesis at V©B - Technical University of Ostrava.
A 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 magic-type 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 magic-type labeling we use the same or a different magic-type 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 magic-type labelings of copies and products of regular graphs.
If we find a decomposition of a graph G into certain magic-type factors Fi, we can combine the known labelings of Fi to obtain a magic-type 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 K2 or 2K3 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 at
Talk "On VMT Labelings of graphs", V©B - TU Ostrava, (20th December, 2004).