STUDY ON LABELING OF CERTAIN CLASS OF GRAPHS

Abstract

A graph is a collection of nodes and lines that we call vertices and edges, respectively. A graph can be labeled or unlabeled. In this thesis, we are interested in labeled graphs. In many labeled graphs, the labels are used for identification only. The kind of labeling we are interested in can serve dual purposes: Labeling can be used not only to identify vertices and edges, but also to signify some additional properties, depending on the particular labeling. The study of graph theory was born in the 18th century when the citizens of Konigsberg tried to solve the problem of traversing the 7 bridges on the Pregel river. They wondered if they could walk and cross every bridge exactly once and finish back at the starting point. Using graph representation, the well known mathematician Euler found that it is impossible to do it. However, it is fair to say that the formal and systematical study of graph theory began with D. Konig's book in 1935.