Course

Unit I

Graphs and Sub graphs, isomorphism, matrices associated with graphs, degrees, walks, paths, connected graphs, Euler graph, Hamilton graphs, shortest path algorithm.

Unit II

Trees: Trees, cut-edges and cut-vertices, spanning trees, Cayley’s formula, minimum spanning trees, DFS, BFS algorithms. Connectivity: Graph connectivity, k-connected graphs and blocks.

Unit III

Colorings: Vertex colorings, greedy algorithm and its consequences. Edge-colorings, Vizing theorem on edge-colorings. Planar graphs: Euler formula.

Unit IV

Some Essential Problems, Binomial Coefficients, Multinomial Coefficients, Pigeonhole Principle, Principle of Inclusion and Exclusion.
Generating Functions, Double Decks, Counting with Repetition, Fibonacci Numbers, Recurrence Relations.

Unit V

Polya’s Theory of Counting, Permutation Groups, Burnside’s Lemm, Cycle Index. Polya’s Enumeration Formula, deBruijn’s generalization.

Course Description  

This course demonstrates the knowledge of fundamental concepts in graph theory. Students will be able to use graphs to solve real life problems. This helps students to develop efficient algorithms for graph related problems in different domains of engineering and science.  

Course Objectives 

• To understand and apply the fundamental concepts in graph theory. 
• To learn computational algorithms.
• To develop fundamental knowledge of combinatorics and complexity. 

Course Outcomes 

CO-PO Mapping 

Prerequisites 

• Discrete Mathematics 
• Linear Algebra 
• Mathematical proof technique (induction, proof by contradiction) 

• J. A. Bondy and U. S. R. Murty, Graph Theory and Applications, Springer, 2008.
• Richard A. Brualdi, Introductory Combinatorics, Pearson, 2012
• D. B. West, Introduction to Graph Theory, P.H.I. 2010.
• J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001.
• Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998.