Degree Sequence Conditions for Super-Edge-Connected Graphs and Digraphs

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

Abstract

A graph or a digraph \(G\) 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 \(G\) is super-\(\lambda\), then \(\lambda(G) = \delta(G)\), where \(\delta(G)\) is the minimum degree and \(\lambda(G)\) is the edge-connectivity of \(G\).

In this paper, degree sequence conditions for graphs and digraphs as well as for bipartite graphs and digraphs to be super-\(\lambda\) are presented.