On Magic Graph Labelings
Master Thesis at UMD.
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 two magic type labelings.
A vertex magic total labeling assigns distinct consecutive integers starting at 1 to both vertices and edges so that the sum
λ(x) + Σy ∈ N(x) λ(xy)is constant for all vertices in the graph. We give labelings for certain product related graphs such as "drums" and products of complete graphs and cycles.
Often a "patter" plays an important role in constructing a vertex magic total labeling of regular graphs. Probably the most common pattern is a vertex antimagic total labeling. A vertex antimagic total labeling has the same properties as vertex magic total labelings except that we require the sums to be different, preferably constituting an arithmetic progression. We prove some new general results on vertex antimagic total labelings and build up a rich collection of antimagic labelings of cycles. They will prove to be useful in later sections for constructing vertex magic total labelings of products of graphs.