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)