Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916390613549056 |
|---|---|
| author | Gutin, Gregory Lei, Hui Yeo, Anders Zhou, Yacong |
| author_facet | Gutin, Gregory Lei, Hui Yeo, Anders Zhou, Yacong |
| contents | An oriented multigraph is a directed multigraph without directed 2-cycles. Let ${\rm fas}(D)$ denote the minimum size of a feedback arc set in an oriented multigraph $D$. The degree of a vertex is the sum of its out- and in-degrees. In several papers, upper bounds for ${\rm fas}(D)$ were obtained for oriented multigraphs $D$ with maximum degree upper-bounded by a constant. Hanauer (2017) conjectured that ${\rm fas}(D)\le 2.5n/3$ for every oriented multigraph $D$ with $n$ vertices and maximum degree at most 5. We prove a strengthening of the conjecture: ${\rm fas}(D)\le m/3$ holds for every oriented multigraph $D$ with $m$ arcs and maximum degree at most 5. This bound is tight and improves a bound of Berger and Shor (1990,1997). It would be interesting to determine $c$ such that ${\rm fas}(D)\le cn$ for every oriented multigraph $D$ with $n$ vertices and maximum degree at most 5 such that the bound is tight. We show that $\frac{5}{7}\le c \le \frac{24}{29} < \frac{2.5}{3}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_07680 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree Gutin, Gregory Lei, Hui Yeo, Anders Zhou, Yacong Combinatorics Discrete Mathematics An oriented multigraph is a directed multigraph without directed 2-cycles. Let ${\rm fas}(D)$ denote the minimum size of a feedback arc set in an oriented multigraph $D$. The degree of a vertex is the sum of its out- and in-degrees. In several papers, upper bounds for ${\rm fas}(D)$ were obtained for oriented multigraphs $D$ with maximum degree upper-bounded by a constant. Hanauer (2017) conjectured that ${\rm fas}(D)\le 2.5n/3$ for every oriented multigraph $D$ with $n$ vertices and maximum degree at most 5. We prove a strengthening of the conjecture: ${\rm fas}(D)\le m/3$ holds for every oriented multigraph $D$ with $m$ arcs and maximum degree at most 5. This bound is tight and improves a bound of Berger and Shor (1990,1997). It would be interesting to determine $c$ such that ${\rm fas}(D)\le cn$ for every oriented multigraph $D$ with $n$ vertices and maximum degree at most 5 such that the bound is tight. We show that $\frac{5}{7}\le c \le \frac{24}{29} < \frac{2.5}{3}$. |
| title | Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2409.07680 |