Drunken X-mas polynomials for graphs

Question

Given a finite connected graph $\Gamma$ with vertices $\lbrace 1,\ldots,N\rbrace$, we can consider the polynomial $$\sum_{\pi\in\mathcal S_N}x^{\sum_{j=1}^Nd_\Gamma(j,\pi(j))}$$ where $\mathcal S_N$ is the group of all $N!$ permutations of $\lbrace 1,\ldots,N\rbrace$ and where $d_\Gamma(x,y)$ is the distance between two vertices $x$ and $y$ (minimal number of edges needed in a path from $x$ to $y$) in $\Gamma$.

(Explanation for the name: (Sum over) costs for repairing all possible errors of a drunken Santa Claus during the delivery of X-mas presents along $\Gamma$.)

These polynomials seem to have interesting properties:

For $\Gamma$ the complete graph, we get essentially the fix-point statistics of permutations.

For $\Gamma$ the line-graph ($A_N$ Dynkin graph) we get an even polynomial with evaluations $$1,0,2,0,16,0,272,0,7936,0,353792,\ldots$$ at $i$ defining seemingly (up to powers of $2$, and interspersed zeros) sequence A2105 of the OEIS involving Bernoulli numbers.

Mean costs (evaluations at $x=1$ of the derived polynomial, divided by $N!$) are seemingly given by $\frac{N^2-1}{3}$.

etc.

Polynomials associated to $N$-cycles have also interesting properties.

Is there a good reference for these polynomials?

Answer 1

There is quite a bit of literature in statistical mechanics on spatially random permutations. The partition function essentially is $P_\Gamma(x)$ with $x=e^{-\alpha}$ for some temperature like parameter $\alpha\ge 0$.

See the papers by Daniel Ueltschi and collaborators, e.g.,

Gandolfo, D., Ruiz, J. & Ueltschi, D. "On a Model of Random Cycles". J Stat Phys 129, 663–676 (2007). https://doi.org/10.1007/s10955-007-9410-1

D. Ueltschi, "Universal behaviour of 3D loop soup models", https://arxiv.org/abs/1703.09503