zbMATH — the first resource for mathematics

On vertices of degree \(n\) in minimally \(n\)-connected graphs and digraphs. (English) Zbl 0849.05048
Miklós, D. (ed.) et al., Combinatorics, Paul Erdős is eighty. Vol. 2. Budapest: János Bolyai Mathematical Society. Bolyai Soc. Math. Stud. 2, 423-449 (1996).
A directed or undirected graph \(G\) is called minimally \(n\)-(edge-)connected if \(G\) is \(n\)-(edge-) connected but no graph that arises from \(G\) by deleting some edge has this property. Such graphs play an important role. For instance, to prove a statement on \(n\)-connected graphs, we can often restrict ourselves to minimally \(n\)-connected graphs. The starting-point of the present paper is an odd result of R. Halin stating that each minimally \(n\)-connected undirected finite graph has a vertex of degree \(n\). W. Mader surveys the results on vertices of degree \(n\) in minimally \(n\)-connected graphs and minimally \(n\)-edge-connected graphs (in the directed case, vertices of indegree \(n\) and vertices of outdegree \(n\) are considered) and discusses related questions. Moreover, he proves some new results and gives a lot of conjectures. Main topics of the paper are the number of vertices of degree \(n\) in minimally \(n\)-(edge-)connected graphs and fundamental extensions of R. Halin’s result due to the author. He proves that each circuit in an \(n\)-connected undirected (not necessarily finite) graph contains a vertex of degree \(n\) or an edge whose deletion does not destroy the \(n\)-connectivity. Moreover, he verifies a similar statement for directed graphs. The author also gives some variations of these results for small integers \(n\). Finally, he considers some generalizations of \(n\)-(edge-)connectivity such as \(n\)-(edge-)connected subsets \(A\subseteq V(G)\) in a graph \(G\) (i.e. \(|A|\geq 2\) and any two vertices of \(A\) are connected by \(n\) openly disjoint (edge-disjoint) paths in \(G\)) and a common generalization of \(n\)-connectivity and \(n\)-edge-connectivity. Again, he surveys results on graphs \(G\) such that \(G\) satisfies such a generalized connectivity condition, but no graph with this property arises from \(G\) by deleting some edge.
For the entire collection see [Zbl 0837.00020].
Reviewer: A.Huck (Hannover)

05C40 Connectivity
05C35 Extremal problems in graph theory
05C20 Directed graphs (digraphs), tournaments