A003682 - hamilton paths - comments and (possibly constructive) criticism..

[Gordon Royle]

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