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:
- Wilson, R.J. (5 th Ed., 2010). Introduction to Graph Theory, Longman.
- Chartrand, G. & Zhang, P. (2013). A First Course in Graph Theory, Courier Corporation.
- Balakrishnan, V. (2004). T&P Of Graph Theory (Schaum's outline series) Tata McGraw-Hill Education.
- Cvetkovic, D.M., Doob, M. & Sachs, H. (3 rd Ed., 1999). Spectra of Graphs: Theory and Applications, Wiley.
- 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.