On the existence of noncritical vertices in digraphs

DOI10.1007/S10958-014-1694-5MaRDI QIDQ744557zbMATH OpenOpenAlexFDO

Authors Gleb V. Nenashev

Publication date 25 September 2014

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.2479

zbMATH Keywords

strongly connected digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Abstract: Let $D$ be a strongly connected digraphs on $nge4$ 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.

Recommendations

• On the number of noncritical vertices in strongly connected digraphs
• On critically connected digraphs
• Critical vertices in \(k\)-connected digraphs
• Properties of \(k\)-critically \(n\)-connected digraphs
• scientific article; zbMATH DE number 867644

Cites work

• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• scientific article; zbMATH DE number 867644 (Why is no real title available?)
• On the number of non-critical vertices in strong tournaments of order \(N\) with minimum out-degree \(\delta ^{+}\) and in-degree \(\delta ^{ - }\)
• On the number of noncritical vertices in strongly connected digraphs

Cited in

(3)

• New proofs of the uniqueness of extremal noneven digraphs
• On the number of noncritical vertices in strongly connected digraphs
• On the non-existence of families of \((d,k, \delta)\)-digraphs containing only selfrepeat vertices

This page was built for publication: On the existence of noncritical vertices in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744557)