On the existence of noncritical vertices in digraphs

DOI10.1007/S10958-014-1694-5zbMATH Open1298.05148arXiv1302.2479OpenAlexW3100607261MaRDI QIDQ744557FDOQ744557

Authors: Gleb V. Nenashev 

Publication date: 25 September 2014

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

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.

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

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

zbMATH Keywords

strongly connected digraph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the number of noncritical vertices in strongly connected digraphs
• Title not available (Why is that?)
• On the number of non-critical vertices in strong tournaments of order \(N\) with minimum out-degree \(\delta ^{+}\) and in-degree \(\delta ^{ - }\)

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)