# 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)

##### MSC:
 05C40 Connectivity 05C35 Extremal problems in graph theory 05C20 Directed graphs (digraphs), tournaments
##### Keywords:
$$n$$-connected graphs; $$n$$-connectivity