5
$\begingroup$

In this question, the word graph means simple graph with finitely many vertices. We let $\subseteq$ denote the subgraph relation.

A characterization of complete graphs $K_n$ gives them as "$n$-universal" graphs that contain all graphs $G$ with at most $n$ vertices as subgraphs:

  1. For any graph $G$ with at most $n$ vertices, we have $G \subseteq K_n$, and
  2. given any graph $H$ that contains all graphs $G$ with $|V(G)| \leq n$ as subgraphs, we have $K_n \subseteq H$.

Question 1. (the probably-easy question) Are there planar graphs $U_n$ that are "$n$-universal" in the sense that

  1. For any planar graph $G$ with at most $n$ vertices, we have $G \subseteq U_n$, and
  2. given any planar graph $H$ that contains all planar graphs $G$ with $|V(G)| \leq n$ as subgraphs, we have $U_n \subseteq H$?

Obviously, there is a $4$-universal planar graph. I suspect the answer is negative for $n > 5$. If so, is there a quick proof?

Question 2. (the soft question) Are there any important results about sequences $n\in\mathbb{N} \mapsto S_n$ of planar graphs such that $S_n$ contains all at-most-$n$-vertex planar graphs as subgraphs? Most importantly:

  • Known exact or asymptotic bounds on the minimum vertex number of $S_n$ as a function of $n$? Such exact bounds are known for trees. [1]
  • Constructions of graphs achieving said bounds.

[1] F. R. K. Chung, R. L. Graham and D. Coppersmith: On trees which contain all small trees. The Theory and Applications of Graphs (ed. G. Chartrand) John Wiley and Sons, 1981, 265–272.

$\endgroup$
2
  • 2
    $\begingroup$ For $n=5$, $K_5 - e$ is $5$-universal. $\endgroup$ May 9, 2021 at 15:03
  • $\begingroup$ Thanks @MishaLavrov! I suspected so, but wasn't sure (which is why I hedged by writing $n > 5$). $\endgroup$
    – Z. A. K.
    May 9, 2021 at 15:12

1 Answer 1

4
$\begingroup$

Just to answer the easy question:

For $n=5$, $K_5 - e$ is $5$-universal. Any $5$-vertex planar graph can be triangulated, extending it to a $5$-vertex planar graph with $9$ edges, which can only be $K_5 - e$. And since $K_5-e$ has $5$ vertices itself, every graph which contains all $5$-vertex planar graphs contains $K_5-e$.

For $n>5$, there are multiple possible $n$-vertex triangulations. For example, for $n=6$, there's these two graphs (#226 and #748 in the House of Graphs):

enter image description here enter image description here

They're not drawn planarly, but this is not hard to fix.

Anyway, one planar graph that contains all the $n$-vertex planar graphs is the disjoint union of all $n$-vertex triangulations, and it is minimal: no proper subgraph of this disjoint union contains all $n$-vertex planar graphs. So if any graph will have the $n$-universal property, it's this one.

However, instead of taking the disjoint union, we can take a "wedge sum": pick a vertex $v$ in every $n$-vertex triangulation, and take a union which is disjoint except that all the $v$'s are the same. This is another planar graph that contains all $n$-vertex planar graphs, but it doesn't contain the disjoint union above.

So the disjoint union doesn't have the $n$-universal property; therefore, for $n>5$, no graph does.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .