A003682 - hamilton paths - comments and (possibly constructive) criticism..
Gordon Royle
gordon at csse.uwa.edu.au
Fri Jan 7 07:47:23 CET 2005
The sequence
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/
eisA.cgi?Anum=A003682
lists the numbers of Hamilton paths in a certain sequence of graphs.
It arose (strangely enough) in my research when I was counting the
number of simple cographic matroids with number of elements equal to
rank + 2, but this is not really the point of this posting.
The point is that I had some difficulty in working out how this
sequence was defined, due as is often the case, to some ambiguity in
the definitions....
The problems I had were as follows:
(1) What graph is it?
-the "product" of two graphs is an ambiguous expression, as there are
quite a number of different graph products around. As it turns out, the
one being used in this situation is actually the "Cartesian product" of
the two graphs in question. I think that it is impossible to use the
word "product" without further explanation or a small example... In
this case, the small example of K2 x K2 = C4 (the 4-cycle) would
probably suffice.
(2) What is being counted?
- the name says "hamilton paths", but it is not actually hamilton
paths in the normal sense of the words. For example, C4 has 8 hamilton
paths - if the vertices are labelled ABCD in cyclic order, then the 8
paths are ABCD, BCDA, CDAB, CABD, ADCB, BACD, DBAC, DCBA but the given
number is only 4. In fact, each path and its reverse only contribute 1
to the count.
(3) The comment "a(2) to a(47) are given by n^2-n+2" is odd, because
the original paper (by Faase) gives a recurrence for the numbers, which
indeed has this as its solution... so maybe the comment could be
upgraded to a "formula".
Any comments on my comments?
Belated Happy New Year to all..
Gordon
More information about the SeqFan
mailing list