Week |
Contents |
Week 1 |
Adjacency matrices of Graphs: Basic properties and computing eigenvalues of some graphs. Perron-Frobenius theorem. Eigenvalues, eigenvectors and bipartiteness. |
Week 2 |
Harary's determinant formula, Sach's coefficient theorem and applications. |
Week 3 and 4 |
Inverse of tree: Characterization of invertibility, formula for the inverse of the trees, alternating path, corona tree, characterization of trees whose inverse is also a tree. |
Week 5 and 6 |
Spectral Theorem for symmetric matrices, Rayleigh quotient theorem. Bounds for the eigenvalues. Wilf's theorem, Hoffman's bound, Stanley's bound, Hong's bound, Nikiforov's bound. Mantel's theorem and Nosal's theorem. |
Week 7 |
Moore graphs, Hoffman-Singleton Theorem. Decomposition of K10 into Petersen graphs. Witsenhausen Theorem and Graham-Pollak Theorem. Strongly regular graphs. |
Week 8 | The friendship theorem. Expander mixing lemma and Hoffman radio bound. Courant-Fischer Theorem. Cauchy interlacing theorem, Poincare separation theorem. |
Week 9 | Applications of interlacing theorems: Cvetkovic Inertia Bound. Proof of sensitivity conjecture. Graphs determined by spectrum, construction cospectral graphs. |
Week 10 and 11 | Laplacian matrices and incidence matrices. Spectral bounds for Max-cut and bisection problems. Matrix-Forest Theorem. Counting the number of spanning trees in Hypercubes. |
Week 12 | Bounds for the Laplacian eigenvalues. Algebraic connectivity. Fiedler's Nodal domain theorem. |
Week 13 | Semester Break |
Week 14 | Characteristic vertices and Charateristic edges of trees. Classification of trees. |
Week 15 |
Monotonicity property of Fiedler vector. Bounds for the algebraic connectivity. |
Week 16 and 17 | Distance matrices of trees: Determinant and inverse. Eigenvalues of distance matrices and Laplacian matrics. We will discuss some of the results of Graham and Pollak, Graham and Lovasz, and Grone, Merris and Sunder. |