Preliminaries&LOWELL W.BEINEKE and ROBIN J.WILSON

1.Graph theory

2.Connectivity

3.Flows in networks

1 Menger’s theorem&ORTRUD R.OELLERMANN

1.Introduction

2.Vertex-connectivity

3.Edge-connectivity

4.Mixed connectivity

5.Average connectivity

6.Menger results for paths of bounded length

7.Connectivity of sets

8.Connecting with trees

2 Maximally connected graphs&DIRK MEIERLING and LUTZ VOLKMANN

1.Introduction

2.Maximally edge-connected graphs

3.Maximally edge-connected digraphs

4.Maximally locally edge-connected graphs and digraphs

5.Maximally connected and maximally locally connected graphs and digraphs

6.Restricted edge-connectivity

7.Conditional vertex-connectivity and edge-connectivity

3 Minimal connectivity&MATTHIAS KRIESELL

1.Introduction

2.Edge-deletion

3.Vertex-deletion

4.Edge-contraction

5.Generalized criticality

6.Reduction methods

7.Subgraph-deletion

8.Partitions under connectivity constraints

9.Line graphs

4 Contractions of k-connected graphs&KIYOSHI ANDO

1.Introduction

2.Contractible edges in 3-connected graphs

3.Contractible edges in 4-connected graphs

4.Contractible edges in k-connected graphs

5.Contraction-critical 5-connected graphs

6.Local structure and contractible edges

7.Concluding remarks

5 Connectivity and cycles&R.J.FAUDREE

1.Introduction

2.Generalizations of classical results

3.Relative lengths of paths and cycles

4.Regular graphs

5.Bipartite graphs

6.Claw-free graphs

7.Planar graphs

8.The Chvatal-Erdos condition

9.Ordered graphs

10.Numbers of cycles

6 H-linked graphs&MICHAEL FERRARA and RONALD J.GOULD

1.Introduction

2.k-linked graphs

3.Weak linkage

4.Digraphs

5.Modulo and parity linkage

6.Disjoint connected subgraphs

7.The disjoint paths problem

8.H-linked graphs

9.H-extendible graphs

7 Tree-width and graph minors&DIETER RAUTENBACH and BRUCE REED

1.Introduction

2.Subtree intersection representation

3.Tree decomposition and tree-width

4.Tree decompositions decompose

5.Excluding planar minors

6.Wagner’s conjecture

7.The dual of tree-width

8.A canonical tree decomposition

9.Wagner’s conjecture for arbitrary graphs

10.Efficient characterization of H-minor-free graphs

8 Toughness and binding numbers&IAN ANDERSON

1.Introduction

2.Toughness and connectivity

3.Toughness and cycles

4.Toughness and k-factors

5.Binding number

6.Binding number and k-factors

7.Binding numbers and cycles

8.Other measures of vulnerability

9 Graph fragmentability&KEITH EDWARDS and GRAHAM FARR

1.Introduction

2.Values and bounds for fragmentability

3.Reduction and separation

4.Bounded degree classes

5.Planarization

6.Applications

7.Monochromatic components

8.Open problems

10 The phase transition in random graphs&BELA BOLLOBAS and OLIVER RIORDAN

1.Introduction

2.The Erdos-Renyi theorem：the double jump

3.Correction：no double jump

4.The phase transition - simple results

5.Exploring components

6.The phase transition - finer results

7.The young giant

8.Final words

11 Network reliability and synthesis&F.T.BOESCH，A.SATYANARAYANA and C.L.SUFFEL

1.Introduction

2.Domination in digraphs

3.Coherent systems and domination in graphs

4.Computational complexity of reliability

5.Synthesis of reliable networks

6.Other measures of vulnerability

12 Connectivity algorithms&ABDOL-HOSSEIN ESFAHANIAN

1.Introduction

2.Computing the edge-connectivity

3.Computing the arc-connectivity

4.Computing the vertex-connectivity

5.Concluding remarks

13 Using graphs to find the best block designs&R.A.BAILEY and PETER J.CAMERON

1.What makes a block design good？

2.Graphs from block designs

3.Statistical issues

4.Highly patterned block designs

5.D-optimality

6.A-optimality

7.E-optimality

8.Some history

9.Block size 2

10.Low average replication

11.Further reading

Notes on contributors

Index