Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Labeling an n-cube

  1. Aug 11, 2004 #1
    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. jcsd
  3. Aug 12, 2004 #2
  4. Aug 12, 2004 #3
    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
  5. Aug 12, 2004 #4
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?