[seqfan] eulerian orientations of hypercube graphs

Brendan McKay Brendan.McKay at anu.edu.au
Fri Oct 28 03:53:42 CEST 2022

I'm wondering if anyone has information on the sequence of the title or 
would like to work on it.

I can't find anything in OEIS.

Some definitions.  A hypercube graph is the skeleton (vertices and 
edges) of a hypercube.
So for dimension 2, it is a square, and for dimension 3 it is the 
familiar graph with 8 vertices
and 12 edges.  In dimension d, there are 2^d vertices and each vertex 
has degree d.
Another description is that the vertices are the binary vectors of 
length d and edges
join vectors at Hamming distance 1.

When a graph has each vertex of even degree, it is possible to orient 
the edges so that
each vertex has equal numbers of incoming and outgoing edges. That's 
called an
eulerian orientation.  These orientations are of importance in 
statistical physics, though
I don't know of an application for the hypercube case.

For the d-dimensional hypercube to have eulerian orientations, d must be 
For d=2, there are two eulerian orientations (the cyclic ones).  If my 
little program
isn't buggy, for d=4 there are 2970 eulerian orientations (can someone 
According to A307334 <https://oeis.org/A307334> this is also the number 
of proper 3-colourings - coincidence?

Doing d=4 was a sub-second task but d=6 may be  a serious challenge.

Cheers, Brendan.

More information about the SeqFan mailing list