Geodesic
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/}
}
TY  - JOUR
AU  - S. V. Savchenko
TI  - On the number of noncritical vertices in strongly connected digraphs
JO  - Matematičeskie zametki
PY  - 2006
SP  - 743
EP  - 755
VL  - 79
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2006_79_5_a10/
LA  - ru
ID  - MZM_2006_79_5_a10
ER  - 
%0 Journal Article
%A S. V. Savchenko
%T On the number of noncritical vertices in strongly connected digraphs
%J Matematičeskie zametki
%D 2006
%P 743-755
%V 79
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2006_79_5_a10/
%G ru
%F 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/

[1] Mader W., “Critically $n$-connected digraphs”, Graph Theory, Combinatorics, and Applications, V. II, eds. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, John Wiley and Sons, New York–London–Sydney–Toronto, 1991, 811–829 | MR | Zbl

[2] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka; Fizmatlit, M., 1997 | MR

[3] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, M., 1990

[4] Bang-Jensen J., Gutin G., Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London, 2000 | MR

[5] Clark L. H., Entringer R. C., “The number of cutvertices in graphs with given minimum degree”, Discrete Math., 81 (1990), 137–145 | DOI | MR | Zbl

[6] Albertson M. O., Berman D. M., “The number of cut-vertices in a graph of given minimum degree”, Discrete Math., 89 (1991), 97–100 | DOI | MR | Zbl

[7] Nebesky L., “On induced subgraphs of a block”, J. Graph Theory, 1 (1977), 69–74 | DOI | MR | Zbl

[8] Kriesell M., “Contractible subgraphs in $3$-connected graphs”, J. Combin. Theory Ser. B, 80 (2000), 32–48 | DOI | MR | Zbl

[9] Nelson D. A., “The structure of saturated critical blocks”, J. Graph Theory, 43 (2003), 223–237 | DOI | MR | Zbl

[10] Nebesky L., “A theorem on $2$-connected graphs”, $\breve{\text{C}}$asopis. $\breve{\text{p}}$est. mat., 100 (1975), 116–117 | MR | Zbl

[11] Veldman H. J., “Non-${\kappa}$-critical vertices in graphs”, Discrete Math., 44 (1983), 105–110 | DOI | MR | Zbl