Operations Research Transactions ›› 2011, Vol. 15 ›› Issue (3): 57-61.

• Original Articles • Previous Articles     Next Articles

The Number of Arcs of Strongly Connected Oriented Graphs with Two Noncritical Vertices

 LIN  Shang-Wei, LI  Chun-Fang, WANG  Shi-Ying   

  • Online:2011-09-20 Published:2011-09-20

Abstract: It is proved that a strongly
 connected oriented graph $D$ with $n\geq 4$ vertices and  at least ${n-1 \choose 2}+3$
 arcs has two distinct vertices $u^*, v^*$ such that both $D-u^*$ and $D-v^*$ are strongly connected. The examples
show that the above lower bound on the number of arcs is sharp.

Key words:  digraph,  , strongly connected subdigraph, critical vertex