Bounding the Feedback Vertex Number of Digraphs in Terms of Vertex Degrees

Abstract

The Turan bound is a famous result in graph theory, which relates the independence number of an undirected graph to its edge density. Also the Caro-Wei inequality, which gives a more refined bound in terms of the vertex degree sequence of a graph, might be regarded today as a classical result. We show how these statements can be generalized to directed graphs, thus yielding a bound on directed feedback vertex number in terms of vertex outdegrees and in terms of average outdegree, respectively.

arXiv commentpreprint submitted to Discrete Applied Mathematics; minor corrections, added doi (v2)