JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Prerequisite:

• 1. An understanding of Mathematics in general is sufficient.

Course Outcomes:

• Know some important classes of graph theoretic problems;
• Be able to formulate and prove central theorems about trees, matching, connectivity, colouring and planar graphs;
• Be able to describe and apply some basic algorithms for graphs;
• Be able to use graph theory as a modelling tool.

UNIT - I

Introduction-Discovery of graphs, Definitions, Subgraphs, Isomorphic graphs, Matrix representations of graphs, Degree of a vertex, Directed walks, paths and cycles, Connectivity in digraphs, Eulerian and Hamilton digraphs, Eulerian digraphs, Hamilton digraphs, Special graphs, Complements, Larger graphs from smaller graphs, Union, Sum, Cartesian Product, Composition, Graphic sequences, Graph theoretic model of the LAN problem, Havel-Hakimi criterion, Realization of a graphic sequence.

UNIT - II

Connected graphs and shortest paths - Walks, trails, paths, cycles, connected graphs, Distance, Cut-vertices and cut-edges, Blocks, Connectivity, Weighted graphs and shortest paths, Weighted graphs, Dijkstra‟s shortest path algorithm, Floyd-Warshall shortest path algorithm.

UNIT - III

Trees- Definitions and characterizations, Number of trees, Cayley’s formula, Kircho-matrix- tree theorem, Minimum spanning trees, Kruskal’s algorithm, Prim’s algorithm, Special classes of graphs, Bipartite Graphs, Line Graphs, Chordal Graphs, Eulerian Graphs, Fleury’s algorithm, Chinese Postman problem, Hamilton Graphs, Introduction, Necessary conditions and sufficient conditions.

UNIT - IV

Independent sets coverings and matchings– Introduction, Independent sets and coverings: basic equations, Matchings in bipartite graphs, Hall‟s Theorem, K¨onig‟s Theorem, Perfect matchings in graphs, Greedy and approximation algorithms.

R16 B.TECH CSE.

UNIT - V

Vertex Colorings- Basic definitions, Cliques and chromatic number, Mycielski’s theorem, Greedy coloring algorithm, Coloring of chordal graphs, Brooks theorem, Edge Colorings, Introduction and Basics, Gupta-Vizing theorem, Class-1 and Class-2 graphs, Edge-coloring of bipartite graphs, Class-2 graphs, Hajos union and Class-2 graphs, A scheduling problem and equitable edge-coloring.

TEXTBOOKS:

• 1. J. A. Bondy and U. S. R. Murty. Graph Theory, volume 244 of Graduate Texts in Mathematics. Springer, 1st edition, 2008.
• 2. J. A. Bondy and U. S. R. Murty. Graph Theory with Applications.

REFERENCES:

• 1. Lecture Videos: http://nptel.ac.in/courses/111106050/13
• 2. Introduction To Graph Theory, Douglas B. West, Pearson.
• 3. Schaum's Outlines Graph Theory, Balakrishnan, TMH
• 4. Introduction to Graph Theory, Wilson Robin j, PHI
• 5. Graph Theory with Applications to Engineering and Computer Science, Narsing Deo, PHI
• 6. Graphs - An Introductory Approach, Wilson and Watkins R16 B.TECH CSE.