1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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