Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

NPTEL

Introduction to Algebraic Graph Theory

NPTEL via Swayam

Go to class Write review

No Longer Offered

Corporate Finance Institute Ad

Learn Excel and Financial Modeling the Way Finance Teams Actually Use Them

Learn More → Boot.dev Ad

The Most Addictive Python and SQL Courses

Learn More →

Overview

Google, IBM & Meta Certificates – 40% Off
One Coursera Plus subscription covers most Professional Certificates on Coursera.
Unlock All Certificates
ABOUT THE COURSE:Algebraic graph theory is the study of graphs (or networks) using linear algebra or matrix theory. This course provides a comprehensive foundation of Algebraic graph theory, areas where graph properties play a critical role include complex network analysis, theoretical computer science, and other related fields. Upon completing the course, learners will acquire the ability to analyze graph properties using matrix theory and related algebraic techniques. They will develop the skills to formulate, derive, and interpret bounds for various graph-theoretic problems. This course is ideal for individuals interested in bridging the gap between theoretical concepts and practical applications in graph analysis.INTENDED AUDIENCE: Students, Researchers, ProfessionalsPREREQUISITES: Linear Algebra, Introduction to Graph TheoryINDUSTRY SUPPORT: Microsoft Research, Google, Facebook, LinkedIn and start-ups working in the field of graph.

Syllabus

Week 1: Graphs, associated matrices and some basic properties, counting number of components, existence of a cycle in a graph, Eigenvalues and eigenvectors
Week 2:Matrix power, spectral theorem, number of walks, closed walks, diameter of graph, counting the number of spanning trees
Week 3:Perron Frobenius theorem for graphs, Rayleigh quotient, minimum eigenvalue, maximum eigenvalue, maximum degree, minimum degree, average degree, Characterization of bipartite graphs
Week 4:Spectrum of induced subgraph, introduction to Cauchy interlacing theorem, proof of Cauchy interlacing theorem
Week 5:Eigenvalues and coloring of graphs, eigenvalues and largest clique, Graphs isomorphism and eigenvalues
Week 6:Graphs determined by eigenvalues, Regular graph, strongly regular graph
Week 7:Friendship theorem, Random walks, Rate of Convergence
Week 8:Algebraic connectivity, Fiedler vector, Introduction to expanders graph

Taught by

Prof. Ranveer Singh

Reviews

Start your review of Introduction to Algebraic Graph Theory

Go to class

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free
Someone learning on their laptop while sitting on the floor.