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. [To be more explicit, given an edge $\ell$ joining vertices $v_1$ and $v_2$, $t_{\ell}$ is a permutation exchanging $v_1$ and $v_2$, leaving all other vertices fixed.] 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.?
Best Answer
I can't imagine there is an extremely efficient way of computing this, however I don't have any proof of this fact.
In general when someone asks about a graph polynomial my instinct is to think about the tutte polynomial (http://en.wikipedia.org/wiki/Tutte_polynomial). 'Most' polynomials associated to graphs are evaluations of the tutte polynomial. The best way to test whether your X is associated to the tutte poly in this way is to check the deletion-contraction recurrence.
I was seeking an small counterexample to the condition that, if G is disconnected (I know that you required that G be connected, but I can't see why that's required in general: nothing will change), we have that the polynomial of the graph is the product of the polynomials of the components.
I used G:=(the union of a 3-cycle and a 4-cycle) and found such a counterexample. We have $$ X(G) = 5040N^4, X(C3) = 6N^2, X(C4) = 24N^2. $$
Thus, this polynomial is not 'nice' in this way. The good news is that computing the Tutte polynomial is exponential, so yours may even be nicer! I think the best strategy would be to explore what happens to the polynomial when you perform surgery on the graph (deleting edges, etc.). However the definition itself is slightly wild, and as it's divorced from Automorphisms and should be badly-behaved when dealing with edge-deletion or other operations, I expect you're out of luck. =(
EDIT: I missed a much simpler counterexample to the deletion-contraction recurrence using only connected graphs. Let $C_n$ be an $n$-cycle: then for any edge $e$, the edge-contraction is an $n-1$-cycle, and the edge-deletion is a path with $n-1$ edges. Thus we ought to have $$ n! N^2 = (n-1)! N + (n-1)! N^2, $$ which is not true.