e(ho0n3 Posted August 9, 2004 Share Posted August 9, 2004 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. Link to comment Share on other sites More sharing options...
e(ho0n3 Posted August 10, 2004 Author Share Posted August 10, 2004 Seems this question isn't getting much attention. Perhaps it's too 'over-the-top'. Please forgive my shameless bumping. Link to comment Share on other sites More sharing options...
bloodhound Posted August 10, 2004 Share Posted August 10, 2004 I done this sort of question before, but not this complex. mainly stuff like how many ways you can colour a blah blah blah with three colours so that the adjacent sides arent the same etc. etc. Link to comment Share on other sites More sharing options...
Dave Posted August 10, 2004 Share Posted August 10, 2004 Yeah, I just don't seem to have the patience/vision for this sort of problem. Sorry Link to comment Share on other sites More sharing options...
e(ho0n3 Posted August 30, 2004 Author Share Posted August 30, 2004 It's been a long time but I think I've figured it out. Let s(n) denote the number of different vertex-labelings of an n-cube. To construct and (n+1)-cube, one combines two n-cubes G and G' by drawing an appropriate edge from a vertex in G to a vertex in G'. In how many ways can this be done? Let v be a vertex in G and v' a vertex in G' with the same label A = a[1] a[2] ... a[n]. Draw and edge from v to v'. Since the labels of v and v' must differ by one bit, one must append an extra bit x to the label of v and ~x to the label of v' in the same relative position. This can be done in n + 1 ways (in front of a[1], in front of a[2], ..., in front of a[n] or behind a[n]). Since x can have on of two values, the answer is 2(n + 1) ways. Do this for every vertex in G and G' with the same label to contruct the (n+1)-cube. Because G can have on of s(n) different vertex-labelings, then the number of different vertex-labelings in the (n+1)-cube is s(n + 1) = 2(n + 1)s(n). Solving this recurrence relations gives [math]\textstyle s(n+1) = 2^{n+1}(n+1)![/math]. Hence, the number of different vertex-labelings for an n-cube is [math]\textstyle 2^{n}(n)![/math]. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now