MA6230 GRAPH THEORY
Basics: subgraphs, isomorphism, automorphism group, matrices associated with graphs, degrees, walks, connected graphs, shortest path algorithms.
Bipartite graphs: characterization, trees, cut-edges and cut-vertices, spanning trees, minimum spanning trees, DFS, BFS algorithms
Connectivity: k-connected graphs, characterization of 2-connected graphs
Euler and Hamilton graphs: characterization of Euler graphs, necessary/ sufficient conditions for the existence of Hamilton cycles, Fleury's algorithm for eulerian trails, Chinese-postman-problem (complete algorithmic solution), approximate solutions of traveling salesman problem
Matchings: Berge's theorem, Hall's theorem, Tutte’s perfect matching theorem, k-matchings (reduction to perfect matching problem), job-assignment- problem
(1) J.A. Bondy and U.S.R. Murty: Graph Theory and Applications (Freely downloadable from Bondy's website)
(2) D.B. West: Introduction to graph theory, P.H.I. (2004)