Syllabus For The Subject GRAPH THEORY

UNIT - 01

GRAPHS AND SUB-GRAPS AND SIMPLE GRAPHS - GRAPH ISOMORPHISM - THE INCIDENE

AND ADJACENCY MATRICES.

UNIT - 02

SUB-GRAPHS - VERTEXDEGREES - PATH PROBLEMS.

UNIT - 03

TREES - CUT EDGES AND BOUNDS - CUT VERTICES - CAYLEY`S FORMULA AND THE

CONNECTOR PROBLEM.

UNIT - 04

CONNECTIVITY - BLOCKS AND CONSTRUCTION OF RELIABLE COMMUNICATION

NETWORK - EULER TOURS - HAMILTON CYCLES.

UNIT - 05

THE CHINESE POSTMAN PROBLEM AND THE TRAVELING SALESMAN PROBLEM.

UNIT - 06

MATCHINGS AND COVERINGS IN BIPARTITE GRAPHS - PERFECT MATCHINGS - THE

PERSONNEL ASSIGNMENT PROBLEM AND THE OPTIMAL ASSIGNMENT PROBLEM - EDGE

- COLORINGS.

UNIT - 07

EDGE CHROMATIC NUMBER - VIZINGS`S THEOREM AND THE TABLING PROBLEM.

UNIT - 08

INDEPENDENT SETS - RAMSEY`S THEOREM - TURAN`S THEOREM - SCHUR`S THEOREM

AND A GEOMETRY PROBLEM VERTEX COLORINGS.

UNIT - 09

CHROMATIC NUMBERS - BROOK`S THEOREM - HAJO`S CONJECTURE - CHROMATIC

POLYNOMIALS - GIRTH AND CHROMATIC NUMBER AND A STORAGE PROBLEM.

UNIT - 10

PLAN GRAPHS - PLANE AND PLANER GRAPHS - DUAL GRAPHS - EULER`S FORMULA -

BRIDGES - KURATOWSKI`S THEOREM.

UNIT - 11

THE FIVE COLOR THEOREM AND THE FOUR COLOR CONJUNCTIONS NON-HAMILTONIAN

PLANER GRAPHS AND A PLANARITY ALGORITHM.

UNIT - 12

DIRECTED GRAPHS - DIRECTED PATH - DIRECTED CYCLES - A JOB SEQUENCING

PROBLEM - DESIGNING AN EFFICIENT COMPUTER DRUM - MAKING A ROAD SYSTEM ONE

WAY AND RANKING THE PARTICIPANTS IN A TREATMENT.

Vinayaka Missions University,Directorate of Distance Education

Salem India

MASTER OF SCIENCE IN MATHEMATICS

2 Yr.

GRAPH THEORY(2030512)