On universal graphs for trees and treewidth $k$ graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911093139439616 |
|---|---|
| author | Kaul, Neel Wood, David R. |
| author_facet | Kaul, Neel Wood, David R. |
| contents | Let $s(n)$ be the minimum number of edges in a graph that contains every $n$-vertex tree as a subgraph. Chung and Graham [J. London Math. Soc. 1983] claim to prove that $s(n)\leqslant O(n\log n)$. We point out a mistake in their proof. The previously best known upper bound is $s(n)\leqslant O(n(\log n)(\log\log n)^{2})$ by Chung, Graham and Pippenger [Proc. Hungarian Coll. on Combinatorics 1976], the proof of which is missing many crucial details. We give a fully self-contained proof of the new and improved upper bound $s(n)\leqslant O(n(\log n)(\log\log n))$. The best known lower bound is $s(n)\geqslant Ω(n\log n)$.
We generalise these results for graphs of treewidth $k$. For an integer $k\geqslant 1$, let $s_k(n)$ be the minimum number of edges in a graph that contains every $n$-vertex graph with treewidth $k$ as a subgraph. So $s(n)=s_1(n)$. We show that $Ω(k n\log n) \leqslant s_k(n) \leqslant O(kn(\log n)(\log\log n))$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_03335 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On universal graphs for trees and treewidth $k$ graphs Kaul, Neel Wood, David R. Combinatorics Discrete Mathematics Let $s(n)$ be the minimum number of edges in a graph that contains every $n$-vertex tree as a subgraph. Chung and Graham [J. London Math. Soc. 1983] claim to prove that $s(n)\leqslant O(n\log n)$. We point out a mistake in their proof. The previously best known upper bound is $s(n)\leqslant O(n(\log n)(\log\log n)^{2})$ by Chung, Graham and Pippenger [Proc. Hungarian Coll. on Combinatorics 1976], the proof of which is missing many crucial details. We give a fully self-contained proof of the new and improved upper bound $s(n)\leqslant O(n(\log n)(\log\log n))$. The best known lower bound is $s(n)\geqslant Ω(n\log n)$. We generalise these results for graphs of treewidth $k$. For an integer $k\geqslant 1$, let $s_k(n)$ be the minimum number of edges in a graph that contains every $n$-vertex graph with treewidth $k$ as a subgraph. So $s(n)=s_1(n)$. We show that $Ω(k n\log n) \leqslant s_k(n) \leqslant O(kn(\log n)(\log\log n))$. |
| title | On universal graphs for trees and treewidth $k$ graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2508.03335 |