Home

Syllabus Graph Theory

Syllabus :

  1. Fundamental Concepts:

    • Graphs, Matrices and isomorphism decomposition, connection in Graphs, bipartite

      graphs, Eulerian circuits, vertex degrees, and Graphic sequences.

  2. Trees and Distance:

    • Trees, Distance in trees and Graphs, Enumeration of trees Caycley’s formula, Spanning

      trees in graphs, minimum spanning trees, Kruskal’s algorithm, shortest paths, Dijkstra’s

      Algorithm.

  3. Matchings:

    • Maximum Matchings, Hall’s matching condition, Min-Max Theorems, Maximum

      bipartite Matching, weighted bipartite matching.

  4. Connectivity and Paths:

    • Connectivity, edge-connectivity, blocks, 2-connected graphs, k-connected and k-edge-connected graphs, Menger’s Theorem, Maximum Network flow, Max-flow min-cut Theorem.

 

Text Book :

  • West D.B. Introduction to Graph Theory (Second edition), Prentice Hall of India,New Delhi (2009). Chapters : 1, 2, 3.1, 3.2, 4.

Reference Books :

  • J. Clark, D.A. Holton, A First Look at Graph Theory, Allied Publishers.

  • R. J. Wilson, Introduction to Graph Theory, (Fourth Edition), Pearson Education, Singapore (2003).