Feedback vertex sets of digraphs with bounded maximum degree
Discrete Mathematics · 2027-02 · 350 (2) · 115390
DOI: 10.1016/j.disc.2026.115390 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics, 2027-02. Verfasst von Jiangdong Ai und 4 weiteren Autor:innen. Die Arbeit nennt 29 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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 $\Delta$. We prove the following bounds. If $D$ is an oriented graph, then $fvs(D)\leq \frac{3n}{7}$ when $\Delta\le 4$ and $fvs(D)\leq \frac{n}{2}$ when $\Delta\le 5$. If $D$ is a connected digraph, $\Delta\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 $\Delta\le 5$ then $fvs(D)\leq \frac{2n}{3}.$ Note that all the above bounds are tight.
Zitieren
APA
Ai, J., Gutin, G., Liu, X., Yeo, A., & Zhou, Y. (2027). Feedback vertex sets of digraphs with bounded maximum degree. Discrete Mathematics, 350(2), 115390. https://doi.org/10.1016/j.disc.2026.115390
Vancouver
Ai J, Gutin G, Liu X, Yeo A, Zhou Y. Feedback vertex sets of digraphs with bounded maximum degree. Discrete Mathematics. 2027;350(2):115390. doi:10.1016/j.disc.2026.115390
BibTeX
@article{Ai2027,
author = {Ai, Jiangdong and Gutin, Gregory and Liu, Xiangzhou and Yeo, Anders and Zhou, Yacong},
title = {Feedback vertex sets of digraphs with bounded maximum degree},
journal = {Discrete Mathematics},
year = {2027},
volume = {350},
number = {2},
pages = {115390},
doi = {10.1016/j.disc.2026.115390}
}
EUVIMED