Degree Sequence Conditions for Super-Edge-Connected Oriented Graphs

Lutz Volkmann1
1Lehrstuhl II fiir Mathematik, RWTH Aachen University, 52056 Aachen, Germany

Abstract

If \( D \) is a digraph, \( \delta \) its minimum degree, and \( \lambda \) its edge-connectivity, then \( \lambda \leq \delta \). A digraph \( D \) is called super-edge-connected or super-\( \lambda \) if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree. Clearly, if \( D \) is super-\( \lambda \), then \( \lambda = \delta \). A digraph without any directed cycle of length \( 2 \) is called an oriented graph. Sufficient conditions for digraphs to be super-edge-connected were given by several authors. However, closely related results for oriented graphs have received little attention until recently. In this paper, we will present some degree sequence conditions for oriented graphs as well as for oriented bipartite graphs to be super-edge-connected.

Keywords: oriented graph, edge-connectivity, super-edge-connectivity, degree sequence, oriented bipartite graph