Advanced Graph Theory

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. 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