Graphs and Matrices

Code: MA601 | L-T-P-C: 3-0-0-6

Matrices, Eigenvalues of symmetric matrices, Graphs. Incidence Matrix, Rank, Minors, 0-1 Incidence matrix, Matchings in bipartite graphs. Adjacency Matrix, Eigenvalues of some graphs, Determinant, Bounds, Energy of a graph, Antiadjacency matrix of a directed graph, Nonsingular trees. Laplacian Matrix, Basic properties, Computing Laplacian eigenvalues, Matrix-tree theorem, Bounds for Laplacian spectral radius, Edge-Laplacian of a tree.Cycles and Cuts, Fundamental cycles and fundamental cuts, Fundamental matrices, Minors.Regular Graphs, Perron–Frobenius theory, Adjacency algebra of a regular graph, Complement and line graph of a regular graph, Strongly regular graphs and friendship theorem, Graphs with maximum energy.Line Graph of a Tree, Block graphs, Signless Laplacian matrix, Nullity of the line graph of a tree. Algebraic Connectivity, Classification of trees, Monotonicity properties of Fiedler vector, Bounds for algebraic connectivity. Distance Matrix of a Tree, Distance matrix of a graph, Distance matrix and Laplacian of a tree, Eigenvalues of the distance matrix of a tree. Positive Definite Completion Problem, Nonsingular completion, Chordal graphs, Positive definite completion.

Texts/References:

1. R. B. Bapat, Graphs and Matrices, Texts and Readings in Mathematics, Hindustan Book Agency, New Delhi, 2010.
2. D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, Academic Press, 1980.
3. C. Godsil and G. Royale, Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer, 2001.
4. N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1974.