A109094 maximum salesman path in K_n

[Artur]

Who know which is number of following sequence :

shortest path along the edges of the complete graph with n vertices

ARTUR



Mitch Harris pisze:
> 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
>
> __________ NOD32 Informacje 2701 (20071204) __________
>
> Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
> http://www.nod32.com lub http://www.nod32.pl 
>
>
>
>