Concerning the problem of "square" chains and necklaces: Now I am confident that for n < 32 the only values of n for which a chain exists are 15, 16, 17, 23 and 25 thru 31. It seems that for n > 31 cycles always exist. I have only checked this up to 50 or so plus 64, 100 and 200. The latter two were done using Bill Kocay's program Groups and Graphs. (The Hamiltonian cycle for the case n = 200 is found almost immediately!). My colleague Stephen Suen thought of a related question. Is there a Hamiltonian path for the infinite graph with vertices = all positive integers with adjacence defined by "sum to a square"? I decided to write a greedy program to see how far this would take me. Then I looked at Sloane's EIS and found the sequence ID Number: A034175 Sequence: 0,1,3,6,10,15,21,4,5,11,14,2,7,9,16,20,29,35,46,18,31,33,48, 52,12,13,23,26,38,43,57,24,25,39,42,22,27,37,44,56,8,17,19, 30,34,47,53,28,36,45,55,66,78,91,105,64,80,41,40,60,61,83, 86,58,63,81,88,108,117,79,65 Name: a(n) is minimal such that a(n)+a(n-1) is a square and a(n) is not in {a(0), ..., a(n-1)}. Comments: Conjectured to be a permutation of the nonnegative integers [There is also a similar sequence in EIS for "sums to a prime".] Here's a more general question: Let G be a graph whose vertices are N, the natural numbers. Suppose for every n the subgraph G_n of G induced on {1,2,...,n} has a Hamiltonian path starting with 1. Does G necessarily have a Hamiltonian path? (The converse is false as the graph 1-3-2-5-4-7-6-... shows.) Edwin Clark On Sat, 23 Nov 2002, Richard Guy wrote:
Thanks for your comments. The argument about 20 to 30 having only one vertex of valence one doesn't quite work, since you can drop an edge to a 2-valent vertex to make the other end of the chain. Ed Pegg has chains for 23, 25, 26, 27, 28, 29, 30, 31 and cycles (which can be broken anywhere to make a chain) for 32, 33, 34, 35, 36, 37. Probably cycles exist for all n from here on, but I haven't proved it. R.
On Fri, 22 Nov 2002, Edwin Clark wrote:
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/ ------------------------------------------------------------
------------------------------------------------------------ W. Edwin Clark, Math Dept, University of South Florida, http://www.math.usf.edu/~eclark/ ------------------------------------------------------------