# Graph Theory

By Dr.T.Asir   |   Madurai Kamaraj University
Learners enrolled: 962
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 : Ongoing Course Type : Elective Duration : 12 weeks Start Date : 18 Jan 2023 End Date : 09 Apr 2023 Exam Date : Enrollment Ends : 12 Mar 2023 Category : Mathematics Credit Points : 4 Level : Undergraduate

### 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

### Dr.T.Asir

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.

### Course certificate

30% for in course Assessment & 70% of end term Proctored Exam