On existence of noncritical vertices in digraphs

G. V. Nenashev

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 107-116

Résumé

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.