Degree Sequence Conditions For Maximally Edge-Connected And Super-Edge-Connected Oriented Graphs Depending On The Clique Number

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

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. If \(D\) is an oriented graph with the property that the underlying graph \(G(D)\) contains no complete subgraph of order \(p+1\), then we say that the clique number \(\omega(D)\) of \(D\) is less or equal \(p\).

In this paper, we present degree sequence conditions for maximally edge-connected and super-edge-connected oriented graphs \(D\) with clique number \(\omega(D) \leq p\) for an integer \(p \geq 2\).