[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
even.
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
check?).
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