Graph theory (2023-24 even semester)
Graph theory (2023-24 even semester)
An extra class will be conducted on 09-th February 2024 (Friday) from 3:30 to 5 PM.
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
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
Solve all the problems by yourself and submit before the due date
Assignment 1 (Due date 22.01.2024)
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 (Published on 06.05.2024 at 2 PM)
We update the following Google sheet time to time
https://docs.google.com/spreadsheets/d/1z0aaRIkJzxHDcM3hwqNc6saTF_a8eD3cKjAIQYrJ9Jk/edit?usp=sharing