Analysis of various graph labeling techniques

Abstract

quotBackground: The first paper in the history of graph theory was Seven Bridges of Konigsberg by Leonhard Euler, which was published in 1736. The term graph was rst used by Sylvester in a paper which was published in 1878 in Nature. The first textbook on graph theory was written by Denes Konig and was published in 1936. Another book by Frank Harary was published in 1969, which is used widely in the study of graph theory. Most graph labeling techniques trace their origin to labeling presented by Rosa in1967. One of the important areas in graph theory is Graph Labeling used in many applications like coding theory, x-ray crystallography, radar, astronomy, circuit design, communication network addressing, data base management. Moreover it is also used in important newlinemajor areas of computer science like data mining, image processing, cryptography, software testing, information security, communication networks. newline newlineAim: To analyze the various existing graph labeling techniques and then to discover several new graph families which satisfy the essential conditions for specic labeling. Further to obtain new graph labeling techniques and to discuss about dierent graph families satisfying conditions of these new labelings is one of the prime aim of this research work. newline newlineMaterials and Methods: For the presented research work, initially reading of books and analysis of papers for the corresponding concepts were adopted. Then after case study, observation and modication methods were used for further research work. Combinatorial and induction methods have also been used for verication of labeling pattern in various graphs. newline newlineResults and Discussion: This thesis is made up to analyze various graph labeling techniques like Cordial labeling, 3-equitable labeling, Permutation labeling and Square sum labeling. Some new graphs and its families have been discovered for cordial, 3-equitable and permutation labeling related to some graph operations like Join of graphs, Star of a graph and Union of graphs. A new graph called Halfwheel and a new la