On existence of noncritical vertices in digraphs
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 107-116
Voir la notice du chapitre de livre
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.
@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/}
}
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/
[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