Learn · Introduction to Algebraic Graph Theory

Lecture 42 of 48Week 8

Sign Switching in Signed Graphs

Prof. Ranveer Singh · IIT Indore

Credits and licence

From
Introduction to Algebraic Graph Theory, IIT Indore (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
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
Tweens profiles and older. How courses are placed

All the lectures

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