Book contents
- Frontmatter
- Contents
- PREFACE
- 1 Resonance and reconstruction
- 2 Symmetry conditions in graphs
- 3 Extremal hypergraph problems
- 4 Connectivity and edge-connectivity in finite graphs
- 5 Partition theory and its applications
- 6 Strongly regular graphs
- 7 Geometries in finite projective and affine spaces
- 8 Long cycles in digraphs with constraints on the degrees
- 9 Colouring problems and matroids
- Index
4 - Connectivity and edge-connectivity in finite graphs
Published online by Cambridge University Press: 17 March 2010
- Frontmatter
- Contents
- PREFACE
- 1 Resonance and reconstruction
- 2 Symmetry conditions in graphs
- 3 Extremal hypergraph problems
- 4 Connectivity and edge-connectivity in finite graphs
- 5 Partition theory and its applications
- 6 Strongly regular graphs
- 7 Geometries in finite projective and affine spaces
- 8 Long cycles in digraphs with constraints on the degrees
- 9 Colouring problems and matroids
- Index
Summary
In the last twelve years more and more combinatorialists have taken interest in connectivity problems, and therefore some progress has been made, but there are still more unsolved problems than solved ones. We shall confine ourselves here to finite, undirected graphs and only sometimes we shall mention analogous problems for infinite graphs or for digraphs. Most of the connectivity problems for undirected graphs have a counterpart in the directed case. In general, these “directed” problems are more complicated, and so it may happen that a connectivity problem is completely solved for undirected graphs whereas the corresponding problem for digraphs has not even been attacked. (But there are some connectivity problems for digraphs which have no analogue for undirected graphs, as for instance the question answered in [22], Also the intermediate result of Nash-Williams [54] (cf. also [45]) should be mentioned.) If not otherwise stated, all graphs are supposed to be undirected and finite without multiple edges or loops.
The article is divided into four parts. In part I we determine the maximum number of openly disjoint or edge-disjoint paths joining vertices of a given set. In part II we try to construct all n-connected (n-edge-connected) graphs and collect some properties of n-connected graphs. In part III we look for some special configurations (circuits through given vertices or edges, subdivisions of complete graphs) in n connected graphs and in part IV we ask for the maximum number of edges a graph with m vertices may have without containing such configurations as vertices x ≠ y joined by n openly disjoint (or edge-disjoint) paths or an n-connected (or n-edge-connected) subgraph.
- Type
- Chapter
- Information
- Surveys in Combinatorics , pp. 66 - 95Publisher: Cambridge University PressPrint publication year: 1979
- 28
- Cited by