Graph Theory

This text offers the most comprehensive and up-to-date presentation available on the fundamental topics in graph theory. It develops a thorough understanding of the structure of graphs, the techniques used to analyze problems in graph theory and the uses of graph theoretical algorithms in mathematics, engineering and computer science. There are many new topics in this book that have not appeared before in new proofs of various classical theorems, signed degree sequences, criteria for graphical sequences, eccentric sequences, matching and decomposition of planar graphs into trees. Scores in digraphs appear for the first time and include new results due to Pirzada. The climax of the book is a new proof of the famous four colour theorem due to Dharwadker. Preface......Page 2 Contents......Page 4 Basic Concepts......Page 5 Degrees......Page 7 Isomorphism......Page 8 Types of graphs......Page 11 Graph properties......Page 15 Paths, Cycles and Components......Page 16 Operations on Graphs......Page 26 Topological Operations......Page 30 Distance and eccentricity......Page 37 Exercises......Page 39 Degree Sequences......Page 41 Criteria for Degree Sequences......Page 42 Degree Set of a Graph......Page 53 New Criterion......Page 55 Equivalence of Seven Criteria......Page 57 Signed Graphs......Page 59 Exercises......Page 62 Euler Graphs......Page 63 Konigsberg Bridge Problem......Page 65 Unicursal Graphs......Page 68 Arbitrarily Traceable Graphs......Page 69 Sub-Eulerian Graphs......Page 70 Hamiltonian Graphs......Page 71 Pancyclic Graphs......Page 79 Exercises......Page 82 Basics......Page 83 Rooted and Binary Trees......Page 87 Number of Labelled Trees......Page 95 The Fundamental Cycles......Page 99 Generation of Trees......Page 100 Helly Property......Page 104 Signed Trees......Page 105 Exercises......Page 107 Basic Concepts......Page 109 Cut Vertex Tree......Page 114 Connectivity Parameters......Page 116 Menger’s Theorem......Page 123 Some Properties of a Bond......Page 126 Fundamental Bonds......Page 127 Block Graphs and Cut Vertex Graphs......Page 132 Exercises......Page 136 Planarity......Page 138 Kuratowski’s Two Graphs......Page 139 Region......Page 141 Euler’s Theorem......Page 143 Kuratowski’s Theorem......Page 149 Geometric Dual......Page 151 Polyhedron......Page 157 Decomposition of Some Planar Graphs......Page 163 Exercises......Page 165 Vertex colouring......Page 167 Critical Graphs......Page 170 Brook’s Theorem......Page 174 Edge colouring......Page 181 Region Colouring (Map Colouring)......Page 187 Heawood Map-Colouring Theorem......Page 194 Uniquely Colourable Graph......Page 196 Hajos Conjecture......Page 198 Exercises......Page 200 Matchings......Page 202 Factors......Page 212 Antifactor Sets......Page 219 -factor Theorem......Page 224 Degree Factors......Page 232 ]-factors......Page 235 Exercises......Page 236 Edge Graphs......Page 238 Edge Graphs and Traversability......Page 250 Total Graphs......Page 253 Eccentricity Sequences and Sets......Page 254 Distance Degree Regular and Distance Regular Graphs......Page 262 Isometry......Page 263 Exercises......Page 265 Incidence Matrix......Page 267 Submatrices of......Page 271 Cycle Matrix......Page 275 Cut-Set Matrix......Page 282 Fundamental Cut-Set Matrix......Page 285 and......Page 286 Path Matrix......Page 289 Adjacency Matrix......Page 292 Exercises......Page 299 Basic Definitions......Page 300 Digraphs and Binary Relations......Page 302 Directed Paths and Connectedness......Page 304 Euler Digraphs......Page 310 Hamiltonian digraphs......Page 311 Trees with Directed Edges......Page 314 Matrices A, B and C of Digraphs......Page 318 Number of Arborescences......Page 330 Tournaments......Page 333 Exercises......Page 337 Introduction......Page 339 Map Colouring......Page 340 Steiner Systems......Page 342 Eilenberg Modules......Page 344 Hall Matchings......Page 347 Riemann Surfaces......Page 348 Main Construction......Page 356 Graph Algorithms......Page 370 Dijkstra’s Algorithm for Shortest Paths......Page 371 Prim’s Algorithm for Minimal Spanning Tree......Page 382 Fleury’s Algorithm for Eulerian Circuit......Page 391 De Bruijn Graphs......Page 397 Hamiltonian Circuits......Page 399 Score Sequences in Tournaments......Page 407 Frequency Sets in Tournaments......Page 414 Lexicographic Enumeration and Tournament Construction......Page 417 Simple Score Sequences in Tournaments......Page 421 Score Sequences of Bipartite Tournaments......Page 422 Uniquely Realisable (Simple) Pairs of Score Sequences......Page 428 Score Sequences of Oriented Graphs......Page 432 Score Sets in Oriented Graphs......Page 435 Uniquely Realisable (Simple) Score Sequences in Oriented Graphs......Page 438 Score Sequences in Oriented Bipartite Graphs......Page 440 Score Sequences of Semi Complete Digraphs......Page 443 Refs......Page 446