2
$\begingroup$

Given set $\mathcal T_n=\{0,1,3,4\dots,2^n-1\}$ (note there is no $2$) what is the minimum number of vertices $m$ needed in a planar graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\mathcal G_{m}$ (set of all planar graphs on $m$ vertices) with Spanning tree count exactly $i$? Is there $m=O(poly(n))$?

Essentially I am asking whether for every $i$ in $\mathcal T_n$ we can construct a graph with spanning tree count exactly $i$ and the number of vertices is just $O(poly(n))$?

If $m=2^{O(n)}$ then regular $i$-agon suffices for $i=m$.

Improve this question
$\endgroup$
2
  • $\begingroup$ It's easy to reduce this to the case of $i$ prime, but I'm not sure how to solve that $\endgroup$ Commented Jul 10, 2024 at 4:31
  • $\begingroup$ Cf. MO question 93656 where it was conjectured (empirically) that graphs of $o(\log(n))$ vertices exist that have $n$ spanning trees. (Planarity not mentioned though. $\endgroup$ Commented Jul 10, 2024 at 17:59

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.