Advanced Graph Theory

Preface
Acknowledgments
Contents
1
Basics of Graph Theory
	1.1 Introduction
	1.2 Graph! What is it?
		1.2.1 Simple Graph
		1.2.2 Graph
		1.2.3 Loops
		1.2.4 Degree of Vertices
		1.2.5 Equivalence Relation
		1.2.6 Random Graph Model
	1.3 Digraphs
	1.4 Path, Trail, Walk and Vertex Sequence
	1.5 Subgraph
	1.6 Circuit and Cycle
	1.7 Cycles and Multiple Paths
	1.8 Connected Graph
	1.9 Spanning Subgraph and Induced Subgraph
	1.10 Eulerian Graph (Eulerian Trail and Circuit)
	1.11 Hamiltonian Graph
	1.12 Biconnected Graph
	1.13 Algebraic terms and operations used in Graph Theory
		1.13.1 Graphs Homomarphism and Graph Isomorphism
		1.13.2 Union of two Graphs
		1.13.3 Intersection of two Graphs
		1.13.4 Addition of two Graphs
		1.13.5 Direct Sum or Ring Sum of two Graphs
		1.13.6 Product of two Graphs
		1.13.7 Composition of two Graphs
		1.13.8 Complement of a Graph
		1.13.9 Fusion of a Graph
		1.13.10 Rank and Nullity
		1.13.11 Adjacency Matrix
		1.13.12 Some Important Theorems
	1.14 Some Popular Problems in Graph Theory
		1.14.1 Tournament Ranking Problem
		1.14.2 The Königsberg Bridge Problem
		1.14.3 Four Colour Problem
		1.14.4 Three Utilities Problem
		1.14.5 Traveling - Salesman Problem
		1.14.6 MTNL’S Networking Problem
		1.14.7 Electrical Network Problems
		1.14.8 Satellite Channel Problem
	1.15 Applications of Graphs
	1.16 Worked Examples
	SUMMARY
	EXERCISES
	Suggested Readings
2
Trees
	2.1 Introduction
	2.2 Definitions of Tree
	2.3 Forest
	2.4 Rooted Graph
	2.5 Parent, Child, Sibling and Leaf
	2.6 Rooted Plane Tree
	2.7 Binary Trees
	2.8 Spanning Trees
	2.9 Breadth – First Search and Depth – First Search (BFS and DFS)
	2.10 Minimal Spanning Trees
		2.10.1 Kruskal’s Algorithm (for Finding a Minimal Spanning Tree)
		2.10.2 Prim’s Algorithm
		2.10.3 Dijkstra’s Algorithm
		2.10.4 The Floyd-Warshall Algorithm
	2.11 Directed Trees
	2.12 Solved Examples
	SUMMARY
	EXERCISES
	Suggested Readings
3
Planar Graphs
	3.1 Introduction
	3.2 Geometrical Representation of Graphs
	3.3 Bipertite Graph
	3.4 Homeomorphic Graph
	3.5 Kuratowski’s Graphs
	3.6 Dual Graphs
	3.7 Euler’s Formula
	3.8 Outerplanar Graphs
		3.8.1 k-outerplanar Graphs
	3.9 Solved Examples
	SUMMARY
	EXERCISES
	Suggested Readings
4
Directed Graphs
	4.1 Introduction
	4.2 Directed Paths
	4.3 Tournament
	4.4 Directed Cycles
	4.5 Acyclic Graph
	4.6 Di-Orientable Graph
	4.7 Applications of Directed Graphs
		4.7.1 Job Sequencing Problem
		4.7.2 To Design an Efficient Computer Drum
		4.7.3 Ranking of the Participants in a Tournament
	4.8 Network Flows
	4.9 Improvable Flows
	4.10 Max-Flow Min-Cut Theorem
	4.11 k-flow
	4.12 Tutte’s Problem
	SUMMARY
	EXERCISES
	Suggested Readings
5
Matching & Covering
	5.1 Introduction
	5.2 Matching and Covering in Bipertite Graphs
		5.2.1 Covering
	5.3 Perfect Matching
	5.4 Factor-critical Graph
	5.5 Complete Matching
	5.6 Matrix Method to Find Matching of a Bipertite Graph
	5.7 Path Covers
	5.8 Applications
		5.8.1 The Personnel Assignment Problem
		5.8.2 The Optimal Assignment Problem
		5.8.3 Covering to Switching Functions
	SUMMARY
	EXERCISES
	Suggested Readings
6
Colouring of Graphs
	6.1 Introduction
	6.2 Vertex Colouring
	6.3 Chromatic Polynomial
		6.3.1 Bounds of the Chromatic Number
		6.3.2 Clique
	6.4 Exams Scheduling Problem
	6.5 Edge Colouring
	6.6 List Colouring
	6.7 Greedy Colouring
	6.8 Applications
		6.8.1 The Time Table Problem
		6.8.2 Scheduling of Jobs
		6.8.3 Ramsey Theory
		6.8.4 Storage Problem
		SUMMARY
		EXERCISES
		Suggested Readings
7
Ramsey Theory for Graphs
	7.1 Introduction
	7.2 Independent Sets and Cliques
	7.3 Original Ramsey’s Theorems
	7.4 Induced Ramsey Theorems
	7.5 Applications
		7.5.1 Schur’s Theorem
		7.5.2 Geometry Problem
	SUMMARY
	EXERCISES
	Suggested Readings
8
Enumeration and Pölya’s Theorem
	8.1 Introduction
	8.2 Labelled Counting
	8.3 Unlabelled Counting
	8.4 Generating Function
	8.5 Partitions of a Finite Set
	8.6 The Labelled counting Lemma
	8.7 Permutations
		8.7.1 Cycle Index
	8.8 Pölya’s Enumeration Theorem
	SUMMARY
	EXERCISES
	Suggested Readings
9
Spectral Properties of Graphs
	9.1 Introduction
	9.2 Spectrum of the Complete Graph Kn
	9.3 Spectrum of the Cycle Cn
	9.4 Spectra of Regular Graphs Theorem
	9.5 Theorem of the Spectrum of the Complement of a Regular Graph
	9.6 Sachs’ Theorem
	9.7 Cayley Graphs and Spectrum
	SUMMARY
	EXERCISES
	Suggested Readings
10
Emerging Trends in Graph Theory
	10.1 Introduction
	10.2 Perfect Graphs
	10.3 Chordal Graphs Revisited
	10.4 Intersection Representation
	10.5 Tarjan’s Theorem (1976)
	10.6 Perfectly Orderable Graph
	10.7 Minimal Imperfect Graph
		10.7.1 Star-cutset Lemma
	10.8 Imperfect Graphs
	10.9 Strong Perfect Graph Coryecture
	10.10 Hereditary Family
	10.11 Matroids
		10.11.1 Hereditary Systems
		10.11.2 Rank Function in Cycle Matroids
	10.12 Basic Properties of Matroids
	10.13 Span Function
	10.14 Encodings of Graphs
	10.15 Ramanujan Graphs
	EXERCISES
	Suggested Readings
References
Index