Course Course
Name of Course L T P Credit
Type Code
OE CSO302 Graph Theory 3 0 0 9
Course Objective
To create interest, to familiarize the students with the important concepts, to develop their skills in the subject
Learning Outcomes
The students are expected to be able to deal with problems and challenges in the related fields both in academics and
industries
Unit Lecture
Topics to be Covered Learning Outcome
No. Hours
This introductory topics help students pick
Basic graph theoretical concepts, definitions,
up the basic knowledge and concepts to start
1 representation, related theorems, different types of 5
with the subject, to proceed with the more
graphs
complex concepts
students will pick up concepts about the
trees, spanning trees, Euler’s theorem, vertex and
2 4 special subgraphs with many applications in
edge connectivity, blocks,
related problems
the students will learn about special cycle
3 Hamiltonian and Euler graphs 5 and tours in graphs and will learn how to
detect them if they exist in a graph
Matching covering have extensive
Matching, covering, related theorem, SDR, Edge applications in problems that can be handled
4 7
coloring under the framework of graph theory and the
students will learn them
Independent set, clique, Ramsey theorem, vertex These are related and extended concepts of
5 5 topics in item 4 which the students will learn
coloring, critical graphs
planar graphs and related concepts are very
important in various problems like VLSI
6 Planar graphs, planarity testing, Directed graphs 4
and many others and the students will learn
them
The students will pick up concepts to
Strongly regular graphs, line graphs and eigen values, analyze graphs from a different perspective
7 6
Laplacian of graphs, cuts and flows, rank polynomial which is more inclined to algorithmic
treatments
Random and infinite graphs, Applications in biology The students will learn the application parts
8 4
and social sciences of the graph theory
Text Books:
1. Graph theory with applications by J.A. Bondy and U.S.R. Murty,
Elsevier
2. Algebraic graph theory by Chris Godsil and Gordon Royle, Springer
Reference Books:
1. Modern Graph Theory by Bela Bollobas, Springer
2. Introduction to Graph Theory by Douglas B West, PHI
