Course

Syllabus

Graph Theory: An Introduction to Graph theory, Definition and examples, Subgraph, Complements and Graph Isomorphism, Vertex Degree: Euler Trials and Circuits, Planar Graphs, Hamilton Paths and Cycles, Probabilistic graph, Social Graphs, Applications in Social Networks, Graph Coloring and Chromatic Polynomials, Digraph, Dijkstra’s Shortest-Path Algorithm , maximal matching- perfect matching – k-factor graphs. 

Tree: Properties of Trees, Distances and centers in a tree, Spanning Tree, Minimal and Maximal spanning tree, The Algorithms of Kruskal and Prim, Transport Network: The Max-Flow Min-cut Theorem, Weighted Trees and Prefix Codes Vertex and Horizontal constrained graphs, Interval, Permutations and Intersection graphs with simple properties. 

Algorithms and Applications: Shortest and longest path algorithm, Minimal and Maximal spanning tree algorithms, maximal matching algorithms, Coloring algorithms, Graph Partitioning algorithm. 

Research Paper Discussion and Presentation on applied graph theory in wireless networks. 

Course Outcomes: 

1. Frank Harary, “Graph Theory”, Narosa Publishing house, 2001.  
2. Douglas B.West, “Graph Theory”, Second Edition, Pearson Education, 2001.  
3. Alan Gibbons, “Algorithmic Graph Theory”, Cambridge University Press, 1985