Bounding the feedback vertex number of digraphs in terms of vertex degrees

DOI10.1016/J.DAM.2011.01.006MaRDI QIDQ534359zbMATH OpenOpenAlexFDO

Authors Hermann Gruber

Publication date 17 May 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.1291

zbMATH Keywords

feedback setacyclic setCaro-Wei inequalitydirected feedback vertex numberinduced DAG

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07)

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.

Recommendations

• The size of graphs with given feedback vertex number
• Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
• Feedback vertex number of Sierpiński-type graphs
• scientific article; zbMATH DE number 3972888
• Bounds on feedback numbers of de Bruijn graphs
• On the bounds of feedback numbers of \((n,k)\)-star graphs
• Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
• Feedback vertex sets on restricted bipartite graphs
• Independent feedback vertex sets for graphs of bounded diameter
• A new bound on the feedback vertex sets in cubic graphs

Cites work

• scientific article; zbMATH DE number 5939736 (Why is no real title available?)
• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1542661 (Why is no real title available?)
• scientific article; zbMATH DE number 5032352 (Why is no real title available?)
• A note on greedy algorithms for the maximum weighted independent set problem
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Hypergraph coverings and local colorings
• Large induced degenerate subgraphs
• Lower bounds on the independence number in terms of the degrees
• On cliques in graphs
• On maximal transitive subtournaments
• Turan's Graph Theorem

Cited in

(4)

• scientific article; zbMATH DE number 6403923 (Why is no real title available?)
• Bounds on feedback numbers of de Bruijn graphs
• scientific article; zbMATH DE number 5711445 (Why is no real title available?)
• On the bounds of feedback numbers of \((n,k)\)-star graphs

This page was built for publication: Bounding the feedback vertex number of digraphs in terms of vertex degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534359)