On Fri, 22 Nov 2002, Richard Guy wrote:
I recently mentioned a problem of finding chains and necklaces in which adjacent links add to a square (or other things). Such problems can be restated as: Draw a graph having the numbers from 1 to n as vertices and an edge between any pair of vertices whose labels add to a square (or whatever). Is there a Hamilton path (circuit) in the graph? For example (requested by at least one listener), n = 32.
28 8 1 15 10 21 26 4 23 32 2 17 14 19 22 30 27 6 9 3 16 13 20 12 29 24 7 25 11 5 31 18
This can be upped to 33 by inserting
... 9 16 33 31 18 7 29 20 5 11 ...
so we now have chains for n = 15 16 17 31 32 33 34 35 ... (and no smaller others??).
Dealing with the case where i adjacent to j iff i + j is a square: A short Maple program shows that for n < 14 the graphs are not connected and so cannot contain Hamiltonian circuits or paths. The graph for n = 14 has three vertices for degree one so clearly cannot contain either a spanning path or circuit. n=18 is not possible since it has 3 degree 1 vertices n = 20 thru 30 each have only one vertex of degree 1 so they are also ruled out. The graph for n = 19 has degree sequence [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3] and according to Maple is connected. So it could have a Hamiltonial path. But I have a little ad hoc argument that shows it cannot. So I guess you have the beginning of a new sequence for the OLEIS. Edwin ------------------------------------------------------------ W. Edwin Clark, Math Dept, University of South Florida, http://www.math.usf.edu/~eclark/ ------------------------------------------------------------