Preliminaries&LOWELL W.BEINEKE and ROBIN J.WILSON 1
1.Graph theory 1
2.Connectivity 8
3.Flows in networks 10
1 Menger’s theorem&ORTRUD R.OELLERMANN 13
1.Introduction 13
2.Vertex-connectivity 14
3.Edge-connectivity 18
4.Mixed connectivity 19
5.Average connectivity 22
6.Menger results for paths of bounded length 28
7.Connectivity of sets 30
8.Connecting with trees 32
2 Maximally connected graphs&DIRK MEIERLING and LUTZ VOLKMANN 40
1.Introduction 40
2.Maximally edge-connected graphs 41
3.Maximally edge-connected digraphs 46
4.Maximally locally edge-connected graphs and digraphs 48
5.Maximally connected and maximally locally connected graphs and digraphs 50
6.Restricted edge-connectivity 54
7.Conditional vertex-connectivity and edge-connectivity 58
3 Minimal connectivity&MATTHIAS KRIESELL 71
1.Introduction 71
2.Edge-deletion 73
3.Vertex-deletion 74
4.Edge-contraction 79
5.Generalized criticality 81
6.Reduction methods 82
7.Subgraph-deletion 88
8.Partitions under connectivity constraints 91
9.Line graphs 94
4 Contractions of k-connected graphs&KIYOSHI ANDO 100
1.Introduction 100
2.Contractible edges in 3-connected graphs 101
3.Contractible edges in 4-connected graphs 102
4.Contractible edges in k-connected graphs 103
5.Contraction-critical 5-connected graphs 106
6.Local structure and contractible edges 109
7.Concluding remarks 111
5 Connectivity and cycles&R.J.FAUDREE 114
1.Introduction 114
2.Generalizations of classical results 115
3.Relative lengths of paths and cycles 117
4.Regular graphs 119
5.Bipartite graphs 122
6.Claw-free graphs 123
7.Planar graphs 128
8.The Chvatal-Erdos condition 131
9.Ordered graphs 132
10.Numbers of cycles 134
6 H-linked graphs&MICHAEL FERRARA and RONALD J.GOULD 141
1.Introduction 141
2.k-linked graphs 143
3.Weak linkage 149
4.Digraphs 150
5.Modulo and parity linkage 152
6.Disjoint connected subgraphs 154
7.The disjoint paths problem 154
8.H-linked graphs 155
9.H-extendible graphs 159
7 Tree-width and graph minors&DIETER RAUTENBACH and BRUCE REED 165
1.Introduction 165
2.Subtree intersection representation 166
3.Tree decomposition and tree-width 168
4.Tree decompositions decompose 173
5.Excluding planar minors 174
6.Wagner’s conjecture 175
7.The dual of tree-width 176
8.A canonical tree decomposition 178
9.Wagner’s conjecture for arbitrary graphs 180
10.Efficient characterization of H-minor-free graphs 181
8 Toughness and binding numbers&IAN ANDERSON 185
1.Introduction 185
2.Toughness and connectivity 187
3.Toughness and cycles 188
4.Toughness and k-factors 191
5.Binding number 194
6.Binding number and k-factors 196
7.Binding numbers and cycles 198
8.Other measures of vulnerability 198
9 Graph fragmentability&KEITH EDWARDS and GRAHAM FARR 203
1.Introduction 203
2.Values and bounds for fragmentability 206
3.Reduction and separation 207
4.Bounded degree classes 208
5.Planarization 210
6.Applications 214
7.Monochromatic components 215
8.Open problems 216
10 The phase transition in random graphs&BELA BOLLOBAS and OLIVER RIORDAN 219
1.Introduction 219
2.The Erdos-Renyi theorem：the double jump 223
3.Correction：no double jump 225
4.The phase transition - simple results 227
5.Exploring components 238
6.The phase transition - finer results 240
7.The young giant 243
8.Final words 247
11 Network reliability and synthesis&F.T.BOESCH，A.SATYANARAYANA and C.L.SUFFEL 251
1.Introduction 251
2.Domination in digraphs 252
3.Coherent systems and domination in graphs 255
4.Computational complexity of reliability 260
5.Synthesis of reliable networks 260
6.Other measures of vulnerability 263
12 Connectivity algorithms&ABDOL-HOSSEIN ESFAHANIAN 268
1.Introduction 268
2.Computing the edge-connectivity 269
3.Computing the arc-connectivity 274
4.Computing the vertex-connectivity 275
5.Concluding remarks 279
13 Using graphs to find the best block designs&R.A.BAILEY and PETER J.CAMERON 282
1.What makes a block design good？ 283
2.Graphs from block designs 284
3.Statistical issues 288
4.Highly patterned block designs 292
5.D-optimality 293
6.A-optimality 294
7.E-optimality 302
8.Some history 304
9.Block size 2 306
10.Low average replication 311
11.Further reading 314
Notes on contributors 318
Index 323