An Analysis of Extreme Hamiltonian Circuits.
Kenneth Kalmanson · Defense Technical Information Center (DTIC) · 1972
The report investigates the problem of finding the shortest and longest Hamiltonian circuits on a complete graph, having finitely many vertices. Analytic conditions, involving sets of inequalities between edge lengths-which the authors call edgeconvexity- are given which lead to minimal and maximal circuits. Geometric realizations of this condition are given, which include convex polygons in the Euclidean plane and on the two-sphere. Other realizations include convex polygons in the plane where distance is measured with any linear (Minkowski) metric; points on rectifiable Jordan curve, where distance is measured by minor arc length; points in a Minkowski plane, distance measured with the Minkowski metric, where there is a minimal Hamiltonian circuit (H-circuit) whose length equals that of the perimeter of the convex hull of the set of points. (Author)