Please use this identifier to cite or link to this item:
Title: Some investigations on graph theory
Researcher: Kalita, Bichitra
Guide(s): Baruah, Hemata Kumar
Keywords: Conjecture
University: Gauhati University
Completed Date: 31/12/2000
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
Appears in Departments:Department of Mathematics

Files in This Item:
File Description SizeFormat 
01_title page.pdfAttached File25.95 kBAdobe PDFView/Open
02_content.pdf66.12 kBAdobe PDFView/Open
03_certificate.pdf66.77 kBAdobe PDFView/Open
04_declaration.pdf19.04 kBAdobe PDFView/Open
05_acknowledgement.pdf48.94 kBAdobe PDFView/Open
06_abstract.pdf162.39 kBAdobe PDFView/Open
07_chapter 1.pdf225.09 kBAdobe PDFView/Open
08_chapter 2.pdf647.34 kBAdobe PDFView/Open
09_chapter 3.pdf467.05 kBAdobe PDFView/Open
10_chapter 4.pdf536.94 kBAdobe PDFView/Open
11_chapter 5.pdf643.17 kBAdobe PDFView/Open
12_chapter 6.pdf433.61 kBAdobe PDFView/Open
13_chapter 7.pdf1.05 MBAdobe PDFView/Open
14_chapter 8.pdf556.59 kBAdobe PDFView/Open

Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.