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 the line of research 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. Our result also stands in contrast to 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, and it was later shown that there is no polynomially sized universal tree. Furthermore, we investigate (outer)planar graphs containing all n-vertex (outer)planar graphs as subgraphs, determining exponential lower bounds in both cases. We can however construct a planar graph on \(n^{O(\log (n))}\) vertices containing all n-vertex outerplanar graphs as subgraphs. Lastly, we determine the number of vertices needed in the worst case for a planar graph to contain three given trees as subgraphs 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Subgraph-Universal Planar Graphs for Trees

  • Helena Bergold,
  • Vesna Iršič Chenoweth,
  • Robert Lauff,
  • Joachim Orthaber,
  • Manfred Scheucher,
  • Alexandra Wesolek

摘要

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 the line of research 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. Our result also stands in contrast to 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, and it was later shown that there is no polynomially sized universal tree. Furthermore, we investigate (outer)planar graphs containing all n-vertex (outer)planar graphs as subgraphs, determining exponential lower bounds in both cases. We can however construct a planar graph on \(n^{O(\log (n))}\) vertices containing all n-vertex outerplanar graphs as subgraphs. Lastly, we determine the number of vertices needed in the worst case for a planar graph to contain three given trees as subgraphs 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.