Geodesic
On existence of noncritical vertices in digraphs
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 107-116 
G. V. Nenashev. On existence of noncritical vertices in digraphs. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 107-116. http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a5/
@article{ZNSL_2012_406_a5,
     author = {G. V. Nenashev},
     title = {On existence of noncritical vertices in digraphs},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {107--116},
     year = {2012},
     volume = {406},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a5/}
}
TY  - JOUR
AU  - G. V. Nenashev
TI  - On existence of noncritical vertices in digraphs
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 107
EP  - 116
VL  - 406
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a5/
LA  - ru
ID  - ZNSL_2012_406_a5
ER  - 
%0 Journal Article
%A G. V. Nenashev
%T On existence of noncritical vertices in digraphs
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 107-116
%V 406
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a5/
%G ru
%F ZNSL_2012_406_a5

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

Let $D$ be a strongly connected digraph on $n\ge4$ vertices. A vertex $v$ of $D$ is noncritical, if the digraph $D-v$ is strongly connected. We prove, that if sum of the degrees of any two adjacent vertices of $D$ is at least $n+1$, then there exists a noncritical vertex in $D$, and if sum of the degrees of any two adjacent vertices of $D$ is at least $n+2$, then there exist two noncritical vertices in $D$. A series of examples confirm that these bounds are tight.

[1] W. Mader, “Critically $n$-connected digraphs”, Graph Theory, Combinatorics, and Applications, v. 2, 1991, 811–829 | MR | Zbl

[2] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, 2000 | MR

[3] S. V. Savchenko, “O chisle nekriticheskikh vershin v silno svyaznykh orgrafakh”, Mat. zametki, 79:5 (2006), 743–755 | DOI | MR | Zbl

[4] S. V. Savchenko, “On the number of non-critical vertices in strong tournaments of order $N$ with minimum out-degree $\delta^+$ and in-degree $\delta^-$”, Discrete Math., 310 (2010), 1177–1183 | DOI | MR | Zbl