## Details of MA3103 (Autumn 2016)

Level: 3 |
Type: Theory |
Credits: 3.0 |

Course Code | Course Name | Instructor(s) |
---|---|---|

MA3103 |
Graph Theory and Combinatorics |
Anirban Banerjee |

Syllabus |
---|

MA3103 : Graph Theory and Combinatorics
Enumerative Combinatorics: The pigeonhole principle, principle of inclusion / exclusion, integer functions, finite and infinite sums; derangements; Stirling, Euler, harmonic, Bernoulli, Bell and Fibonacci numbers; generating functions and recursion relations; partitions; Polya theory; inversion techniques (optional). Graph Theory: Graphs and digraphs, basic definitions and concepts; graph isomorphism; graph representation; trees and spanning trees, connectivity, graph traversals, Eulerian and Hamiltonian paths and cycles; planarity; graph colorings; matching and bipartite graphs; graph algorithms. |

Prerequisite |
---|

Linear algebra, sets, functions, permutations, combinations. |

References |
---|

Suggested Texts/Reference Books:
1. Aigner, M., Discrete Mathematics, American Mathematical Society, 2007. 2. Bondy, J. A. and Murty, U. S. R., Graph Theory,Graduate Texts in Mathematics, Springer-Verlag, 2008. 3. Graham, R. L., Knuth, D. E. and Patashnik, O., Concrete Mathematics: A Foundation for Computer Science (2nd Edition), Addison Wesley, 1994. 4. Gross, J, L and Yellen, J., Graph Theory & Its Applications (2nd Edition). Chapman & Hall, 2006. 5. Rosen, K. H., Discrete Mathematics & Its Applications (6th Edition), Tata McGraw-Hill, 2007. |

#### Course Credit Options

Sl. No. | Programme | Semester No | Course Choice |
---|---|---|---|

1 | IP | 1 | Core |

2 | IP | 3 | Not Allowed |

3 | IP | 5 | Not Allowed |

4 | MR | 1 | Not Allowed |

5 | MR | 3 | Not Allowed |

6 | MS | 5 | Core |

7 | RS | 1 | Elective |

8 | RS | 2 | Elective |