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

[Richard Guy]

Lovasz, in a lecture in Atlanta a couple of
days ago, mentioned a graph that he called V_8
It is an 8-cycle, with the 4 pairs of diametrically
opposite points joined.  It is in fact a M"obius
ladder, a fact he pretended not to know.

Same as the ladder mentioned below, but with the
sides joined the wrong way round.  As described
above, its crossing number might appear to increase
with  n,  but in fact it's 1.

See MR 37 #2627 or #98.      R.

On Sat, 8 Jan 2005, Gordon Royle wrote:

>> 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.
>
> Better be careful here.. the "ladder" is a well-known graph which is the 
> Cartesian product of K_2 and a *cycle* not a path..
>
>>> e 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
>
> Actually there is no problem with the recurrence or the formula - the only 
> problem is C(1) which is the "odd man out" in the scheme of things. If you 
> solve the recurrence, but using C(2), C(3) and C(4) as the "base cases" 
> then you get the stated formula, which is correct for all values other 
> than C(1).
>
> C(1) counts hamilton paths in K_2 and according to the formula it "wants" 
> to be equal to 2, but collapses to 1 in this small case.
>
> Gordon