Graph theory

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