2
$\begingroup$

Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count $P_1P_2$ (introduce one additional vertex $v$ and join any one vertex in Graph $G_1$ to the vertex $v$ and any one vertex in Graph $G_2$ to the vertex $v$) and this contruction does not need to know $P_1$ and $P_2$.

Is there a graph construction in polynomial time to get a planar graph from $G_1$ and $G_2$ with spanning tree count $P_1+P_2$ without knowing $P_1$ or $P_2$ when $P_1+P_2>2$ holds?

Improve this question
$\endgroup$
7
  • $\begingroup$ There is no simple graph (planar or otherwise) with exactly 2 spanning trees, right? $\endgroup$
    – Sam Hopkins
    Commented Feb 12, 2022 at 23:33
  • 1
    $\begingroup$ Well, you get every number greater than 2 by considering the cycle graphs. $\endgroup$
    – Sam Hopkins
    Commented Feb 12, 2022 at 23:39
  • $\begingroup$ I think that morally answers my question. $\endgroup$
    – Turbo
    Commented Feb 12, 2022 at 23:39
  • $\begingroup$ The other "moral" problem with your question is that we can simply compute the numbers $P_1$ and $P_2$ in polynomial time. $\endgroup$
    – Sam Hopkins
    Commented Feb 12, 2022 at 23:40
  • $\begingroup$ Yeah technically speaking I want to be in Logspace but since I am talking to mathematicians I figured some amount of difficulty becomes evident with the way I am portraying (there is no known logspace or even non-deterministic logspace (both are conjectured to be same) algorithm to find $P_1$ or $P_2$). $\endgroup$
    – Turbo
    Commented Feb 12, 2022 at 23:41

0

Reset to default

You must log in to answer this question.