PMAT 42383: Graph Theory

Course Code  :  PMAT 42383

Title                :  Graph Theory

Pre-requisites :  PMAT 21553

 Learning Outcomes:

At the end of the course the student should be able:

• recognize the applications of graphs in real life

• calculate the matrices and their properties associated with graphs

• find the minimum spanning tree

• apply graph coloring in various applications

• apply the concept of matching, covering and connectivity in real world applications

• determine the maximum flow and minimum cut of a network

• construct random graph models and apply them to the relevant real-life problems

• solve graph related application in the real-life situations.

 Course Contents:

Matrices Associated with graphs and their properties: 

• Laplacian, Normalized Laplacian, Signless Laplacian.

Trees: 

• Spanning trees, Algorithms for shortest path and spanning trees.

Graph Coloring: 

• Vertex colouring, Edge colouring, Colouring algorithms, Chromatic polynomials.

Matching: 

• Perfect matching, Maximum matching, Alternate and Augmented paths, Hall’s marriage theorem, Stable matching,

Covering: 

• Vertex cover, Edge cover, Konig’s theorem, Factors of a graph,

Connectivity: 

• Vertex connectivity, Edge connectivity, Connectivity index, k-Connected graphs, Menger’s theorem.

Introduction to graph Labelling: 

• Prime labelling, Graceful labelling.

Network flow problems: 

• Network of a digraph, Flows and source/sink cuts, Ford-Fulkerson algorithm, Max-flow min-cut theorem.

Random graphs: 

• Basics in probability, Random variable, Moment generating functions, Types of random graphs, Properties of random graphs, Erdo ̈s theorem

 Method of Teaching and Learning :  A combination of lectures, group project and assignments

 Recommended Reading:

1. Wilson, R.J. (5 th Ed., 2010). Introduction to Graph Theory, Longman.

2. Chartrand, G. & Zhang, P. (2013). A First Course in Graph Theory, Courier Corporation.

3. Balakrishnan, V. (2004). T&P Of Graph Theory (Schaum's outline series) Tata McGraw-Hill Education.

4. Cvetkovic, D.M., Doob, M. & Sachs, H. (3 rd Ed., 1999). Spectra of Graphs: Theory and Applications, Wiley.

5. West, D.B. (2 nd Ed., 2005). Introduction to Graph Theory, Prentice Hall. 6. Balakrishan, R. & Ranganathan, K. (2 nd Ed., 2012). Textbook of Graph Theory, Springer.