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

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

2011-01-06

arxiv.org/abs/1101.1291v2

Discrete Applied Mathematics, 159(8):872-875, 2011

Computer Science

Discrete Mathematics

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

Scientific paper

10.1016/j.dam.2011.01.006

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.

Affiliated with

Also associated with

No associations

Rating

Bounding the Feedback Vertex Number of Digraphs in Terms of Vertex Degrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounding the Feedback Vertex Number of Digraphs in Terms of Vertex Degrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounding the Feedback Vertex Number of Digraphs in Terms of Vertex Degrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-482774