Details of MA3103 (Autumn 2017)

Level: 3 Type: Theory Credits: 4.0

Course CodeCourse NameInstructor(s)
MA3103 Graph Theory and Combinatorics Swarnendu Datta

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.ProgrammeSemester NoCourse 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 Not Allowed
8 RS 2 Elective