COURSE SUMMARY
Course Title: 
Advanced Graph Theory and its Applications
Course Code: 
18MAT731
Year Taught: 
2019
Semester: 
2
Type: 
Elective
Degree: 
Doctoral Programs
School: 
School of Arts and Sciences
Campus: 
Kochi

'Advanced Graph Theory and its Applications' is an elective course offered in the second semester of M.Phil. in Mathematics program (Full Time/Part Time) offered by School of Arts & Sciences, 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.