Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2012 January 25

From Wikipedia, the free encyclopedia
Mathematics desk
< January 24 << Dec | January | Feb >> January 26 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


January 25

[edit]

number of non-isomorphic hamiltonian cycle on n-cubes?

[edit]

For n=1, 2 and 3 all hamiltonian cycles on the edges of an n-cube are isomorphic to each other but this is not true for n=4. I think there are at least 3 based on whether the edge which is "removed" from the cycles of two 3-cubes to connect the cycles is in the dimension where the n=3 hamiltonian cycle changes value 4 times or the two dimensions where it only changes twice. For example if the cycle on n=3 is 000,001,011,010,110,111,101,100(,000) then the third position is the one that changes 4 times. I've been looking at oeis, specifically at oeis:A66037, but I don't understand why they appear to have a value greater than 1 for n=3, since as far as I can tell, all n=3 hamiltonian cycles are isomorphic to each other. Any ideas?Naraht (talk) 15:18, 25 January 2012 (UTC)[reply]

The OEIS sequence does not count isomorphism classes but cycles with a fixed starting point and direction. oeis:A091302 is probably closer to what you had in mind but it's still not counting isomorphism classes in the graph theoretic sense. I get two paths according to the A091302 definition: 000,001,011,010,110,111,101,100 and 000,001,011,111,101,100,110,010; there is an isomorphism of the cube which takes one to the other, but it's not obtained by permuting indices so the cycles are counted as different. I couldn't find an OEIS sequence for actual isomorphism classes, it seems like there ought to be one if the values are known.--RDBury (talk) 17:17, 25 January 2012 (UTC)[reply]
PS. [1] has some current research on the subject. Apparently the number of isomorphism classes is known only up to the 5-cube.--RDBury (talk) 17:42, 25 January 2012 (UTC)[reply]
Thank you for the link, that's a place to start. The numbers grow *really* rapidly...Naraht (talk) 22:36, 25 January 2012 (UTC)[reply]
For what it's worth, I added it as OEISA159344 to collect some of the references and results. Maybe that would be useful to you? CRGreathouse (t | c) 18:30, 26 January 2012 (UTC)[reply]
I've never had an OEIS sequence made for me before, Thank You. I'm touched (someone would say in the head :) )Naraht (talk) 01:57, 27 January 2012 (UTC)[reply]
Glad to have done it. :) CRGreathouse (t | c) 03:23, 29 January 2012 (UTC)[reply]

What is And --84.61.131.15 (talk) 17:30, 25 January 2012 (UTC)[reply]