Face Labelings of Graphs Embedded on the Surface of a Sphere or a Torus

Abstract

The thesis deals with the problem of labeling the vertices, edges and faces of a plane graphs by the consecutive integers in such a way that the label of a face and the labels of the vertices and edges surrounding that face all together add up to a weight of that face. If these face weights form an arithmetic progression with common difference d then the labeling is called d-antimagic. Such a labeling is called super if the smallest possible labels appear on the vertices. The thesis examines the existence of such labelings for toroidal fullerenes, gener- alized prism and disjoint union of generalized prisms. The toroidal fullerene is a 2-colorable cubic graph, there exist a 1-factor (perfect matching) and a 2-factor (a collection of n cycles on 2m vertices each). First we label the vertices of toroidal fullerene and then we label the edges of a 1-factor by consecutive integers and then in successive steps we label the edges of 2m-cycles (respectively 2n-cycles) in a 2-factor by consecutive integers. This technique allows us to construct super d-antimagic labelings of type (1, 1, 1) of toroidal fullerenes for several values of d. We consider the generalized prism as a collection of two classes of cycles: the main cycles and the middle cycles. To label the main cycles and the middle cycles we use the super (a, d)-edge-antimagic total and (a, d)-edge-antimagic total labelings and combine these labelings to a resulting super d-antimagic labeling of type (1, 1, 1). The disjoint union of generalized prism can be considered as a collection of disjoint union of main cycles and disjoint union of middle cycles. To label the disjoint union of main and middle cycles we again use edge-antimagic total labelings and super edge- antimagic total labelings. Combining these labelings we obtain a resulting super d-antimagic labeling of type (1, 1, 1) for a given diference d.