
Syllabus
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