Partial Solutions To Certain Graph Labeling Open Problems

Abstract

A distance magic labeling of a graph G with n vertices, is a bijective function l from newlinethe vertex set of G to a set of first n natural numbers 1,2, · · · ,n with the property that newlinethe weight of each vertex is the same, where the weight of a vertex v of G is defined newlineto be the sum of all the labels of vertices adjacent to v in G. newlineThe thesis mainly deals with partial solutions to certain problems posted during newline2004 to 2018 in the area of distance magic labeling of graphs. Counting the number newlineof distance magic labelings of a distance magic graph, existence of the group distance newlinemagicness of the lexicographic and direct product of a non-regular graph with a newlinebalanced distance magic graph, determining the distance magic index of infinitely newlinemany classes of graphs and scheduling the possible spectrum of handicap incomplete newlinetournaments are some non-trivial problems that are dealt with in this thesis. newlineVarious elements and sub-structures of algebraic graph theory are used to compute newlinethe number of possible distance magic labelings of a distance magic graph, which is newlineunsolved for the last 16 years. newlineCombinatorial objects namely, magic squares, magic rectangles, and Kotzig newlinearrays play a vital role to define labelings at different levels of the proofs in the newlinechapters in this thesis. Certain new combinatorial objects namely, quasi magic newlinerectangles and lifted quasi Kotzig arrays are introduced and studied. These objects newlineare handy tools to solve various problems in magic type labelings of graphs. In newlineparticular, quasi magic rectangles are used effectively to determine the distance newlinemagic index of infinitely many regular graphs. newlineCertain concepts in additive group theory namely, exponent of group, order of newlineelements and their algebraic inter-relationships are effectively, used to solve certain newlineproblems in the area of group distance magicness of graphs.