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.

#### Syllabus

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

#### References

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.