Let $G=(V,E)$ be a simple graph.
My question: For what graph $G$, does there exist a permutation $\sigma$ on $V$ such that $$\prod_{uv\in E}(x_{\sigma(u)}-x_{\sigma(v)})=-\prod_{uv\in E}(x_u-x_v)?$$
For example, when $G$ is the complete graph $K_n$, any transposition on $V$ satisfies the above property.
Is there any known result about my problem? Any idea is welcome!
I don't know about the literature on your specific problem but I know this arises as a trivial subquestion of a more general one for which there is literature, most of it from the 19th century.
Let $P_G(x)$ denote your polynomial. If the graph is $k$-regular then you can make a homogenized version $$ HP_G(x,y)= \prod_{uv\in E}(x_uy_v-x_vy_u) $$ and then a symmetrized version of the latter $SHP_G$ where you sum over permutations of the pairs $(x_u,y_u)$. What you get is an $SL_2$ invariant of binary forms. In fact you can do this identification in two ways:
1) by seeing the pairs as homogeneous roots and so the invariant is of degree $k$ in the coefficients of a binary form of degree $|V|$,
2) by seeing the pairs as symbolic letters and so the invariant is of degree $|V|$ in the coefficients of a binary form of degree $k$.
The precise relationship between the two interpretations is the isomorphism of $SL_2(\mathbb{C})$ modules $$ {\rm Sym}^{k}({\rm Sym}^{|V|}(\mathbb{C}^2))\simeq {\rm Sym}^{|V|}({\rm Sym}^{|k|}(\mathbb{C}^2)) $$ known as Hermite reciprocity. This also works for nonregular graphs by completing the polynomial with extra factors $(x_u\times 0 - x_v\times 1)$ involving the "difference with respect to the point at infinity", in which case you get a covariant instead of an invariant. The above Hermite reciprocity covers this more general case too.
Now you see there is a composition of maps: $$ {\rm graph}\ G\ \rightarrow\ SHP_G\ \rightarrow {\rm invariant\ or\ covariant} $$ The second is injective and also surjective if one takes linear spans. The first map however is completely mysterious and highly noninjective. This poses the fundamental question (that every classical invariant theorist has confronted at some point):
How to tell if $SHP_G=0$ simply by looking at the graph?
The simplest reason for which $SHP_G=0$ is when there exists a permutation as in this MO question. However, this is not the only possibility, as shown by the (multi)graph with $$ P_G=(x_1-x_2)^2(x_1-x_3)(x_2-x_3)\ . $$
For pointers to the literature on the wider question I formulated above, see my answer to the MO question Symmetric polynomial from graphs and in particular the reference to the papers by Sabidussi.
