Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs
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_ | 1866909622785277952 |
|---|---|
| author | Botler, F. Couto, Y. S. Fernandes, C. G. de Figueiredo, E. F. Gómez, R. Santos, V. F. dos Sato, C. M. |
| author_facet | Botler, F. Couto, Y. S. Fernandes, C. G. de Figueiredo, E. F. Gómez, R. Santos, V. F. dos Sato, C. M. |
| contents | Chernyshev, Rauch, and Rautenbach proved that every connected graph on $n$ vertices with less than $\frac{11}{5}n-\frac{18}{5}$ edges has a vertex cut that induces a forest, and conjectured that the same remains true if the graph has less than $3n-6$ edges. We improve their result by proving that every connected graph on $n$ vertices with less than $\frac{9}{4}n$ edges has a vertex cut that induces a forest. We also study weaker versions of the problem that might lead to an improvement on the bound obtained. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_17885 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs Botler, F. Couto, Y. S. Fernandes, C. G. de Figueiredo, E. F. Gómez, R. Santos, V. F. dos Sato, C. M. Combinatorics Discrete Mathematics Chernyshev, Rauch, and Rautenbach proved that every connected graph on $n$ vertices with less than $\frac{11}{5}n-\frac{18}{5}$ edges has a vertex cut that induces a forest, and conjectured that the same remains true if the graph has less than $3n-6$ edges. We improve their result by proving that every connected graph on $n$ vertices with less than $\frac{9}{4}n$ edges has a vertex cut that induces a forest. We also study weaker versions of the problem that might lead to an improvement on the bound obtained. |
| title | Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2411.17885 |