RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2012 Volume 406, Pages 107–116 (Mi znsl5292)

On existence of noncritical vertices in digraphs

G. V. Nenashev

Saint-Petersburg State University, Saint-Petersburg, Russia

Abstract: 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.

Key words and phrases: digraph, strong connectivity, noncritical vertex.

UDC: 519.172.3

Received: 21.06.2012


 English version:
Journal of Mathematical Sciences (New York), 2014, 196:6, 791–796

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025