Re: [math-fun] Square (& other) chains and necklaces.

23 Nov 2002


      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/
------------------------------------------------------------