Foreword by Ortrud R. Oellermann ............................... xi
Preface ...................................................... xiii
Preliminaries ................................................ 1
LOWELL W. BEINEKE and ROBIN J. WILSON
1 Graph theory .............................................. 1
2 Connectivity .............................................. 8
3 Flows in networks ........................................ 10
1 Menger's theorem ............................................ 13
ORTRUD R. OELLERMANN
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 .................................. 40
DIRK MEIERLING and LUTZ VOLKMANN
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 ........................................ 71
MATTHIAS KRIESELL
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 ......................... 100
KIYOSHI ANDO
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 .................................... 114
R.J. FAUDREE
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 Chvátal-Erdos condition ............................. 131
9 Ordered graphs .......................................... 132
10 Numbers of cycles ....................................... 134
6 H-linked graphs ............................................ 141
MICHAEL FERRARA and RONALD J. GOULD
1 Introduction ............................................ 141
2 fc-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 ................................ 165
DIETER RAUTENBACH and BRUCE REED
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 .............................. 185
IAN ANDERSON
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 ...................................... 203
KEITH EDWARDS and GRAHAM FARR
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 ...................... 219
BÉLA BOLLOBÁS and OLIVER RIORDAN
1. Introduction ............................................ 219
2 The Erdős-Rényi 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 .......................... 251
F.T. BOESCH, A. SATYANARAYANA and C.L. SUFFEL
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 .................................... 268
ABDOL-HOSSEIN ESFAHANIAN
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 ................ 282
R.A. BAILEY and PETER J. CAMERON
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
|
