Course Code: PMA24E19 (M.Sc. 4th semester in Computational Mathematics) & DTMA26C01 (BTMT 6th semester in Mathematics and Computing)
Department of Mathematics,
National Institute of Technology Agartala.
Course instructor: Supriyo Dutta
Teaching Assistant: Gourav Sinha.
Meetings: Monday and Thursday 9 am to 11 am.
First Class 09th January 2025.
Class test before mid-term: 6th February 2025 (20 min at the end of the lecture)
Mid-term: Date will be announced by Exam Section
Class test before end-term: 21st April 2025 (20 min at the end of the lecture)
End-term: Date will be announced by Exam Section
You may find the the class notes, assignment, and question papers of my previous course from the below link:
Graph theory (2023-24 even) for BTMT 6th and MSc 4 th semester students.
Graph theory (2024-25 odd) for BSMS 5th semester students.
Mass class bank will not be tolerated.
Due to modification of academic calendar, we get two more classes before mid-semester exam and loose two classes after the mid-term exam.
Syllabus of Mid-term exam will be upto lecture 12.
Introduction to Graphs: The concept of a graph, paths in graphs, graph models, graph terminology and special types of graphs bipartite graphs, complete graphs. operations on graphs, graph isomorphism.
Graphs in NetworkX: Brief idea on NetworkX
Trees: Introduction to trees and characterization of trees, applications of trees, spanning trees, minimum spanning trees in computer science.
Connectivity: Eularian graphs, and Hamiltonian graphs.
Representing Graphs: Adjacency matrix, incidence matrix, cycle matrix.
Planarity: Plane and planar graphs, outerplaner graphs, Kuratowski's theorem.
Directed Graphs: Basic definitions, Type of Connectedness. Distance concepts and matrices, Connectivity, Acyclic digraphs, Cycles and traversability, Orientations and Tournaments.
You may consult to the course instructor or teaching assistant to get a soft copy of these 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
Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall of India Pvt.Ltd., New Delhi, 1997
Jonathan L. Gross, Jay Yellen, Graph Theory and Its Applications. CRC Press. 2006.
Find the underlined text to get handwritten class notes.
Before Mid-term
Lecture 1 (9th January 2025): Introduction to graphs, and digraphs, as well as their applications in different branches of Sciences and Computation. Adjacency matrix, degree matrix, incidence matrix and examples.
Lecture 2 (13th January 2025): Path graph, cycle graph, complete graph, complete bipartite graph, star graph. Walk, trail, path, and cycle in a graph. Connected graph.
Lecture 3 (16th January 2025): Hypercube graph, Circulant graph, Cayley graph, intersection and interval graphs. Some application of graphs: job-assignment problem, interval graphs in archeology. Eccentricity of a vertex in a graph, radius and diameter of a graph.
Lecture 4 (20th January 2025): Konigsberg bridge problem, Complement of a graph, subgraph, independent set and clique in a graph, graph coloring problem, chromatic number, graph isomorphism.
Lecture 5 (23th January 2025): Self-complementary graphs, Petersen graph and its properties, cut vertex, cut edge, induced subgraph.
Lecture 6 (27th January 2025): Operations on graphs, removal of vertices and edges, cut edges and cut vertices, Koning's theorem, bipartite graphs and cycles in it.
Lecture 7 (30th January 2025): The class was rescheduled due to GATE Examination 2025.
Lecture 8 (3rd February 2025): Handshaking theorem of graph theory, Other counting lemmas, degree sequence of a graph, Construction of a graph from a degree sequence.
Lecture 9 (6th February 2025): Graphic sequence, Havel-Hakimi theorem, directed graphs, indegree, outdegree, split of a graph, simple directed graph.
Lecture 10 (10th February 2025): Digraph from a relation, functional diagraph, kernel of a digraph, orientation and tournament. Tree, forest, spanning tree.
Lecture 11 (13th February 2025): Some fundamental properties of a tree.
Lecture 12 (17th February 2025): Maximum number of edges in a disconnected graph, Six equivalent definitions of a tree.
Lecture 13 (20th February 2025): Counting of trees. Prufer sequence.
Lecture 14 (24th February 2024):
After Mid-term
Lecture 15 (10th March 2025): Important surfaces in topological graph theory
Lecture 16 (13th March 2025)
Lecture 17 (17th March 2025): Some important surfaces - plane, sphere, torus. Example of planar and non-planar graphs with proofs.
Lecture 18 (20th March 2025): Geometric Graph Theory. Subdivision of edges, Barycentric subdivision, Graph homeomorphism problem.
Lecture 19 (24th March 2025): Connectivity of a graph, edge connectivity, vertex connectivity.
Lecture 20 (27th March 2025): Edge connectivity is greater than vertex connectivity - proof.
Lecture 21 (3rd April 2025): Properties and Construction of $k$ connected graphs.
Lecture 22 (7th April 2025): Synthesis of $k$-connected graphs for $k = 2, 3$ and any positive integer $k$.
Lecture 23 (14th April 2025)
Lecture 24 (17th April 2025): Eulerian graphs and their characterization.
Lecture 25 (21th April 2025): Hamiltonian paths and cycles (Online lecture due to Chicken Pox in campus) Class test for all BTMT and MSc students.
Lecture 26 (24th April 2025): Presentation on self-study projects.
We distribute the students with following groups. Every group is assigned a topic for self-study. They need to submit a report on their study and will present it in group.
All MSc students: Collect all the question on Graph Theory from last 10 years' GATE question papers of Mathematics and last 5 years' NET question papers and solve them.
Group 1: Collect all the question on Graph Theory from last 10 years' GATE question papers of Mathematics and last 5 years' NET question papers and solve them.
Group 2: Construct various graphs using NetworkX and find out their properties .
Group 3: Generate complex networks using NetworkX and find their properties.
Group 4: Implement Kronecker product, Cartesian product, Coronal Product, and Laxiographic product of graphs using Networkx.
Group 5: Prepare a report on expander graphs and their properties.
For old question papers find the previous course websites.
Class test - 1 question paper, Dated 6th February 2025.
.Mid Term question paper, Dated 05th March 2025
Class test - 2 question paper, Dated 21-st April 2025
End Term question paper for BTMT and MSc Dated 10-th May 2025
Distribution of marks
End Term examination = 50 marks
Mid Term examination = 20 marks
Class Test 1 (before mid semester) = 10 marks
Class Test 2 (before mid semester) = 10 marks
Attendance = 5 marks
Submission of self-study project = 5 marks
Total credit in this course: 4
Find the linked Google sheet for your marks and grades (Check for the detailed calculation of your marks)
Result:
BTMT Ex = 3, A = 5, B = 5, C = 0, D = 3, P = 4, F = 5.
MSc Ex = 2, A = 2, B = 2, C = 1, D = 0, F = 0.