Back close

Course Detail

Course Name Advanced Graph Theory and its Applications
Program M.Phil. in Mathematics (Offered at Kochi Campus)
Year Taught 2019
Degree Postgraduate (PG)
School School of Arts and Sciences
Campus Kochi


Unit 1:

Introduction: Definition of graph-degree of vertex- Regular graphs – Connected graph, complete graphs – Bipartite graph – Euler graph necessary and sufficient conditions for Euler graph-Hamiltonian graph and its properties – Connectivity, vertex connectivity, edge connectivity.Trees – properties of Trees-spanning tree

Unit 2:

Domination theory – Definition of dominating sets in graphs- Domination number- bounds in terms of degree, diameter and girth- product graphs and Vizing’sconjecture

Unit 3:

Changing and unchanging domination – changing vertex removal – changing edge removal – bondage number – unchanging vertex removal – unchanging edge removal

Unit 4:

Four Standard Graph Products – Cartesian Product – Strong Product – Direct Product – Lexicographic Product – distance formula

Unit 5:

Three Fundamental Products – Commutativity property, Associativity property -Projections and Layers


  1. Richard Hammack, WilfriedImrich and SandiKlavzar,Handbook OfProduct Graphs, CRC Press, 2nd edition 2011.
  2. Douglas B. West, Introduction to graph Theory, Second Edition, Pearson Publication, 2001.
  3. Teresa W Hynes, Stephen T. Hedetniemi and Peter. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker INC, New York.

DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.

Admissions Apply Now