|
| 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. |