Sufficient average degree conditions for the existence of large highly connected subgraphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915611963031552 |
|---|---|
| author | Krone, Maximilian |
| author_facet | Krone, Maximilian |
| contents | Mader proved that every sufficiently large graph with average degree at least $(2+\sqrt{2})k$ has a $(k+1)$-connected subgraph. He also conjectured that an average degree of at least $3k$ is sufficient. The best known sufficient factor was improved by multiple authors but never reached $3$. In the present paper, it is further improved to $3.109$. In addition, the obtained $(k+1)$-connected subgraph is constrained to have more than $1.2k$ vertices. Moreover, similar conditions on the average degree are proven to be sufficient for the existence of even greater $(k+1)$-connected subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08256 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sufficient average degree conditions for the existence of large highly connected subgraphs Krone, Maximilian Combinatorics 05C40, 05C35 Mader proved that every sufficiently large graph with average degree at least $(2+\sqrt{2})k$ has a $(k+1)$-connected subgraph. He also conjectured that an average degree of at least $3k$ is sufficient. The best known sufficient factor was improved by multiple authors but never reached $3$. In the present paper, it is further improved to $3.109$. In addition, the obtained $(k+1)$-connected subgraph is constrained to have more than $1.2k$ vertices. Moreover, similar conditions on the average degree are proven to be sufficient for the existence of even greater $(k+1)$-connected subgraphs. |
| title | Sufficient average degree conditions for the existence of large highly connected subgraphs |
| topic | Combinatorics 05C40, 05C35 |
| url | https://arxiv.org/abs/2511.08256 |