Learn · NPTEL

Course10610669848 lectures

Introduction to Algebraic Graph Theory

Prof. Ranveer Singh · IIT Indore

Start with lecture 1 At NPTEL

Lectures

Week 1

  1. Warm-up with graphs Video
  2. Incidence matrix, cofactors of the Laplacian matrix (towards Matrix-Tree Theorem) Video
  3. Determinant of submatrices of incidence matrices and characterization of spanning trees Video
  4. Cauchy-Binet theorem and the proof of matrix-tree theorem Video
  5. Rank of incidence matrix and the number of connected components Video

Week 2

  1. Rank and acyclic graphs, 0-1 incidence matrix and characterization of bipartite graph Video
  2. Introduction of the eigenvalues and eigenvector Video
  3. Adjacency matrix and number of walks; powers of a symmetric matrix Video
  4. The spectral theorem Video
  5. Rayleigh quotient and the eigenvalues Video

Week 3

  1. A bound on the diameter of a graph using the number of distinct eigenvalues Video
  2. The rank of a symmetric matrix equals the number of nonzero eigenvalues. Video
  3. Perron-Frobenius theorem for nonnegative symmetric matrices Video
  4. The consequences of the Perron-Frobenius theorem (the properties of the largest eigenvalue and the corresponding eigenvectors) Video
  5. Eigenvalues of a graph and its subgraph; a relation between the largest eigenvalue and the degree(s) Video
  6. Cauchy interlace theorem Video

Week 4

  1. Bipartite graphs and their eigenvalues Video
  2. Positive semi-definite matrices and the eigenvalues of their partitioned form Video
  3. The eigenvalues of a symmetric matrix in partitioned form Video
  4. Bounds on chromatic number, clique number, and independence number Video
  5. Introduction to lazy random walk, walk matrix Video
  6. Convergence of lazy random walk Video

Week 5

  1. Rate of convergence of lazy random walk Video
  2. Regular graphs, spectral properties, bound on size of independent set Video
  3. Strongly regular graphs, their eigenvalues, and characterization Video
  4. The friendship theorem Video
  5. Introduction to cospectral graphs Video

Week 6

  1. Godsil McKay switching to generate cospectral graphs Video
  2. Cartesian product and their eigenvalues, Shrikhande graph Video
  3. Graph determined by the spectrum Video
  4. Sensitivity, block sensitivity and hypercube graph Video
  5. Proof of sensitivity conjecture Video
  6. Introduction to expander graphs Video

Week 7

  1. A lower bound on Cheeger constant, and expander mixing lemma Video
  2. Introduction to Ramanujan graphs Video
  3. 2-Lift and Zig-zag product for construction of expander and Ramanujan graphs Video
  4. Introduction of algebraic connectivity and Fiedler vector Video
  5. Upper bound on algebraic connectivity Video
  6. Some more bounds on algebraic connectivity Video

Week 8

  1. Relation between algebraic connectivity of graph and its induced subgraph. Video
  2. Introduction to Balanced Signed Graphs Video
  3. Sign Switching in Signed Graphs Video
  4. Laplacian of Signed Graphs, Frustration number and Frustration index Video
  5. Determinant, Permanent in terms of graph structure. Video

Live Session

  1. Live Session 27-08-2025 Video
  2. Live Session 06-09-2025 Video
  3. Live Session 22-09-2025 Video
  4. Live Session 31-10-2025 Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Indore
Department
Computer Science and Engineering
Teacher
Prof. Ranveer Singh
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Madras.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed