Syllabus of Andhra University BTech Information Technology - IT 4.1.5 - Combinatorics & Graph Theory (Elective I)

Fourth year - First Semester

Instruction: 3 Periods & 1 Tut /week
Univ. Exam : 3 Hours

Sessional Marks: 30
Univ-Exam-Marks:70

PART I: Combinatorics

1. FOUNDATION: Basics- Sets- Relations- Proof methods- Problem-solving strategies-Mathematical Induction.

2. COMINATORICS: Basics of counting-Combinations and Permutations- Enumeration of Combinations & Permutations without repetitions and without repetitions- with constrained repetitions-Binomial Coefficients-Binomial and Multinomial theorems- Principle of Inclusion-Exclusion

3. RECURRENCE RELATIONS: Generating Functions of Sequences- Calculating Coefficients of Generating Functions- Recurrence Relations- Solving Recurrence Relations using Substitution and Generating Functions-Method of Characteristic Roots-Solutions of homogeneous and inhomogeneous recurrence relations.

PART II Graph Theory

4. FUNDAMENTAL CONCEPTS: what is a Graph-Paths-Cycles-Trails-Vertex Degrees and Counting-Directed Graphs-Trees and Distance-Spanning Trees-Enumeration-Optimization and Trees.

5. MATCHINGS AND CONNECTIVITY : Matchings and Covers-Algorithms and applications of matching-Matchings in General graphs-Cuts and Connectivity-k-connected graphs-Network flow problems.

6. COLORING AND PLANAR GRAPHS: Vertex coloring and upper bounds-Structure of kchromatic Graphs-Enumerative Aspects-Embeddings and Euler’s formula-Characterization of Planar graphs-Parameters of Planarity-Edges and Cycles-Line Graphs and edge-coloring-Hamiltonian Cycles-Planarity-coloring and cycles.

Text Books:

1. J.L. Mott, Abraham Kandel & Theodore P. Baker, " Discrete mathematics for Computer Scientists & Mathematics", Prentice-Hall of India Ltd. New Delhi. (Chapters 1,2,3)

2. Douglas B. West, "Introduction to Graph Theory", Pearson Education Asia, New Delhi. (Chapters 1,2,3,4,5,6,7)

Reference Books:

1. Michel Townsend, "Discrete Mathematics: Applied Combinatorics and graph theory", The Benjamin/Cummings Publishing Company", California.

2. Kenneth H Rosen. "Discrete Mathematics and Its Applications, Tata McGrahHill Publishing Company, New Delhi.

3. Robin J. Wilson, "Introduction to Graph Theory" Pearson Education Asia, New Delhi.