Sufficient Conditions for Maximally Edge-Connected and Super-Edge-Connected Oriented Graphs Depending on the Clique Number

Abstract

An orientation of a simple graph $G$ is called an oriented graph. If $D$ is an oriented graph, $\delta (D)$ its minimum degree and $\lambda (D)$ its edge-connectivity, then $\lambda (D)\le \delta (D)$. The oriented graph is called maximally edge-connected if $\lambda (D)=\delta (D)$ and super-edge-connected, if every minimum edge-cut is trivial. In this paper, we show that an oriented graph $D$ of order $n$ without any clique of order $p+1$ in its underlying graph is maximally edge-connected when

$$n\le 4\lfloor \frac{p\delta (D)}{p–1}\rfloor -1.$$

Some related conditions for oriented graphs to be super-edge-connected are also presented.