Binary invariants and orientations of graphs (Q1197033)

Julius Petersen posed the following problem: (L'Intermédiaire des Mathématicens 1 (1894), p.\ 24, Problem 66) ``Soit \(u_ 0=(x_ 1-x_ 2)^ \alpha(x_ 1-x_ 3)^ \beta(x_ 2-x_ 3)^ \gamma... (x_{n- 1}-x_ n)^ \mu\) une expression où les exposants \(\alpha\), \(\beta\), \(...\), sont des entiers positifs, ou zéro; \(u_ 0\) étant du même degré en \(x_ 1,x_ 2,...,x_ n\). De \(u_ 0\) déduisons \(u_ 1,u_ 2,...\) en faisant toutes les permutations possibles entre \(x_ 1,x_ 2,...,x_ n\). La somme \(u_ 0+u_ 1+...\) est une fonction symétrique de \(x_ 1,x_ 2,...,x_ n\) qui peut être identiquement nulle. Est-il possible de trouver des conditions simples que doive remplir \(u_ 0\) pour que cela ait lieu?'' The present author interprets the problem as ``of the type: Given a regular graph and a property of its induced invariant, what can be said about the graph? ... In \S3 we discuss the connection between the vanishing of the induced invariant and properties of the orientations of the graph. On the basis of a classical result about the existence of invariants of degree 3 we then show that the answer to Question 66 is negative (\S4). \S5 is devoted to orientations of 3-regular graphs. The existence or non-existence of `odd reorientations' (reversals of an odd number of edges) which preserve all outdegree sequences is dealt with by invariant theoretical means as well as purely graph theoretical ones. The final section contains some remarks about a class of orientations whose presence ensures that the graph induces a nonvanishing invariant''.