Graph Theory

By Dr.T.Asir | Department of Mathematics, Pondicherry University

Learners enrolled: 1227

The course on Graph Theory is a 2 credit course which contains 26 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 :	Core
Language for course content :	English
Duration :	8 weeks
Category :	Mathematics
Credit Points :	2
Level :	Undergraduate
Start Date :	10 Jul 2024
End Date :	31 Oct 2024
Enrollment Ends :	31 Aug 2024
Exam Date :	08 Dec 2024 IST
Exam Shift: :	Shift-2

Note: This exam date is subject to change based on seat availability. You can check final exam date on your hall ticket.

Page Visits

Course layout

Week - 1

1. Introduction to graphs

2. Basic properties of graphs

3. Complete and bi-partite graphs

Week - 2

4. Isomorphism of graphs

5. Paths and circuits

6. Eulerian Graphs

7. Hamiltonian graphs

Week - 3

8. Matrix representation of graphs

9. Chordal graphs

10. Weighted graphs

Week - 4

11. Matchings in graphs

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

13. Travelling salesman’s problem & Chinese postman problem

Week - 5

14. Distances in graphs

15. Shortest path and Dijkstra’s algorithm

16. Floyd – Warshall Algorithm and

17. Bellman-Ford Algorithm

Week - 6

18. Trees

19. Spanning tree in graphs

20. Minimum spanning tree algorithms

21. Kruskal’s algorithm

Week - 7

22. Independent sets and Coverings in graphs

23. Planar graphs

Week - 8

24. Euler's formula

25. Cut vertices and Cut edges

26. Edge connectivity of graphs

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

Department of Mathematics, Pondicherry University

Dr. T. Asir has pursued his B.Sc. and M.Sc. in Mathematics from St. Xavier’s College, Palayamkottai and his M.Phil. from Manonmaniam Sundaranar University, Tirunelveli. He has received a gold medal in M.Sc. and secured University second rank in M.Phil. He received the Ph.D. degree in Mathematics at Manonmaniam Sundaranar University and his Ph.D. work was supported by the grants “Major Project Fellowship” by University Grants Commission(UGC), India and the “INSPIRE Fellowship” by the Department of Science & Technology(DST), India. He did his Post Doctorate under the UGC-Kothari Postdoctoral Fellowship. He was worked as an Assistant Professor and Head i/c in Department of Mathematics-DDE, Madurai Kamaraj University, Tamil Nadu from Dec 2013 to July 2022.

His research interest is Algebra and Graph Theory. More specifically, graphs arising from rings and vice versa. He has published 37 research articles in International Journals and two books (including a book in Springer) with a citation count of 276 on Web of Science, 379 on Scopus and 589 on Google Scholar. He has completed three projects UGC-Startup grant, SERB-MATRICS project and Deanship of Scientific Research at King Abdulaziz University, Saudi Arabia. Currently, his research is supported by CSIR project. Also, he has received travel grants from DST(2012), UGC(2015), SERB(2019), CSIR(2020) and Gustave Eiffel University, France(2023) to deliver talks at International Conferences held at AlAin-UAE(2012), Thailand(2015), Palestine-Israel-Egypt(2019), Sharjah-UAE(2020) and France(2023). Further, received grants from SERB, CSIR and MKU to conduct an International Conference during January, 2018.

Further 5 Ph.D.’s and 25 M.Phil.’s have been awarded under his guidance. Moreover, he has delivered more than 80 invited talks at various National/International conferences and Orientation/Refreshers programs. He has served as a referee of several international journals in the frame of pure and applied mathematics. Furthermore, he has developed online mathematical content through MOOC Courses “Core and Pedagogy of Mathematics”, “Modern Algebra”, “Graph Theory”, “Algebra” and “Ring Theory and Linear Algebra” in SWAYAM Platform (MHRD).