GTA Osmania University (OU) Syllabus


Preliminaries: Graphs, isomorphism, sub graphs, matrix representations, degree, operations on graphs, degree sequences. Connected graphs and shortest paths: Walks, trails, paths, connected graphs, distance, cut-vertices, cut-edges, blocks, connectivity, weighted graphs, shortest path algorithms Trees: Characterizations, number of trees, minimum spanning trees

Special classes of graphs: Bipartite graphs, line graphs, chordal graphs
Eulerian graphs: Characterization, Fleury’s algorithm, chinese-postman-problem

Hamilton graphs: Necessary conditions and sufficient conditions Independent sets, coverings, matchings: Basic equations, matching sin bipartite graphs, perfect matchings, greedy and approximation algorithms

Vertex colorings: Chromatic number and cliques, greedy coloring algorithm, coloring of chordal graphs, Brook’s theorem
Edge colorings: Gupta-Vizing theorem, Class-1 graphs and class-2 graphs, equitable edge-coloring

Planar graphs: Basic concepts, Euler’s formula, polyhedrons and planar graphs, characterizations, planarity testing, 5-color-theorem.
Directed graphs: Out-degree, in-degree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments

Suggested Reading:
1. F. Harry, Graph theory, Narosa Publications, 1988.
2. C.Berge: Graphs and Hypergraphs, North-Holland/Elsevier, 1973
3. J A Bondy and U.S. R Murthy, Graph Theory with Applications, Elsevier Science Ltd, 1976.
4. Douglas B West, Introduction to Graph Theory, Prentice-Hall, 2004

How useful was this post?

Click on a star to rate it!

Average rating 4.5 / 5. Vote count: 48

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Leave a Comment

Scroll to Top