Unit 1
Rules of sum and products, Permutation, Combination, Permutation groups and application, Probability, Ramsey theory, Discrete numeric function and generating function, Combinatorial problems, Difference equation.
Unit II
Recurrence Relation-Introduction, Linear recurrence relation with constant coefficient,
Homogeneous solution, Particular solution, Total solution, Solution by the method of generating function.
Unit III
Graphs, sub-graphs, some basic properties, Walks, Path & circuits, Connected graphs, Disconnected graphs and component, Eular and Hamiltonian graphs, Various operation on graphs, Tree and fundamental circuits, Distance diameters, Radius and pendent vertices, Rooted and binary trees, Counting trees, Spanning trees, Finding all spanning trees of a graph and a weighted graph.
Unit IV
Cut-sets and cut vertices, some properties, All cut sets in a graph, Fundamental circuit and cut sets, Connectivity and seperatability, Network flows, mincut theorem, Planar graphs, Combinatorial and geometric dual, Kuratowski to graph detection of planarity, Geometric dual, Some more criterion of planarity, Thickness and Crossings, Vector space of a graph and vectors, basis vectors, cut set vector, circuit vector, circuit and cut set verses sub spaces, orthogonal vector and sub space.
Incidence matrix of graphs, sub matrices of A(G), circuit matrix, cut set matrix, path matrix and relationship among Af, Bf, Cf, fundamental circuit matrix and range of Bf adjacency matrix, rank nullity theorem.
Unit V
Coloring and covering partitioning of graph, Chromatic number, Chromatic partitioning, Chromatic polynomials, Matching, covering, Four color problem, Directed graph, Types of directed graphs, Directed paths and connectedness, Euler digraph, Trees with directed edges, Fundamental circuit in digraph, Matrices A, B, C of digraph adjacency matrix of digraph, Enumeration and its types, Counting of labeled and unlabeled trees, Polya’s theorem, Graph enumeration with polyas theorem, Graph theoretic algorithm.
References
1. Deo Narsing, “Graph Theory with applications to engineering & computer science”, PHI
2. Tremblay & Manohar, “ Discrete mathematical structures with applications to computer
Science”, TMH
3. Joshi K. D., “Fundamental of discrete mathematics”, New Age International
4. John Truss, “Discrete mathematics for computer scientist”
5. C. L. Liu, “Discrete mathematics”