A109094 maximum salesman path in K_n

[Richard Mathar]

On Dec 6, 2007 7:53 AM, Richard Mathar <mathar at strw.leidenuniv.nl> wrote:
>
> A109094 looks for a longest path along the edges of the complete graph
> with n vertices.
...
> The total number of edges is n(n-1)/2. Traveling each at most once
> and not allowing return to the starting vertex gives an upper bound
> a(n) < n(n-1)/2 for n>2. Heuristically, this seems to be actually achieved for
> all odd n, and I presume that there is a "template" path argument to prove
> this case looking for some pattern in the paths listed above.
>
> There is also a simple argument why the upper bound is not reached for
> cases of even n: the connectivity of each vertex is n-1, an odd number.
> Since the path subtracts 2 (an even number) from the connectivity each
> time it passes a vertex, for n-2 vertices (all but the first and last)
> one edge is not used and remains dangling (as people in surface chemistry
> would say). So the additional deficiency in the edge count is (n-2)/2
> (at least) for even n, where the division by 2 means that there is one edge
> left over for each pair of vertices not connected by an element of the path.

The problem is more related to Euler paths (covering all -edges-)
rather than Hamilton paths (covering all nodes, whose weighted version
is called the traveling salesman problem).

Following reasoning similar to what you gave above, K_{2n+1} -always-
has an Euler cycle ,one that goes all edges (in this case n(2n+1)
edges), and since we're working on complete graphs, removing the last
edge gives the longest -path- sought. So

  a(2n+1) = n(2n+1) - 1  (or a(k) = k(k-1)/2 - 1, where k is odd = 2n+1)


Now the more interesting problem is a maximal edge covering path in
K_{2n}, because by similar reasoning just mentioned, it -never- has an
Euler path (much less an Euler cycle) for n>1.

A simple upper bound is of course n(2n-1) - 1 as you say (the total
number of edges) but since that cannot be reached, there must be a
better bound. At worst, n - 1 edges cannot be used (2n - 2 nodes have
all but 1 edge covered, the remaining 2 nodes have all edges covered)
this results in an upper bound of

  n(2n-1) - n + 1 = 2n^2 -2n + 1 (or k(k-1)/2 - k/2 + 1 where k is even = 2n)

(I'm not saying this is a(k) for even k on purpose, even though it
mght work out that way)

This gives:

  1, 2, 5, 9, 13, 20, 25, 35, 41, 54, 61, 77, 85, 104, 113, 135, 145, 170

which only differs from your examples starting at odds from 61.

But this is a simple upper bound, given without a construction.Off the
top of my head I can't think of one. Any ideas? Can one connect 2n-1
disjoint n-cycles, such that there are n left over disconnected edges?
That seems the way to go but I just can't visualize enforcing the
leftover edges being disconnected.

Mitch