GRAPH THEORY (BCS405B)

GRAPH THEORY

Course Code BCS405B 
CIE Marks 50
Teaching Hours/Week (L:T:P: S) 2:2:0:0 
SEE Marks 50
Total Hours of Pedagogy 40 
Total Marks 100
Credits 03 
Exam Hours 03
Examination type (SEE) Theory

Module-1

Introduction to Graphs: Introduction- Basic definition – Application of graphs – finite, infinite and

bipartite graphs – Incidence and Degree – Isolated vertex, pendant vertex and Null graph. Paths

and circuits – Isomorphism, sub-graphs, walks, paths and circuits, connected graphs,

disconnected graphs and components. (8 hours)

(RBT Levels: L1, L2 and L3)

Module-2

Eulerian and Hamiltonian graphs: Euler graphs, Operations on graphs, Hamiltonian paths and

circuits, Travelling salesman problem. Directed graphs – types of digraphs, Digraphs and binary

relation. (8 hours)

(RBT Levels: L1, L2 and L3)

Module-3

Trees – properties, pendant vertex, Distance and centres in a tree - Rooted and binary trees,

counting trees, spanning trees.

Connectivity Graphs: Vertex Connectivity, Edge Connectivity, Cut set and Cut Vertices,

Fundamental circuits. (8 hours)

(RBT Levels: L1, L2 and L3)

Module-4

Planar Graphs: Planar graphs, Kuratowski’s theorem (proof not required), Different

representations of planar graphs, Euler's theorem, Geometric dual.

Graph Representations: Matrix representation of graphs-Adjacency matrix, Incidence Matrix,

Circuit Matrix, Path Matrix. (8 hours)

 (RBT Levels: L1, L2 and L3)

Module-5:

Graph Colouring: Colouring- Chromatic number, Chromatic polynomial, Matchings, Coverings,

Four colour problem and Five colour problem. Greedy colouring algorithm. (8 hours)

(RBT Levels: L1, L2 and L3)

Suggested Learning Resources:

Text Books:

1. Narsingh Deo, Graph theory with the applications to engineering & Computer Science,

Dovers Publications, 2016

2. J.A. Bondy and U.S.R. Murty. Graph theory with Applications, Springer, 1st edition, 2008.

Reference Books:

1. Garry Chartand and Ping Zhang, Introduction to Graph Theory, Tata McGraw-Hill, 2006.

2. Frank Harary, Graph Theory, Narosa Publishing House, Latest edition.

3. R. Diestel, Graph Theory, free online edition, 2016: diestel-graph-theory.com/basic.html.

4. Douglas B. West, Introduction to Graph Theory, Prentice Hall India Ltd.,2001

5. Robin J. Wilson, Introduction to Graph Theory, Longman Group Ltd.,2010

Web links and Video Lectures (e-Resources):

• http://nptel.ac.in/courses.php?disciplineID=111

• http://www.class-central.com/subject/math(MOOCs)

• http://academicearth.org/

• VTU e-Shikshana Program