Graph Theory and Its Applications (GT)

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      gorithm, 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,             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