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

DOI10.1016/J.DAM.2011.01.006zbMATH Open1222.05030arXiv1101.1291OpenAlexW2113301124MaRDI QIDQ534359FDOQ534359

Authors: Hermann Gruber 

Publication date: 17 May 2011

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

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.

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

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

zbMATH Keywords

feedback setacyclic setCaro-Wei inequalitydirected feedback vertex numberinduced DAG

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Large induced degenerate subgraphs
• Lower bounds on the independence number in terms of the degrees
• A note on greedy algorithms for the maximum weighted independent set problem
• On cliques in graphs
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hypergraph coverings and local colorings
• Title not available (Why is that?)
• Turan's Graph Theorem
• On maximal transitive subtournaments

Cited In (4)

• Title not available (Why is that?)
• Bounds on feedback numbers of de Bruijn graphs
• On the bounds of feedback numbers of \((n,k)\)-star graphs
• Title not available (Why is that?)

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)