Upper Bounds on the Minimum Size of Feedback Arc Set of Directed Multigraphs With Bounded Degree
Abstract
ABSTRACT An oriented multigraph is a directed multigraph without directed 2‐cycles. Let denote the minimum size of a feedback arc set in an oriented multigraph . In several papers, upper bounds for were obtained for oriented multigraphs with maximum degree upper‐bounded by a constant. Hanauer conjectured that for every oriented multigraph with vertices and maximum degree at most 5. We prove a strengthening of the conjecture: holds for every oriented multigraph with arcs and maximum degree at most 5. This bound is tight and improves a bound of Berger and Shor. It would be interesting to determine such that for every oriented multigraph with vertices and maximum degree at most 5 such that the bound is tight. We show that .
Fields of Study & Subjects
graph theory and CDMA systems
Limits and Structures in Graph Theory
Graph theory and applications
Publication details
- Journal / source
- Journal of Graph Theory
- Volume
- 112
- Issue
- 4
- Pages
- 421–432
- Publication date
- 8 April 2026
- Language
- EN