On the number of noncritical vertices in strongly connected digraphs

S. V. Savchenko

Matematičeskie zametki, Tome 79 (2006) no. 5, pp. 743-755

Résumé

By definition, a vertex $w$ of a strongly connected (or, simply, strong) digraph $D$ is noncritical if the subgraph $D-w$ is also strongly connected. We prove that if the minimal out (or in) degree $k$ of $D$ is at least 2, then there are at least k noncritical vertices in $D$. In contrast to the case of undirected graphs, this bound cannot be sharpened, for a given $k$, even for digraphs of large order. Moreover, we show that if the valency of any vertex of a strong digraph of order $n$ is at least $3/4n$, then it contains at least two noncritical vertices. The proof makes use of the results of the theory of maximal proper strong subgraphs established by Mader and developed by the present author. We also construct a counterpart of this theory for biconnected (undirected) graphs.