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) \leq \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 \leq 4{\lfloor\frac{p\delta(D)}{p – 1}\rfloor}-1.\]

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