Graph theory (2023-24 even semester)
Notice
An extra class will be conducted on 09-th February 2024 (Friday) from 3:30 to 5 PM.
Lessson plan
This is a tentative plan and will be modified time to time. The following lectures are planned for all students.
Lecture 1: What Is a Graph? Basic definitions.
Lecture 2: Matrices, Isomorphism, Special Graphs,
Lecture 3: Paths, Cycles, and Trails, Connection in Graphs, Bipartite Graphs, Eulerian Circuits. Vertex Degrees and Counting, Counting and Bijections,
Lecture 4: Graphic Sequences, Directed Graphs, Definitions and Examples, Vertex Degrees, Eulerian Digraphs, Orientations and Tournaments.
Lecture 5: Properties of Trees, Distance in Trees and Graphs, Disjoint Spanning Trees
Lecture 6: Enumeration of Trees, Spanning Trees in Graphs, Decomposition and Graceful Labelings, Branchings and Eulerian Digraphs.
Lecture 7: Maximum Matchings on graphs, Hall's Matching Condition, Min-Max Theorems, Independent Sets and Covers.
Lecture 8: Connectivity, Edge-connectivity, Blocks.
Lecture 9: Vertex and edge connectivity. k-connected Graphs, 2-connected Graphs, Connectivity of Digraphs, k-connected and k-edge-connected Graphs, Menger's Theorem.
Lecture 10: Maximum Network Flow, Integral Flows.
Lecture 11: Vertex Colorings and Upper Bounds. Definitions and Examples, Upper Bounds, Brooks' Theorem
Lecture 12: Graphs with Large Chromatic Number, Extremal Problems and Turan's Theorem, Color-Critical Graphs.
Lecture 13: Embeddings and Euler's Formula. Drawings a graph in the Plane, Dual Graphs, Euler's Formula.
Lecture 14: Preparation for Kuratowski's Theorem, Convex Embeddings, Planarity Testing
Lecture 15: Coloring of Planar Graphs, Crossing Number, Surfaces of Higher Genus.
Lecture 16: Line Graphs and Edge-coloring, Characterization of Line Graphs
Lecture 17: Hamiltonian Cycles, Necessary Conditions, Sufficient Conditions, Cycles in Directed Graphs
Special lectures for MSc and PhD students:
Lecture 1: Random graph
Lecture 2: A few Spectral properties of graphs
Lecture 3: Random walk on graphs
Lecture 4: Ihara zeta function
Text Books:
Introduction to Graph Theory. Douglas B. West
Handbook on Graph Theory. Jonathan L. Gross, Jay Yellen, Ping Zhang.
Introduction to Graph Theory. Robin J. Wilson
Assignments:
Solve all the problems by yourself and submit before the due date
Assignment 1 (Due date 22.01.2024)
Question papers
Class Test 1 was an open book surprise test where the students were asked to solve the following question:
Let A = {0, 1, 2}, and V = A* A * A, where * denotes Cartesian product of sets. E = {(u, v): d(u, v) = 1}, where d(u, v) = d((u_1, u_2, u_3), (v_1, v_2, v_3)) = D(u_1, v_1) + D(u_2, v_2) + D(u_3, v_3). Here D(u_i, v_i) indicates the Hamming distance. Draw the graph with vertex set V and edge set E.
End Term question paper (Will be published on 06.05.2024 at 2 PM)
Evaluation
We update the following Google sheet time to time
https://docs.google.com/spreadsheets/d/1z0aaRIkJzxHDcM3hwqNc6saTF_a8eD3cKjAIQYrJ9Jk/edit?usp=sharing