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

Books:

(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)