The Average Solution of a TSP Instance in a Graph

ABSTRACT We define the average ‐TSP distance of a graph as the average length of a shortest closed walk visiting vertices, that is, the expected length of the solution for a random TSP instance with uniformly random chosen vertices. We prove relations with the average ‐Steiner distance and characterize the cases where equality occurs. We also give sharp bounds for given the order of the graph.