Feedback vertex sets of digraphs with bounded maximum degree
A digraph $D$ is an oriented graph if $D$ does not have a pair of opposite arcs. The degree of a vertex $v$ of $D$ is the sum of the in-degree and out-degree of $v.$ Let $fvs(D)$ be the minimum number of vertices whose deletion from $D$ makes it acyclic. Let $D$ be a digraph with $n$ vertices and maximum degree $Δ$. We prove the following bounds. If $D$ is an oriented graph, then $fvs(D)\leq \frac{3n}{7}$ when $Δ\le 4$ and $fvs(D)\leq \frac{n}{2}$ when $Δ\le 5$. If $D$ is a connected digraph, $Δ\le 4$ and $D$ is not obtained from an odd undirected cycle by replacing every edge with the pair of opposite arcs with the same endvertices, then $fvs(D)\leq \frac{n}{2}$. If $D$ is an arbitrary digraph with $Δ\le 5$ then $fvs(D)\leq \frac{2n}{3}.$ Note that all the above bounds are tight.
Authors
- Anders Yeo (ORCID: https://orcid.org/0000-0003-0293-8708)
- Gregory Gutin (ORCID: https://orcid.org/0000-0002-2377-0417)
- Yacong Zhou (ORCID: https://orcid.org/0000-0002-6988-6968)
- Jiangdong Ai (ORCID: https://orcid.org/0000-0002-5691-3365)
- Xiangzhou Liu
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2026-08-27
- DOI
- https://doi.org/10.1016/j.disc.2026.115390
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00