On the number of noncritical vertices in strongly connected digraphs
Matematičeskie zametki, Tome 79 (2006) no. 5, pp. 743-755
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{MZM_2006_79_5_a10,
author = {S. V. Savchenko},
title = {On the number of noncritical vertices in strongly connected digraphs},
journal = {Matemati\v{c}eskie zametki},
pages = {743--755},
publisher = {mathdoc},
volume = {79},
number = {5},
year = {2006},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/MZM_2006_79_5_a10/}
}
S. V. Savchenko. On the number of noncritical vertices in strongly connected digraphs. Matematičeskie zametki, Tome 79 (2006) no. 5, pp. 743-755. http://geodesic.mathdoc.fr/item/MZM_2006_79_5_a10/