Is this graph polynomial known? Can it be efficiently computed?

Question

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research on a class of quantum spin models with ${\rm SU}(N)$ symmetry. It seems likely to me this polynomial is known, perhaps including results useful for my purposes, but I haven't been able to find any pertinent information.

Consider a connected simple graph $G$ with $n$ vertices and $m$ edges. View each edge $\ell$ as a transposition $t_{\ell}$ acting on the set of vertices. Let ${\cal L}$ be the set of ordered $m$-tuples of the edges, so that elements of ${\cal L}$ are of the form $L = (\ell_1, \dots, \ell_m)$, with each edge appearing exactly once.

To each $L \in {\cal L}$ we can associate a permutation $\pi(L) \in S_n$ by taking the product of transpositions,

$$\begin{equation} \pi[(\ell_1, \dots, \ell_m)] = t_{\ell_1} t_{\ell_2} \cdots t_{\ell_m}. \end{equation}$$

For $\pi \in S_n$, let $c(\pi)$ be the number of cycles in the the cycle decomposition, counting 1-cycles. So for example $c(1) = n$, and $c(\pi) = 1$ for $\pi$ an $n$-cycle. Then I can define the polynomial of interest:

$$\begin{equation} X(N) = \sum_{L \in {\cal L}} N^{c[\pi(L)]} \text{.} \end{equation}$$

My primary question is whether an efficient (in practical terms) procedure is known to compute $X(N)$, either for arbitrary graphs, or for certain families of graphs. In my application, I need to compute $X(N)$ for all graphs that are subgraphs of a given regular lattice, up to some maximum number of edges (which I would like to make as large as possible). In particular, I am focused on the square lattice (for now), which restricts to bipartite planar graphs. Perhaps also relevant, in my application parallel edges are allowed, but I focused on simple graphs here for simplicity.

I already know $X(N) = m! N$ if $G$ is a tree, and $X(N) = m! N^2$ if $G$ is a cycle. In addition, removing all bridges from $G$, there is a simple formula giving $X(N)$ as a product of the $X(N)$'s of the resulting components, multiplied by an overall factor. Beyond this, so far the best I can do is to take a brute force approach.

Beyond my primary question, I am also more generally interested to learn what, if anything, is known about this polynomial. For instance, are there references where $X(N)$ is studied, is $X(N)$ related to other (perhaps better-known) graph polynomials, etc.?

This post imported from StackExchange MathOverflow at 2014-10-02 10:42 (UTC), posted by SE-user Mike Hermele