Covering digraphs with small indegrees or outdegrees by directed cuts

For nonnegative integers k and l, let D(k, l) denote the set of digraphs in which every vertex has indegree at most k or outdegree at most l. In this paper, we first compare three existing upper bounds for the number of directed cuts to cover the arcs of digraphs in D(k, k) and prove that these bounds can be improved from seven to six in the case k = 5, 6. Further, we give a lower bound for the number of directed cuts to cover the digraphs in D(k, l) by constructing a digraph in this class. (C) 2013 Elsevier B.V. All rights reserved.