UNIT-I
Preliminaries: Graphs, isomorphism, sub graphs, matrix representations, degree, operations on graphs, degree sequences. Connected graphs and shortest paths: Walks, trails, paths, connected graphs, distance, cut-vertices, cut-edges, blocks, connectivity, weighted graphs, shortest path algorithms Trees: Characterizations, number of trees, minimum spanning trees
UNIT-II
Special classes of graphs: Bipartite graphs, line graphs, chordal graphs
Eulerian graphs: Characterization, Fleury’s algorithm, chinese-postman-problem
UNIT-III
Hamilton graphs: Necessary conditions and sufficient conditions Independent sets, coverings, matchings: Basic equations, matching sin bipartite graphs, perfect matchings, greedy and approximation algorithms
UNIT-IV
Vertex colorings: Chromatic number and cliques, greedy coloring algorithm, coloring of chordal graphs, Brook’s theorem
Edge colorings: Gupta-Vizing theorem, Class-1 graphs and class-2 graphs, equitable edge-coloring
UNIT-V
Planar graphs: Basic concepts, Euler’s formula, polyhedrons and planar graphs, characterizations, planarity testing, 5-color-theorem.
Directed graphs: Out-degree, in-degree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments
Suggested Reading:
1. F. Harry, Graph theory, Narosa Publications, 1988.
2. C.Berge: Graphs and Hypergraphs, North-Holland/Elsevier, 1973
3. J A Bondy and U.S. R Murthy, Graph Theory with Applications, Elsevier Science Ltd, 1976.
4. Douglas B West, Introduction to Graph Theory, Prentice-Hall, 2004