A Study on Labeling and Coloring of Various Classes of Graphs

Abstract

Graph Theory is still young even though it has experienced developments during the last sixty years. It has lot of applications in many areas of computing, social and natural sciences. There are many diversity concepts in graph theory and hence the research on this subject depends on the popularity of applications and the techniques used to analyze the problems. This popularity is not only due to the mathematical challenges but also the focus on understanding the structure of graphs. In particular the concept of labeling of graphs has wide range of applications to coding theory, circuit design, network design and communication problems. This new branch of mathematics has caught the attention of many authors and many new labeling results appear every year. Nowadays, the study of graph labeling includes abundance of different types of labeling. By a labeling we mean an assignment of integers to the vertices or edges or both subject to certain conditions. We distinguish several classes of labeling by the domain. If the domain of the mapping is the vertex set or the edge set, the labeling is called vertex labeling or edge labeling, respectively. If the domain of the mapping is the set of vertices and edges, then the labeling is called the total labeling. newlineGraph labeling were first introduced in the late 1960 s. Many studies in Graph labeling refer to Rosa s research in 1967and Golomb s research in 1972. Sedlacek [1976] and Stewart [1966] also contributed many research works on graph labeling. However, still there exists, many interesting open problems and conjectures. A dynamic survey of graph labeling by Gallian [2020] presents an exhaustive result on graph labeling. There are different kinds of labeling such as graceful labeling, magic labeling, and prime labeling etc. newlineThe geometric ideas involved in mathematics are very useful in the coloring of graphs, and the classes of graphs, for which the different kinds of graph labeling play an important role. Hence our topic of research brings out results on in these resear