I am interested in the general form of the Kirchoff Matrix Tree Theorem for weighted graphs, and in particular what interesting weightings one can choose.
Let $G = (V,E, \omega)$ be a weighted graph where $\omega: E \rightarrow K$, for a given field $K$; I assume that the graph is without loops.
For any spanning tree $T \subseteq G$ the weight of the tree is given to be,
$$m(T) = \prod_{e \in T}\omega(e)$$
and the tree polynomial (or statistical sum) of the graph is given to be the sum over all spanning trees in G,
$$P(G) = \sum_{T \subseteq G}m(T)$$
The combinatorial laplacian of the graph G is given by $L_G$, where:
$$L_G = \begin{pmatrix} \sum_{k = 1}^n\omega(e_{1k}) & -\omega(e_{12}) & \cdots & -\omega(e_{1n}) \\\ -\omega(e_{12}) & \sum_{k = 1}^n\omega(e_{2k}) & \cdots & -\omega(e_{2n})\\\
\vdots & \vdots & \ddots & \vdots \\\
-\omega(e_{1n}) & -\omega(e_{2n}) & \cdots & \sum_{k = 1}^n\omega(e_{nk}) \end{pmatrix} $$
where $e_{ik}$ is the edge between vertices $i$ and $k$, if no edge exists then the entry is 0 (this is the same as considering the complete graph on n vertices with an extended weighting function that gives weight 0 to any edge not in G). The matrix tree theorem then says that the tree polynomial is equal to the absolute value of any cofactor of the matrix. That is,
$$P(G) = \det(L_G(s|t))$$
where $A(s|t)$ denotes the matrix obtained by deleting row $s$ and column $t$ from a matrix $A$.
By choosing different weightings one would expect to find interesting properties of a graph G. Two simple applications are to give the weighting of all 1's. Then the theorem allows us to count the number of spanning trees with ease (this yields the standard statement of the Matrix Tree Theorem for graphs). Alternatively, by giving every edge a distinct formal symbol as its label then by computing the relevant determinant, the sum obtained can be read as a list of all the spanning trees.
My question is whether there are other interesting weightings that can be used to derive other interesting properties of graphs, or for applied problems.
Best Answer
A very interesting weighting is obtained by just working with directed multigraphs (dimgraphs). 7 or 8 years ago, I applied the matrix-tree theorem applied to dimgraphs in conjunction with the BEST theorem to provide a structure theory for the equilibrium thermodynamics of hybridization for oligomeric (short) DNA strands.
Briefly, the SantaLucia model of DNA hybridization takes a finite word $w$ on four letters (A, C, G, T) and associates to it various thermodynamical characteristics (e.g., free energy $\Delta G$ of hybridization) based on the sequence. Assuming the words are cyclic (which is not fair, but also not a very bad approximation practically), one has $\Delta G (w) = \sum_k \Delta G (w_kw_{k+1})$ where the index $k$ is cyclic and the 16 parameters $\Delta G(AA), \dots, \Delta G(TT)$ are given.
Assuming for convenience that the $\Delta G(\cdot,\cdot)$ are independent over $\mathbb{Q}$, it is not hard to see that $\Delta G$ projects from the space of all words of length $N$ to the space of dimgraphs on 4 vertices (again, A, C, G, T) with $N$ edges, where (e.g.) an edge from A to G corresponds to the subsequence AG. Using matrix-tree and BEST provides a functional expression for the number of words of length $N$ with a given number of AA's, AC's, ... and TT's, and thus for the desired $\Delta G$.
Going a step further, one can use generalized Euler-Maclaurin identities for evaluating sums of functions over lattice polytopes to characterize the space of all (cyclic) words of length $N$ with $\Delta G$ lying in a narrow range. This effectively completes the structure theory and shows how one can construct DNA sequences having desired thermodynamical and combinatorial properties. Among other things, I used this to design a protocol for (as David Harlan Wood put it) "simulating simulated annealing by annealing DNA".