Graphs & Networks - MATH F243
Mathematic Core Course: Semester II 2024-2025
Instructor: Dr. Yasmeen Akhtar
Audience: 2nd, 3rd, and 4th Year B.E. students at BITS Pilani, K K Birla Goa Campus
Tutors: We do not have any formal TAs assigned to the course.
Schedule: Monday, Wednesday, Friday 9:00-9:50 AM at A602 (Lecture)
Thursday 3:00-3:50 AM at A602 (Tutorial)
Course Handout: Available on Quanta.
Evaluation: Quizzes-30%, Midsemester Exam-30%, Comprehensive Exam-40%
February- Quiz 1, March-Quiz 2, March-Midsem, April-Quiz 3, May-Comprehensive Exam
Lecture:
08/01/25 - Introduction and instructions related to the course, Graph: history and applications, Complete graph, Path, and Cycle
09/01/25 - Tutorial
10/01/25 - Distance, Geodesic, Diameter, Subgraph, Connected graphs and properties
13/01/25 - Characterization of connected graph of order >=3, Bipartite Graph and its characterization
15/01/25 - Degree, Neighborhood, Degree Sequence, Graphical sequence, Problems based on degree sequence
16/01/25 - Tutorial
17/01/25 - Proof of Havel-Hakimi Theorem, Regular graphs, Harary Graphs
20/01/25 - Irregularity, F-degree, F-regular and F-irregular graph, Graph Homomorphism and Graph Isomorphism
22/01/25 - Automorphisms of graph and Aut(G), Problems based on graph isomorphism
23/01/25 - Tutorial
24/01/25 - Bridges, Trees, and their properties
27/01/25 - Spanning Subgraph, Spanning Trees, Counting the number of labeled trees on n vertices using the Prufer code, Cayley's Theorem: Number of spanning trees of the complete graph Kₙ
29/01/25 - Matrix Tree Theorem, Counting the number of spanning trees of arbitrary graph G (loopless), Applications
30/01/25 - Tutorial
30/01/25 - Minimum Spanning Tree: Kruskal's Algorithm, Prim's Algorithm (Extra class)
31/01/25 - Validity of algorithm for computing Minimum Spanning Tree, Eccentricity, Radius, Relation between radius and diameter of a graph G
03/02/25 - Eccentric subgraph, Central vertex, Peripheral vertex, Center, and Periphery of a graph, Boundary vertex
05/02/25 - Rooted Tree, Ordered Rooted Tree, Binary Tree, Regular (Full) Binary Tree, Counting Regular Binary Trees (with and without labels)
06/02/25 - Tutorial
06/02/25 - Height of a rooted tree, Average level of leaves in a rooted tree: Ave (T), Complete Binary Trees (Extra class)
07/02/25 - Quark
10/02/25 - Non-instructional day
12/02/25 - Matrix Tree Theorem for Multigraph (Krichhoff's theorem), Dijkstra's algorithm for shortest path
13/02/25 - Quiz 1
14/02/25 - Graph Traversal Algorithms: BFS and DFS, applications
17/02/25 - Eulerian trail and circuit, Eulerian Graph and its characterization, Hamiltonian cycle, and Hamiltonian Graph
19/02/25 - A necessary condition for being Hamiltonian, A sufficient condition for being Non-Hamiltonian, A sufficient condition for being Hamiltonian
20/02/25 - Tutorial: Problems based on Eulerian and Hamiltonian graphs, Fleury's Algorithm, Traveling Salesman Problem
21/02/25 - Proof for Peterson graph is Non-Hamiltonian, Cut-vertex, and related properties
26/02/25 - Holiday
27/02/25 - Tutorial
28/02/25 - Non-separable graph, Vertex-cut, Minimum cut, vertex-connectivity κ(G)
08/03/25 - Midsemester Exam
10/03/25 - Edge-cut, Minimum and Minimal Edge-cut, Edge-connectivity, Relation between vertex-connectivity and edge-connectivity
11/03/25 - Separating Set, Internally disjoint paths, Menger's Theorem
12/03/25 - Planar Graph
13/03/25 - Tutorial
14/03/25 - Holiday
17/03/25 - The Euler Identity, Necessary Condition for being Planar, Maximal Planar
19/03/25 - Sufficient Condition for Nonplanar, Subdivision of Graph, Kuratowski's Theorem, Planar Dual
20/03/25 - Quiz 2
21/03/25 - Planar embedding and Crossing Number ν(G), Vertex coloring of a graph, Chromatic Number χ(G), Clique Number ω(G)
24/03/25 - Bounds on Chromatic Number, Relation between Chromatic Number χ(G) and Independence Number β(G), Chromatic Polynomial and its properties
26/03/25 - Determining the chromatic polynomial, Map Coloring
27/03/25 - Tutorial
28/03/25 - Spree
31/03/25 - Holiday
02/04/25 - Edge-coloring, Chromatic index χ₁(G), Vizing's Theorem, Matching, Edge independence number β₁(G) and its upper bounds
03/04/25 - Tutorial
04/04/25 - Matching in bipartite graphs, Hall's Marriage Theorem
07/04/25 - Perfect Matching in a regular bipartite graph, Konig's Theorem, Edge Cover, Edge Cover Number α₁(G), Gallai's Identity I
07/04/25 - Vertex Cover, Vertex Cover Number α(G), Gallai's Identity II, Dominating Set, Domination Number γ(G), and bound on it, Open Dominating Set, Open Domination Number γ₀(G), Bounds on γ₀ in terms of γ (Extra class)
09/04/25 - Digraph, In-degree and out-degree, The First Theorem of digraph, Isomorphism in digraphs, Oriented graph, Weakly connected and Strongly connected digraph
10/04/25 - Holiday
11/04/25 - Eulerian digraph and its characterization, Tournaments, Transitive Tournament and its properties
14/04/25 - Holiday
16/04/25 - Hamiltonian path and cycle in a digraph, Characterization of Hamiltonian Tournaments
17/04/25 - Quiz 3
18/04/25 - Holiday
23/04/25 - Flow Network, Residual Network, Augmented Path, Max-Flow Problem, Min-Cut Problem
24/04/25 - Tutorial
25/04/25 - Max-Flow Min-Cut Theorem, Ford Fulkerson Method
28/04/25 - Matroid, Applications, and Problems
15/05/25 - Comprehensive Exam (Rescheduled to 30/07/2025)