Download Syllabus in PDF format
Untitled Document
COURSE OUTLINE
Preliminaries: Graphs, isomorphism, subgraphs, 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
Special classes of graphs: Bipartite graphs, line graphs, chordal graphs
Eulerian graphs: Characterization, Fleury’s algorithm, chinese-postman-problem
Hamilton graphs: Necessary conditions and sufficient conditions
Independent sets, coverings, matchings: Basic equations, matchings in bipartite graphs, perfect matchings, greedy and approximation algorithms
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
Planar graphs: Basic concepts, Eulers formula, polyhedrons and planar graphs, charactrizations, planarity testing, 5-color-theorem
Directed graphs: Out-degree, in-degree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments
COURSE DETAIL
Modules
Contents (optional topics are indicated in red)
Number of lectures
Number of lectures by skipping
optional topics
1 Preliminaries
Graphs, isomorphism, subgraphs, matrix representations, degree, operations on graphs, degree sequences
5-10
4
2 Connected graphs and shortest paths
Walks, trails, paths, connected graphs, distance, cut-vertices, cut-edges, blocks, weighted graphs, connectivity, Dijkstra’s shortest path algorithm, Floyd-Warshall shortest path algorithm
4-8
4
3 Trees
Characterizations, number of trees , minimum spanning trees
5-10
4
4 Special classes of graphs
Bipartite graphs, line graphs, chordal graphs
6-12
2
5 Eulerian graphs
Characterization, Fleury’s algorithm, chinese-postman-problem
2-4
2
6 Hamilton graphs
Necessary conditions and sufficient conditions
4-8
4
7 Independent sets, coverings and mathcings
Basic equations, matchings in bipartite graphs, perfect matchings, greedy and approximation algorithms
8-16
6
8 Vertex-colorings
Chromatic number and cliques, greedy coloring algorithm, coloring of chordal graphs, Brook’s theorem
4-8
2
9 Edge-colorings
Gupta-Vizing theorem, Class-1 graphs and class-2 graphs, equitable edge-coloring
8-16
6
10 Planar graphs
Basic concepts, Eulers formula, polyhedrons and planar graphs, charactrizations, planarity testing,
5-color-theorem
10-20
3
11 Directed graphs
Directed graph, underlying graph, out-degree, in-degree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments
8-16
6
REFERENCES
Text Books :
J.A. Bondy and U.S.R.Murty: Graph Theory and Applications ( Freely downloadable from Bondy's website; Google-Bondy)
D.B.West: Introduction to Graph Theory, Prentice-Hall of India/Pearson, 2009 ( latest impression)
Reference Books:
J.A.Bondy and U.S.R.Murty: Graph Theory, Springer, 2008.
R.Diestel: Graph Theory, Springer( low price edition) 2000.
ADDITIONAL READINGS
F.Harary: Graph Theory, Narosa, (1988)
C. Berge: Graphs and Hypergraphs, North Holland/Elsevier, (1973)