Advanced Graph Theory

ISBN-13: 9783031225611 / Angielski / Twarda / 2023

Santosh Kumar Yadav

Opis

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.

Spis treści

1. Basics of Graph Theory 1–50
1.1 Introduction 1
1.2 Graph! What is it? 2
1.2.1 Simple Graph 2
1.2.2 Graph 4
1.2.3 Loops 7
1.2.4 Degree of Vertices 7
1.2.5 Equivalence Relation 10
1.2.6 Random Graph Model 13
1.2.7 Isolated Vertex, Pendent Vertex and Null Graph 13
1.3 Digraphs 14
1.4 Path, Trail, Walk and Vertex Sequence 17
1.5 Subgraph 18
1.6 Circuit and Cycle 18
1.7 Cycles and Multiple Paths 19
1.8 Connected Graph 19
1.9 Spanning Subgraph and Induced Subgraph 20
1.10 Eulerian Graph (Eulerian Trail and Circuit) 21
1.11 Hamiltonian Graph 22
1.12 Biconnected Graph 22
1.13 Algebraic Terms and Operations used in Graph Theory 23
1.13.1 Graphs Homomarphism and Graph Isomorphism 23
1.13.2 Union of two Graphs 25
1.13.3 Intersection of two Graphs 25
1.13.4 Addition of two Graphs 25
1.13.5 Direct Sum or Ring Sum of two Graphs 26
1.13.6 Product of two Graphs 26
1.13.7 Composition of two Graphs 27
1.13.8 Complement of a Graph 27
1.13.9 Fusion of a Graph 28
1.13.10 Rank and Nullity 28
1.13.11 Adjacency Matrix 29
1.13.12 Some Important Theorems 29
1.14 Some Popular Problems in Graph Theory 34
1.14.1 Tournament Ranking Problem 34
1.14.2 The Königsberg Bridge Problem 36
1.14.3 Four Colour Problem 36
1.14.4 Three Utilities Problem 37
1.14.5 Traveling - Salesman Problem 37
1.14.6 MTNL’S Networking Problem 38
1.14.7 Electrical Network Problems 38
1.14.8 Satellite Channel Problem 39
1.15 Applications of Graphs 40
1.16 Worked Examples 40
Summary 46
Exercise 48
Suggested Readings 50
2. Trees 51–88
2.1 Introduction 51
2.2 Definitions of Tree 52
2.3 Forest 53
2.4 Rooted Graph 54
2.5 Parent, Child, Sibling and Leaf 55
2.6 Rooted Plane Tree 55
2.7 Binary Trees 61
2.8 Spanning Trees 63
2.9 Breadth – First Search and Depth – First Search 64
2.10 Minimal Spanning Trees 71
2.10.1 Kruskal’s Algorithm (for Finding a Minimal Spanning Tree) 71
2.10.2 Prim’s Algorithm 76
2.10.3 Dijkstra’s Algorithm 78
2.10.4 The Floyd-Warshall Algorithm 79
2.11 Directed Trees 80
2.12 Solved Examples 81
Summary 86
Exercise 87
Suggested Readings 88
xii Advanced Graph Theory
3. Planar Graphs 89–110
3.1 Introduction 89
3.2 Geometrical Representation of Graphs 90
3.3 Bipertite Graph 92
3.4 Homeomorphic Graph 93
3.5 Kuratowski’s Graphs 94
3.6 Dual Graphs 98
3.7 Euler’s Formula 100
3.8 Outerplanar Graphs 102
3.8.1 k-outerplanar Graphs 103
3.9 Solved Examples 103
Summary 108
Exercise 109
Suggested Readings 109
4. Directed Graphs 111–140
4.1 Introduction 111
4.2 Directed Paths 113
4.3 Tournament 114
4.4 Directed Cycles 116
4.5 Acyclic Graph 119
4.6 Di-Orientable Graph 120
4.7 Applications of Directed Graphs 124
4.7.1 Job Sequencing Problem 124
4.7.2 To Design an Efficient Computer Drum 125
4.7.3 Ranking of the Participants in a Tournament 127
4.8 Network Flows 129
4.9 Improvable Flows 130
4.10 Max-Flow Min-Cut Theorem 131
4.11 k-flow 133
4.12 Tutte’s Problem 134
Summary 136
Exercise 137
Suggested Readings 139
5. Matching and Covering 141–170
5.1 Introduction 141
5.2 Matching and Covering in Bipertite Graphs 143
5.2.1 Covering 147
5.3 Perfect Matching 149
Contents xiii
5.4 Factor-critical Graph 153
5.5 Complete Matching 155
5.6 Matrix Method to Find Matching of a Bipertite Graph 157
5.7 Path Covers 160
5.8 Applications 161
5.8.1 The Personnel Assignment Problem 161
5.8.2 The Optimal Assignment Problem 165
5.8.3 Covering to Switching Functions 166
Summary 168
Exercise 168
Suggested Readings 170
6. Colouring of Graphs 171–200
6.1 Introduction 171
6.2 Vertex Colouring 173
6.3 Chromatic Polynomial 174
6.3.1 Bounds of the Chromatic Number 175
6.3.2 Clique 175
6.4 Exams Scheduling Problem 179
6.5 Edge Colouring 186
6.6 List Colouring 190
6.7 Greedy Colouring 192
6.8 Applications 196
6.8.1 The Time Table Problem 196
6.8.2 Scheduling of Jobs 196
6.8.3 Ramsey Theory 197
6.8.4 Storage Problem 197
Summary 198
Exercise 198
Suggested Readings 199
7. Colouring of Graphs 201–220
7.1 Introduction 201
7.2 Independent Sets and Cliques 203
7.3 Original Ramsey’s Theorems 204
7.4 Induced Ramsey Theorems 208
7.5 Applications 213
7.5.1 Schur’s Theorem 213
7.5.2 Geometry Problem 214
Summary 218
Exercise 218
Suggested Readings 219
xiv Advanced Graph Theory
8. Enumeration and Pölya’s Theorem 221–242
8.1 Introduction 221
8.2 Labelled Counting 222
8.3 Unlabelled Counting 223
8.4 Generating Function 225
8.5 Partitions of a Finite Set 228
8.6 The Labelled counting Lemma 230
8.7 Permutations 231
8.7.1 Cycle Index 232
8.8 Pölya’s Enumeration Theorem 232
8.9 Burnside’s Lemma 235
Summary 240
Exercise 241
Suggested Readings 242
9. Spectral Properties of Graphs 243–252
9.1 Introduction 243
9.2 Spectrum of the Complete Graph Kn 245
9.3 Spectrum of the Cycle Cn 246
9.4 Spectra of Regular Graphs Theorem 246
9.5 Theorem of the Spectrum of the Complement of a Regular Graph 247
9.6 Sachs’ Theorem 248
9.7 Cayley Graphs and Spectrum 250
Summary 251
Exercise 252
Suggested Readings 252
10. Emerging Trends in Graph Theory 253–280
10.1 Introduction 253
10.2 Perfect Graphs 253
10.3 Chordal Graphs Revisited 257
10.4 Intersection Representation 257
10.5 Tarjan’s Theorem (1976) 258
10.6 Perfectly Orderable Graph 261
10.7 Minimal Imperfect Graph 261
10.7.1 Star-cutset Lemma 261
10.8 Imperfect Graphs 262
10.9 Strong Perfect Graph Coryecture 266
10.10 Hereditary Family 267
10.11 Matroids 267
Contents xv
10.11.1 Hereditary Systems 268
10.11.2 Rank Function in Cycle Matroids 269
10.12 Basic Properties of Matroids 270
10.13 Span Function 271
10.14 Encodings of Graphs 275
10.15 Ramanujan Graphs 276
Exercise 278
Suggested Readings 279
References 281–282
Index 283–286

O autorze

Dr.Santosh Kumar Yadav has been associated with academic and research activities for more than 25 years. He has been an active and dynamic administrator as the director (Academic and Research) at J.J.T. University, Rajasthan. As an academician, he has taught undergraduates and postgraduate classes in different premier institutions including various colleges of Delhi University in different capacities.