Number of Edges in 3-Connected Graphs with Cyclic Neighborhoods
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914157732823040 |
|---|---|
| author | Schneider, Samuel Ueckerdt, Torsten |
| author_facet | Schneider, Samuel Ueckerdt, Torsten |
| contents | Chernyshev, Rauch and Rautenbach [Discrete Math., 2025] introduce forest cuts, i.e., vertex separators that induce a forest. They conjecture that, similar to a result by Chen and Yu [Discrete Math., 2002], every $n$-vertex graph with less than $3n-6$ edges has a forest cut. As an intermediate goal they ask how many edges an $n$-vertex $3$-connected graph must have such that the neighborhood of every vertex contains a cycle. Li, Tang and Zhan [arXiv, 2024] resolve this problem by showing that every such graph has at least $15n/8$ edges, while there are examples of such graphs with exactly $15n/8$ edges. We give a much shorter proof for this. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_10717 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Number of Edges in 3-Connected Graphs with Cyclic Neighborhoods Schneider, Samuel Ueckerdt, Torsten Combinatorics Discrete Mathematics Chernyshev, Rauch and Rautenbach [Discrete Math., 2025] introduce forest cuts, i.e., vertex separators that induce a forest. They conjecture that, similar to a result by Chen and Yu [Discrete Math., 2002], every $n$-vertex graph with less than $3n-6$ edges has a forest cut. As an intermediate goal they ask how many edges an $n$-vertex $3$-connected graph must have such that the neighborhood of every vertex contains a cycle. Li, Tang and Zhan [arXiv, 2024] resolve this problem by showing that every such graph has at least $15n/8$ edges, while there are examples of such graphs with exactly $15n/8$ edges. We give a much shorter proof for this. |
| title | Number of Edges in 3-Connected Graphs with Cyclic Neighborhoods |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2511.10717 |