f_G (graph)

Let $G$ be a simple graph and $G^{+}$ be the cone over it. We define

f_{G} = \sum_{T spanning tree of G^{+}} x^{\deg_{T} (0) - 1}

Properties

$f_{G} (0) = n \cdot # spanning trees of G$
- Setting $x = 0$ kills all the trees where $\deg_{T} (0) > 1$ . We note that $\deg_{T} (0) = 1$ is exactly when $0$ is a leaf of the tree, and so we can remove it and this corresponds to a spanning tree. Note also that there are $n$ edges for which the spanning tree could connect to 0, which is why we obtain $n$ copies.
reciprocity formula for f_G: $f_{\bar{G}} (x) = (- 1)^{n - 1} f_{G} (- x - n)$ where $n$ is the number of vertices of $G$
f_G of disjoint union: $f_{G ⊔ H} = x f_{G} (x) f_{H} (x)$

Say the graph is the box on 4 vertices, and
20260413_130823.jpg|200
So,

f_{G} (x) = x^{3} + 4 \cdot 2 x^{2} + 20 x + 4 \cdot 4

Let us compute this function for the complete graph on $n$ vertices:

\begin{aligned} f_{\cdot} (x) & = 1 \\ f_{\underset{n}{\underset{⏟}{\dots}}} (x) & = x^{n - 1} \\ f_{K_{n}} (x) & = (- 1)^{n - 1} (- x - n)^{n - 1} = (x + n)^{n - 1} \end{aligned}

Furthermore, for the complete bipartite graph between $n$ and $m$ vertices $K_{m, n}$ , we note that it is equal to $\overset{―}{K_{n} ⊔ K_{m}}$ , so

\begin{aligned} f_{\overset{―}{K_{n} ⊔ K_{m}}} (x) & = (- 1)^{n + m - 1} (- x - n - m) (- x - n)^{n - 1} (- x - m)^{m - 1} \\ = (x + m + n) (x + n)^{m - 1} (x + m)^{n - 1} \end{aligned}