Modern Graph Theory

Front Cover
Springer Science & Business Media, 1998 - Computers - 394 pages
The time has now come when graph theory should be part of the education of every serious student of mathematics and computer science, both for its own sake and to enhance the appreciation of mathematics as a whole. This book is an in-depth account of graph theory, written with such a student in mind; it reflects the current state of the subject and emphasizes connections with other branches of pure mathematics. The volume grew out of the author's earlier book, Graph Theory -- An Introductory Course, but its length is well over twice that of its predecessor, allowing it to reveal many exciting new developments in the subject. Recognizing that graph theory is one of several courses competing for the attention of a student, the book contains extensive descriptive passages designed to convey the flavor of the subject and to arouse interest. In addition to a modern treatment of the classical areas of graph theory such as coloring, matching, extremal theory, and algebraic graph theory, the book presents a detailed account of newer topics, including Szemer\'edi's Regularity Lemma and its use, Shelah's extension of the Hales-Jewett Theorem, the precise nature of the phase transition in a random graph process, the connection between electrical networks and random walks on graphs, and the Tutte polynomial and its cousins in knot theory. In no other branch of mathematics is it as vital to tackle and solve challenging exercises in order to master the subject. To this end, the book contains an unusually large number of well thought-out exercises: over 600 in total. Although some are straightforward, most of them are substantial, and others will stretch even the most able reader.
 

Contents

Fundamentals
1
I2 Paths Cycles and Trees
8
I3 Hamilton Cycles and Euler Circuits
14
I4 Planar Graphs
20
I5 An Application of Euler Trails to Algebra
25
I6 Exercises
28
Electrical Networks
39
II2 Squaring the Square
46
VI3 Ramsey Theory For Graphs
192
VI4 Ramsey Theory for Integers
197
VI5 Subsequences
205
VI6 Exercises
208
VI7 Notes
213
Random Graphs
215
VII1 The Basic ModelsThe Use of the Expectation
216
VII2 Simple Properties of Almost All Graphs
225

II3 Vector Spaces and Matrices Associated with Graphs
51
II4 Exercises
58
II5 Notes
66
Hows Connectivity and Matching
67
III1 Flows in Directed Graphs
68
III2 Connectivity and Mengers Theorem
73
III3 Matching
76
III4 Tuttes 1Factor Theorem
82
III5 Stable Matchings
85
III6 Exercises
91
III7 Notes
101
Extremal Problems
103
IV1 Paths and Cycles
104
IV2 Complete Subgraphs
108
IV3 Hamilton Paths and Cycles
115
IV4 The Structure of Graphs
120
IV5 Szemeredis Regularity Lemma
124
IV6 Simple Applications of Szemeredis Lemma
130
IV7 Exercises
135
IV8 Notes
142
Colouring
145
V1 Vertex Colouring
146
V2 Edge Colouring
152
V3 Graphs on Surfaces
154
V4 List Colouring
161
V5 Perfect Graphs
165
V6 Exercises
170
V7 Notes
177
Ramsey Theory
181
VI1 The Fundamental Ramsey Theorems
182
VI2 Canonical Ramsey Theorems
189
VII3 Almost Determined Variables The Use of the Variance
228
VII4 Hamilton CyclesThe Use of Graph Theoretic Tools
236
VII5 The Phase Transition
240
VII6 Exercises
246
VII7 Notes
251
Graphs Groups and Matrices
253
VIII1 Cayley and Schreier Diagrams
254
VIII2 The Adjacency Matrix and the Laplacian
262
VIII3 Strongly Regular Graphs
270
VIII4 Enumeration and Polyas Theorem
276
VIII5 Exercises
283
Random Walks on Graphs
295
IX1 Electrical Networks Revisited
296
IX2 Electrical Networks and Random Walks
301
IX3 Hitting Times and Commute Times
309
IX4 Conductance and Rapid Mixing
319
IX5 Exercises
327
IX6 Notes
333
The Tutte Polynomial
335
X1 Basic Properties of the Tutte Polynomial
336
X2 The Universal Form of the Tutte Polynomial
340
X3 The Tutte Polynomial in Statistical Mechanics
342
X4 Special Values of the Tutte Polynomial
345
X5 A Spanning Tree Expansion of the Tutte Polynomial
350
X6 Polynomials of Knots and Links
358
X7 Exercises
371
X8 Notes
377
Symbol Index
379
Name Index
383
Subject Index
387
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information