Bounding the Feedback Vertex Number of Digraphs in Terms of Vertex Degrees
| Autor: | Gruber, Hermann |
|---|---|
| Rok vydání: | 2011 |
| Předmět: | |
| Zdroj: | Discrete Applied Mathematics, 159(8):872-875, 2011 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.dam.2011.01.006 |
| Popis: | 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. Comment: preprint submitted to Discrete Applied Mathematics; minor corrections, added doi (v2) |
| Databáze: | arXiv |
| Externí odkaz: |
|