A Major Elective for B.Sc. (Research) Mathematics.
Credits (Lec:Tut:Lab)= 3:1:0 (3 lectures and 1 tutorial weekly)
Prerequisites: MAT 160 Linear Algebra I
Overview: Graphs are fundamental objects in combinatorics. The results in graph theory, in addition to their theoretical value, are increasingly being applied to understand and analyze systems across a broad domain of enquiry, including natural sciences, social sciences and engineering. The course does not require any background of the learner in graph theory. The emphasis will be on the axiomatic foundations and formal definitions, together with the proofs of some of the central theorems. Few applications of these results to other disciplines would be discussed.
Detailed Syllabus:
Unit 1
- Definitions of Graph, Digraph, Finite and Infinite Graph, Degree of a Vertex, Degree Sequence, Walk, Path, Cycle, Clique.
- Operations on graphs, Complement of a graph, Subgraph, Connectedness, Components, Isomorphism.
- Regular graph, Complete graph, Bipartite graph, Cyclic graph, Euler graph, Hamiltonian path and circuit, Tree, Cut set, Spanning tree.
Unit 2
- Planar graph, Colouring, Covering, Matching, Factorization, Independent sets.
Unit 3
- Graphs and relations, Adjacency matrix, Incidence matrix, Laplacian matrix, Spectral properties of graphs, Matrix tree theorem, Automorphism group of a graph.
Unit 4
- DFS, BFS for minimal spanning tree, Kruskal, Prim and Dijkstra algorithms.
References:
- D. West, Introduction to Graph Theory, 2nd ed., PHI Learning, New Delhi, 2009.
- N. Deo, Graph Theory: With Application to Engineering and Computer Science, PHI Learning, New Delhi, 2012.
- C. D. Godsil and G. Royle, Algebraic Graph Theory, Springer, New Delhi, 2013.
- B. Kolman, R.C. Busby, S.C. Ross, Discrete Mathematical Structures, 6th ed., PHI Learning, New Delhi, 2012.
- F. Harary, Graph Theory, Narosa, New Delhi, 2012.
- J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, New Delhi, 2013.
- R.J. Wilson, Introduction to Graph Theory, 4th ed., Pearson Education, New Delhi, 2003.
Past Instructors: Sudeepto Bhattacharya