Given a finite tree $T$ with $n$ vertices labelled $1,\dots,n$, we say that a permutation $\sigma$ of $1,\dots,n$ rips all edges if $\{\sigma(i),\sigma(j)\}$ is never an edge for every edge $\{i,j\}$ of $T$. It is easy to see that every tree of diameter at least $3$ has such permutations. They are not very hard to count (see A2464 of the Encyclopedia of Integer Sequences) for Dynkin diagrams of type $A$ (with edges given by $\{i,i+1\}$ for $i=1,\dots,n-1$). Can they be counted similarly in polynomial time for an arbitrary tree of diameter $\geq 3$?
More generally, can one compute efficiently the ripping polynomial $R(T)=\sum_{k=0}^{n-1}\alpha_k t^k$ which counts numbers $\alpha_k$ of permutations preserving exactly $k$ edges of $T$? This is again easy for Dynkin diagrams of type $A$ with $R(n)$ defined by \begin{eqnarray*} R(n)&=&A(n)+tB(n),\\ A(1)&=&1,\\ A(n+1)&=&(1-t)A'(n)+(n-2)A(n)+t(1-t)B'(n)+t(n-2)B(n),\\ B(1)&=&0,\\ B(n+1)&=&(1+t)B(n)+2A(n). \end{eqnarray*} The picture obtained by plotting all complex roots (for $n\sim 100$) might be slightly unsuitable for a general audience. Interestingly, we have $R'(n)=2(n-1)(n-1)!$ showing that the mean number of non-ripped edges by a random permutation equals $2-\frac{2}{n}$.
Added: The polynomials $C(n)=\sum_{k=0}^{n-1}\gamma_kt^k$ defined by $R(n)=\sum_{k=0}^{n-1} (n-k)!\gamma_kt^k$ (with $R$ as above attached to the Dynkin diagram of type $A$ with $n$ vertices) are also somewhat interesting since they satisfy the recursion relation $C(n+1)=(1+t)C(n)+tC(n-1)$ (initial values are $C(1)=1,C(2)=1+2t$).
On can of course generalise the above questions to arbitrary graphs (answers are obvious for complete graphs for example).