Let $g$ be a directed, connected multigraph, on $n$ vertices, without loops.
Define
$$P_g(x_1,\dots,x_n) := Sym\left[ \prod_{(i,j) \in g} (x_i-x_j) \right]$$
where $(i,j)$ is the directed edge from $i$ to $j,$ and $Sym$ denotes the symmetrization, that is, sum of all permutations of variables in the argument.
Now, for some multigraphs $g,$ we have that $P_g$ is identically zero.
A sufficient condition is that if we can change the direction of an odd number of edges in $g$ and obtain a graph isomorphic to $g,$ then $P_g$ is identically 0.
This is however not necessary, as the graph with edges (1,2),(2,3),(3,4),(2,4),(2,4) will give a polynomial that is identically 0.
The number of connected multigraphs with n edges that yields a zero polynomial are, for n=1,..,6, equal to 1,0,3,2,19,20, and this sequence gives no hits in Sloane.
What I am asking for is a necessary and sufficient condition of a graph that gives the zero polynomial, as defined by the procedure above.
EDIT: Note that if $g_1$ and $g_2$ are isomorphic as undirected graphs, then $P_{g_1} = \pm P_{g_2}.$ Changing the direction of one single edge changes the sign of the associated polynomial.
