>>Send ur suggestion to Mynotes Tab
Unit- I
Graphs, Sub graphs, some basic properties, various example of graphs & their sub graphs, walks, path & circuits, connected graphs, disconnected graphs and component, euler graphs, various operation on graphs, Hamiltonian paths and circuits, the traveling sales man problem.
Unit- II
Trees and fundamental circuits, distance diameters, radius and pendent vertices, rooted and binary trees, on counting trees, spanning trees, fundamental circuits, finding all spanning trees of a graph and a weighted graph, algorithms of primes, Kruskal and dijkstra Algorithms.
Unit -III
Cuts sets and cut vertices, some properties, all cut sets in a graph, fundamental circuits and cut sets , connectivity and separability, network flows, planer graphs, combinatorial and geometric dual, Kuratowski to graphs detection of planarity, geometric dual , some more criterion of
planarity, thickness and crossings.
Unit -IV
Vector space of a graph and vectors, basis vector, cut set vector, circuit vector, circuit and cut set verses subspaces, orthogonal vectors and subspaces, incidence matrix of graph, sub matrices of A(G), circuit matrix, cut set matrix, path matrix and relationships among A, B , and C , fundamental circuit matrix and rank of B, adjacency matrices, rank- nullity theorem .
Unit -V
Coloring and covering and partitioning of a graph, chromatic number, chromatic partitioning, chromatic polynomials, matching, covering, four color problem, Directed graphs, some type of directed graphs, Directed paths, and connectedness, Euler digraphs, trees with directed edges, fundamental
circuits in digraph, matrices A, B and C of digraphs adjacency matrix of a digraph,, enumeration, types of enumeration, counting of labeled and unlabeled trees, polya’s theorem, graph enumeration with polya’s theorem. Graph theoretic algorithm must be provided wherever required to solve the problems .
References:-
1. Deo, N: Graph theory, PHI
Direct Link
2. Harary, F: Graph Theory, Narosa
Direct Link
3. Bondy and Murthy: Graph theory and application. Addison Wesley.