Hitting cycles through prescribed vertices or edges
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914348615598080 |
|---|---|
| author | Bowler, Nathan Ghorbani, Ebrahim Gut, Florian Jacobs, Raphael W. Reich, Florian |
| author_facet | Bowler, Nathan Ghorbani, Ebrahim Gut, Florian Jacobs, Raphael W. Reich, Florian |
| contents | We prove that for every set $S$ of vertices of a directed graph $D$, the maximum number of vertices in $S$ contained in a collection of vertex-disjoint cycles in $D$ is at least the minimum size of a set of vertices that hits all cycles containing a vertex of $S$. As a consequence, the directed tree-width of a directed graph is linearly bounded in its cycle-width, which improves the previously known quadratic upper bound.
We further show that the corresponding statement in bidirected graphs is true and that its edge-variant holds in both undirected and directed graphs, but fails in bidirected graphs. The vertex-version in undirected graphs remains an open problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_06557 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hitting cycles through prescribed vertices or edges Bowler, Nathan Ghorbani, Ebrahim Gut, Florian Jacobs, Raphael W. Reich, Florian Combinatorics 05C38 We prove that for every set $S$ of vertices of a directed graph $D$, the maximum number of vertices in $S$ contained in a collection of vertex-disjoint cycles in $D$ is at least the minimum size of a set of vertices that hits all cycles containing a vertex of $S$. As a consequence, the directed tree-width of a directed graph is linearly bounded in its cycle-width, which improves the previously known quadratic upper bound. We further show that the corresponding statement in bidirected graphs is true and that its edge-variant holds in both undirected and directed graphs, but fails in bidirected graphs. The vertex-version in undirected graphs remains an open problem. |
| title | Hitting cycles through prescribed vertices or edges |
| topic | Combinatorics 05C38 |
| url | https://arxiv.org/abs/2412.06557 |