IIT Indore · Computer Science

Introduction to Algebraic Graph Theory

Prof. Ranveer Singh · 48 free video lectures

48 video lectures. Topics: Warm-up with graphs; Incidence matrix, cofactors of the Laplacian matrix (towards Matrix-Tree Theorem); Determinant of submatrices of incidence matrices and characterization of spanning trees; Cauchy-Binet theorem and the proof of matrix-tree theorem; Rank of incidence…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Warm-up with graphs
  2. Incidence matrix, cofactors of the Laplacian matrix (towards Matrix-Tree Theorem)
  3. Determinant of submatrices of incidence matrices and characterization of spanning trees
  4. Cauchy-Binet theorem and the proof of matrix-tree theorem
  5. Rank of incidence matrix and the number of connected components
  6. Rank and acyclic graphs, 0-1 incidence matrix and characterization of bipartite graph
  7. Introduction of the eigenvalues and eigenvector
  8. Adjacency matrix and number of walks; powers of a symmetric matrix
  9. The spectral theorem
  10. Rayleigh quotient and the eigenvalues
  11. A bound on the diameter of a graph using the number of distinct eigenvalues
  12. The rank of a symmetric matrix equals the number of nonzero eigenvalues.
  13. Perron-Frobenius theorem for nonnegative symmetric matrices
  14. The consequences of the Perron-Frobenius theorem (the properties of the largest eigenvalue and the corresponding eigenvectors)
  15. Eigenvalues of a graph and its subgraph; a relation between the largest eigenvalue and the degree(s)
  16. Cauchy interlace theorem
  17. Bipartite graphs and their eigenvalues
  18. Positive semi-definite matrices and the eigenvalues of their partitioned form
  19. The eigenvalues of a symmetric matrix in partitioned form
  20. Bounds on chromatic number, clique number, and independence number
  21. Introduction to lazy random walk, walk matrix
  22. Convergence of lazy random walk
  23. Rate of convergence of lazy random walk
  24. Regular graphs, spectral properties, bound on size of independent set
  25. Strongly regular graphs, their eigenvalues, and characterization
  26. The friendship theorem
  27. Introduction to cospectral graphs
  28. Godsil McKay switching to generate cospectral graphs
  29. Cartesian product and their eigenvalues, Shrikhande graph
  30. Graph determined by the spectrum
  31. Sensitivity, block sensitivity and hypercube graph
  32. Proof of sensitivity conjecture
  33. Introduction to expander graphs
  34. A lower bound on Cheeger constant, and expander mixing lemma
  35. Introduction to Ramanujan graphs
  36. 2-Lift and Zig-zag product for construction of expander and Ramanujan graphs
  37. Introduction of algebraic connectivity and Fiedler vector
  38. Upper bound on algebraic connectivity
  39. Some more bounds on algebraic connectivity
  40. Relation between algebraic connectivity of graph and its induced subgraph.
  41. Introduction to Balanced Signed Graphs
  42. Sign Switching in Signed Graphs
  43. Laplacian of Signed Graphs, Frustration number and Frustration index
  44. Determinant, Permanent in terms of graph structure.
  45. Live Session 27-08-2025
  46. Live Session 06-09-2025
  47. Live Session 22-09-2025
  48. Live Session 31-10-2025

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Indore.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights