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

[Mitchell Harris]

On Fri, 7 Jan 2005, Gordon Royle wrote:

>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.
...
>(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.

The default product I normally take to be Cartesian. But it wouldn't hurt 
to help us out by adding "Cartesian".

Another name for these would be ladder graphs.

>(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.

Since the graph is undirected, a (spanning) path would also be 
considered undirected (despite being labelled, its the same path).

>(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".

the web page gives the recurrence

  C(n) = 3C(n-1) - 3C(n-2) + C(n-3), C(1)=1, C(2)=4, C(3)=8

whose solution is

  C(n) = (n^2+3n-2)/2

which does not match the numbers in the OEIS.

Combinatorially however, you can construct a system of recurrences which 
does get the formula above. You have three cases at the end of the ladder:
a) no ends of the spanning path

   +--+
   |  ...
   +--+

b) one end

   +--+        +  +
   |  ...      |  ...
   +  +        +--+

c) both ends

   +--+
      ...
   +--+

so the system of recurrences is 

A(n) = A(n-1) + 2B(n-1) (either add a cap onto a cap that is already there
                         or add a cap onto an up or down end of path)

B(n) = B(n-1) + C(n-1)  (add an up end of path to a down end of path
                         or to the bottom end of two ends)

C(n) = C(n-1)           (just extend the two ends of path)

and the total HPs are A(n) + 2B(n) + C(n) (by symmetry, B need only count 
                                           one direction)

(base cases are A(2) = B(2) = C(2) = 1)

So by elimination we get

  C(n) = 1
  B(n) = B(n-1) + 1 = n-1
  A(n) = A(n-1) + 2(n-1) = n^2 - 3n + 3

  A(n) + B(n) + C(n) = n^2 - n + 2

So, yes, formula.

But now the question is where did the (erroneous) recurrence(s) come from. 
(the numbers are from exhaustive search so I "trust" them better)

-- 
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://lat.inf.tu-dresden.de/~harris