# Labeling an n-cube

1. Aug 11, 2004

### e(ho0n3

I need some closure on this one:

In how many ways can the vertices of an n-cube be labeled 0, … ,2ⁿ - 1 so that there is an edge between two vertices if and only if the binary representation of their labels differs in exactly one bit?

Let G be an appropriately labeled n-cube. Pick an arbitrary vertex v in G. How many ways can one change labels of the vertices appart from v in G and still mantain the properties of the n-cube? Because of the nature of G, there are n incident edges on v with n adjacent vertices. The labels of these vertices differ from the label of v by one bit. If one swaps the labels of two of these vertices and makes the appropriate swaps elsewhere so as to maintain the n-cube (which can be done due to the symmetry of G), one obtains a new labeling. The number of combination of adjacent vertices that can be swapped is n(n - 1)/2, so the number of different labelings of the vertices in G without changing the label of v is n(n - 1)/2.

The label of vertex v is arbitrary. Therefore, for every possible label of v there are n(n - 1)/2 labelings of the vertices in G. Because there are 2ⁿ - 1 possible labels for v, the number of possible labelings for the vertices in G is (2ⁿ - 1)(n - 1)n/2.

2. Aug 12, 2004

### TenaliRaman

3. Aug 12, 2004

### e(ho0n3

Interesting link. I just realized the formula I gave is pure BS (for one thing, the possible labels for a vertex v in G is 2ⁿ and even with this mod. the formula doesn't work). I'll have to look at this again...

Last edited: Aug 12, 2004
4. Aug 12, 2004

### e(ho0n3

OK. I think I have it know. Suppose G is an n-cube, appropriately labeled. Let v be a vertex in G. In how many ways can I change the labels of the vertices in G without changing the label of v? There are n adjecent vertices to v. I can move the labels of these vertices around (making the appropriate changes to rest of G) and obtain a new labeling of the vertices in G in n! ways. Since the label of v can be one of 2ⁿ possibilities, the number of different vertex-labelings in G is n!2ⁿ.

The sequence generated seems to be the same as that in:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eismum.cgi