Re: Gray Codes & Hamiltonian Circuits


Costas Vlachos wrote:
Costas Vlachos wrote:
I have a question regarding the number of different n-bit Gray codes
that can exist for a given positive integer n.
[...]
Replying to my own message!

Well, I posted an answer in another newsgroup already.

If you are going to ask the same question in more than one newsgroup,
you should cross-post them; that is, post the question to all of the
newsgroups at the same time. That way, answers to one thread will show
up in another, and you only have to check one to find out if there are
any updates.

I re-posted to sci.math.research and got a
reply there, which pointed me to Sloanne's online encyclopaedia of
integer sequences. The following two sequences are relevant to the problem:

http://www.research.att.com/~njas/sequences/A066037

http://www.research.att.com/~njas/sequences/A003042

The second one is the first multiplied by 2. With the way I defined
"different" when comparing Gray codes in my original post, sequence
A003042 applies (1,2,12,2688,...). If the direction of each Gray code is
ignored, then sequence A066037 applies (1,1,6,1344,...). From the links
it appears that only 5 terms of the sequence are known, with the 6th
being estimated to be very large, much larger than n!.

The following two papers are relevant:

R. J. Douglas, Bounds on the number of Hamiltonian circuits in the
n-cube, Discrete Mathematics, 17 (1977), 143-146.

Harary, Hayes and Wu, A survey of the theory of hypercube graphs,
Computers and Mathematics with Applications, 15(4), 1988, 7-289.

I managed to find the second one on the net. If anyone is able to
provide the first one (Douglas, 1977) electronically that would be
great. Many thanks to all!

If you have access to JSTOR (if you use a computer at a university),
you can get it from
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V00-45FSP3S-48&_user=10&_handle=C-WA-A-BC-BC-MsSAYWB-UUW-U-U-BC-U-U-AADUABYDWD-AAZDDAECWD-AYWDYUECE-BC-U&_fmt=summary&_coverDate=12%2F31%2F1977&_rdoc=18&_orig=browse&_srch=%23toc%235632%231977%23999799999%23297957!&_cdi=5632&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=3594d16df794ec25981257710e616a66

("quoted" to make sure that Google Groups doesn't break the line)

--- Christopher Heckman

.

Relevant Pages