Graph Theory

By Dr.T.Asir | Madurai Kamaraj University, Madurai, Tamil Nadu.

Learners enrolled: 1109

The course on Graph Theory is a 4 credit course which contains 32 modules. This course deals with some basic concepts in graph theory like properties of standard graphs, Eulerian graphs, Hamiltonian graphs, Chordal graphs, Distances in graphs, Planar graphs, graph connectivity and Colouring of graphs. Further few graph Algorithms have also been discussed. This course is designed on par with the UGC syllabus.

The learners, as an outcome of successful completion will have a basic background of graph theory which has diverse applications in the areas of computer science, biology, chemistry, physics, sociology, and engineering.

Summary

Course Status :	Completed
Course Type :	Elective
Language for course content :	English
Duration :	12 weeks
Category :	Mathematics
Credit Points :	4
Level :	Undergraduate
Start Date :	19 Jan 2022
End Date :	10 Apr 2022
Enrollment Ends :	28 Feb 2022
Exam Date :

Page Visits

Course layout

Week- I

1. Introduction to graphs

2. Basic properties of graphs

3. Complete and bi-partite graphs

Week - II

4. Isomorphism of graphs

5. Paths and circuits

Week - III

6. Eulerian Graphs

7. Hamiltonian cycles

Week - IV

8. Matrix representation of graphs

9. Chordal graphs

10. Weighted graphs

Week - V

11. Matchings in graphs

12. Hall's 'marriage' theorem and its application

13. Travelling salesman’s problem & Chinese postman problem

Week - VI

14. Distances in graphs

15. Shortest path and Dijkstra’s algorithm

16. Floyd – Warshall Algorithm
17. Bellman-Ford Algorithm

Week - VII

18. Trees

19. Spanning tree in graphs

Week - VIII

20. Minimum spanning tree algorithms

21. Kruskal’s algorithm

22. Independence sets and covering in graphs

Week - IX

23. Planar graphs

24. Euler's formula

Week - X

25. Cut vertices and Cut edges

26. Edge connectivity

Week - XI

27. Vertex Colouring of graphs

28. Edge Colouring of graphs

29. The four-colour and five-colour theorems

Week - XII

30. Perfect Graphs

31. Applications of graphs in switching theory

32. Directed Graphs (or Digraphs)

Books and references

1. J. A. Bondy, and U.S.R. Murty, “Graph Theory”, Springer-Verlag, 2008

2. R. DIESTEL, “Graph Theory”, Springer-Verlag, 1997.

3. F. HARARY, “Graph Theory”, Addison-Wesley, 1969.

4. D.B. WEST, “Introduction to Graph Theory”, Prentice Hall, 1996.

5. R.J. WILSON, “Introduction to Graph Theory”, Longman, (3rd ed.) 1985

Instructor bio

Dr. T. Asir has received a gold medal in M.Sc. and secured University second rank in M.Phil. He has received the Ph.D degree in Mathematics which was supported by the grants from University Grants Commission(UGC) and “INSPIRE Fellowship” by Department of Science & Technology(DST). Also he did Post Doctorate under the UGC-Kothari Postdoctoral Fellowship. Currently he is working as an Assistant Professor and Head i/c in the Department of Mathematics-DDE, Madurai Kamaraj University, Tamil Nadu. Also he is the Director i/c for MKU Evening College, Dindigul. His research interest is Algebraic Graph Theory. He has published 23 research articles in International Journals and a book. At present, his research work is supported by Science and Engineering Research Board (SERB) through MATRICS project. Also he has completed a UGC project so-called Startup Grant. Also he has received travel grants from DST (2012), UGC(2015) and SERB (2019) to deliver talks at abroad. Further, received grants from SERB, CSIR and MKU to conduct an International Conference during January 08-10, 2018.

Under his guidance 2 Ph.D.’s and 21 M.Phil.’s have been awarded. Further he has delivered 45 invited talks in various National/International conferences and also abroad places like Palestine, Thailand and United Arab Emirates(UAE). He has served as a referee of several international journals in the frame of pure and applied mathematics. Furthermore, he is involved in developing Massive Open Online Course (MOOC) in SWAYAM Platform.