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