The present book is based on the curriculum of undergraduate and postgraduate courses of universities in India and abroad. Every effort is made to present the various topics in the theory of graphs in a logical manner with adequate historical background and include suitable figures to illustrate concepts and results ideally. The formidable exercises, neither easy nor straightforward, are bold faced and highlighted. The theory portion of each chapter is studied thoroughly as it helps solve many of the problems with comparative ease. Selected material from this book is used for a semester course on graph theory, while the entire book serves for a whole session course.
Author(s): Santosh Kumar Yadav
Edition: 1
Publisher: Springer
Year: 2023
Language: English
Pages: 299
City: Cham
Tags: Graph Encodings; Ramanujan Graphs; Span Function; Tarjan’s Theorem; Perfectly Orderable Graph; Minimal Imperfect Graph; Vertex Colouring; Planar Graphs; Minimal Spanning Trees; Hamiltonian Graph; Eulerian Graph; 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
