Unit I : Independent Sets and Matching
Introduction, Vertex- independent sets and Vertex coloring, Edge-independent sets, Matchings and
Factors, Matchings in bipartite graphs, Perfect matchings and Tutte Matrix.
(12 Hours)
Unit II : Triangulated graphs
Introduction, Perfect graphs, Triangulated graphs, Interval graphs, Bipartite graph B(G) of a graph
G, Circular arc graphs. (12 Hours)
Unit III : Domination and Distances in Graphs
Domination numbers, Some elementary properties Bounds for domination number, Independent
domination and irredundance. Center, Periphery of a Graph and properties.
(12 Hours)
Unit IV : Spectral properties of graphs
Introduction, The spectrum of a graph, Spectrum of the complete graph, spectrum of the cycle,
Spectra of regular graphs, Spectra of complete bipartite graphs, The determinant of the adjacency
matrix of a graph, Spectra of product graphs. (12 Hours)
- Teacher: Dr Chandru Hegde