Some investigations on graph theory

Abstract

This thesis presents the results of investigation of certain fascinating problems in Graph Theory. The results are presented with appropriate theoreti-cal explanations. The whole work is divided into eight chapters. CHAPTER - 1: This is the introductory chapter in which history of Graph Theory is traced back to the pioneer workers Leonhard Euler, G.Kirchhoff, A. Cayley, C.Jordon and May . K. O. The brilliant exploits of Leonhard Euler in 1736 is cited and it is followed by the intr-oduction of some of the works of other distinguished mathematicians. Towards the middle of the chapter, various applications of graph theory are cited.The chapter ends with a detailed statement of the unsol-ved problems of Graph Theory. CHAPTER - 2: This chapter is dedicated to the theoretical investig-ations of isomorphism of Hamiltonian Graphs .In this chapter, we have formulated the following conjecture to prove some theorems of the chapter defining a Reduced Graph. A subgraph GR of a simple graph G is said to be a Reduced Graph of G if GR is obtained by deleting some edges of G in such a way that the subgraph GR is isomorphic to the Hamiltonian Graph of the symmetric group Sn for ngt3. CONJECTURE: For the symmetric group Sn for ngt3, there exists (n-1) ! Hamiltonian Graphs having only one Hamiltonian Circuit of length n. THEOREM(2.1): Two Hamiltonian Graphs G and H are isomorphic to each other if and only if they have equal number of Reduced Graphs. THEOREM(2.2) : The Reduced Graph GR of any Hamiltonian Graph G is two / three colorable if the vertices of G are even or odd. We have also forwarded an algorithm to study the isomorphism of any two graphs . In its support, some verifications are also included. ALGORITHM(2.3): INPUT: We have considered only two graphs G and H. OUTPUT: We shall find whether they are isomorphic or not. CHAPTER - 3: In this chapter, we have developed a heuristic method to establish the travelling salesman problem on the basis of some simple theorems mentioned below. Further, a verification has also been cited