Subgraph-universal planar graphs for trees
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_ | 1866916379940093952 |
|---|---|
| author | Bergold, Helena Iršič, Vesna Lauff, Robert Orthaber, Joachim Scheucher, Manfred Wesolek, Alexandra |
| author_facet | Bergold, Helena Iršič, Vesna Lauff, Robert Orthaber, Joachim Scheucher, Manfred Wesolek, Alexandra |
| contents | We show that there exists an outerplanar graph on $O(n^{c})$ vertices for $c = \log_2(3+\sqrt{10}) \approx 2.623$ that contains every tree on $n$ vertices as a subgraph. This extends a result of Chung and Graham from 1983 who showed that there exist (non-planar) $n$-vertex graphs with $O(n \log n)$ edges that contain all trees on $n$ vertices as subgraphs and a result from Gol'dberg and Livshits from 1968 who showed that there exists a universal tree for $n$-vertex trees on $n^{O(\log(n))}$ vertices.
Furthermore, we determine the number of vertices needed in the worst case for a planar graph to contain three given trees as subgraph to be on the order of $\frac{3}{2}n$, even if the three trees are caterpillars. This answers a question recently posed by Alecu et al. in 2024.
Lastly, we investigate (outer)planar graphs containing all (outer)planar graphs as subgraph, determining exponential lower bounds in both cases. We also construct a planar graph on $n^{O(\log(n))}$ vertices containing all $n$-vertex outerplanar graphs as subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01678 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Subgraph-universal planar graphs for trees Bergold, Helena Iršič, Vesna Lauff, Robert Orthaber, Joachim Scheucher, Manfred Wesolek, Alexandra Combinatorics 05C05, 05C10, 05C78 We show that there exists an outerplanar graph on $O(n^{c})$ vertices for $c = \log_2(3+\sqrt{10}) \approx 2.623$ that contains every tree on $n$ vertices as a subgraph. This extends a result of Chung and Graham from 1983 who showed that there exist (non-planar) $n$-vertex graphs with $O(n \log n)$ edges that contain all trees on $n$ vertices as subgraphs and a result from Gol'dberg and Livshits from 1968 who showed that there exists a universal tree for $n$-vertex trees on $n^{O(\log(n))}$ vertices. Furthermore, we determine the number of vertices needed in the worst case for a planar graph to contain three given trees as subgraph to be on the order of $\frac{3}{2}n$, even if the three trees are caterpillars. This answers a question recently posed by Alecu et al. in 2024. Lastly, we investigate (outer)planar graphs containing all (outer)planar graphs as subgraph, determining exponential lower bounds in both cases. We also construct a planar graph on $n^{O(\log(n))}$ vertices containing all $n$-vertex outerplanar graphs as subgraphs. |
| title | Subgraph-universal planar graphs for trees |
| topic | Combinatorics 05C05, 05C10, 05C78 |
| url | https://arxiv.org/abs/2409.01678 |