# Labelling the Nodes of a Hypercube

I'm trying to find out how many ways can I label the nodes of a n dimensional hypercube. The nodes of a n dimensional hypercube can be labelled from 0 to (2^n - 1) in such a way that there is an edge between any two vertices if and only if the binary representations of their labels differ by one and only one bit.

It seems there are a lot of ways to label such a hypercube, but I'm having a hard time formulating it.

I would appreciate your help.

-
If you're asking how many ways you can assign the numbers $0, \dots, 2^n-1$ to the vertices of a hypercube, it's simply $(2^n)!$. – Dimitrije Kostic Nov 28 '11 at 15:21
@DimitrijeKostic: That's not what he's asking. Vertices connected by an edge need to differ by only one bit. – Grumpy Parsnip Nov 28 '11 at 15:32
@DimitrijeKostic Jim is right. I wish it was that simple, but each node is connected to the nodes that are different from him by one bit only. – Maynard Nov 28 '11 at 15:55

Consider a hypercube canonically embedded into $\mathbb R^n$, such that, in particular, the vertices have coordinates in $\{0,1\}^n$ and the edges are aligned with the coordinate axes. Each coordinate of each vertex can then be naturally represented by a single bit, and two vertices are connected by an edge if and only if their coordinates differ along only one axis.

There are $n!$ ways to map the $n$ coordinate axes to the bits of an $n$-bit string. Furthermore, for each bit, there is a choice of two complementary representations (corresponding to mirroring the hypercube along the axis), for a total of $2^n$ choices. Thus, we have (at least) $n! \cdot 2^n$ distinct ways to map the vertices of an $n$-hypercube onto $n$-bit bitstrings such that adjacent vertices map to strings that differ by one bit.

Showing that these indeed constitute all such mappings is a bit more difficult, but I really just wanted to point out this method of enumerating the mappings for the sake of its nice geometric interpretation.

A related approach is to embed the hypercube into $\mathbb R^n$ such that the vertices lie in $\{-1,1\}^n$, and note that symmetries of the hypercube can then be represented by $n \times n$ signed permutation matrices, which form the hyperoctahedral group of order $n! \cdot 2^n$.

-
thanks for the explanation. It's a nice approach to solve this problem. – Maynard Nov 30 '11 at 21:11

In an n-dimensional hypercube there is 2^n nodes each with n neighbours. For the first 2^n bit strings, each node has n neighbours. So you need to show that these determine the same graphs, otherwise the answer is 0.

After that, you can label the first vertice in 2^n ways, and it has n-fold symmetry around each point, so total $n!2^n$ labelings.

Look here for references: http://oeis.org/A000165

-
Alternatively, view each labelling as an automorphism of the hypercube graph (mapping some canonical labelling of the vertices to the current one). Harary published a paper called The Automorphism Group of a Hypercube in JUCS in 2000, which constructs the group explicitly (and gives the same result for its size). – Erik P. Nov 28 '11 at 17:06
@Holowitz thanks. – Maynard Nov 30 '11 at 21:13