Course Details

Subject {L-T-P / C} : MA5128 : Graph Theory { 3-0-0 / 3}

Subject Nature : Theory

Coordinator : Dr. Hiranmoy Pal

Syllabus

Introduction to Graphs, Isomorphism, Directed graphs. Subgraphs: Spanning Subgraphs, Induced Subgraphs, vertex and edge deleted Subgraphs. Operations on graphs.

Walk, Trails and Paths, connected graphs, disconnected graphs, Bipartite graphs, Cycles, Euler Tour, Euler Trail, Euler graphs, Euler Theorem, Hamiltonian path, Hamiltonian graphs, Maximal non-Hamiltonian graphs, Dirac’s Theorem, Ore’s Theorem, complement graph, Trees, Spanning Trees.

Algorithms on graphs, shortest path Algorithms: Dijkstra’s Algorithm, Minimal Spanning Tree, Breadth First Search Algorithm, Depth First Search Algorithm.Matrix Representation of graphs, Incidence matrix, Adjacency Matrix, Laplacian Matrix, Eigenvalues of Adjacency and Laplacian Matrix.

Cut sets, Cut vertices, Edge connectivity, Vertex connectivity, Whitney’s Inequality, Colouring of graph, Chromatic number, Chromatic polynomial, Edge contraction, Plane and Planar graphs, Embedding and Regions, Kuratowski’s Two graphs K_5 and K_(3,3) , Euler’s Formula, Subdivision and Branch vertex, Kuratowski’s Theorem, Dual of a planar graph, Edge Coloring, Edge Chromatic number, Colouring planar graphs, The Four-Color Theorem, The Five-Colour Theorem.

Course Objectives

Course Outcomes

CO1: Students become familiar with the basic notions of graph theory. <br />CO2: They develop skills to apply the theorems and algorithms that are treated in the course for solving graph theoretical problems. <br />CO3: Students learn the connectivity and coloring problems, and their applications to various situations.

Essential Reading

Supplementary Reading