The average solution of a TSP instance in a graph (Q6978645)

Distance is an important concept that pervades all of graph theory. Beginning with the shortest distance, also known as geodesic, between the vertices of a graph, several types of distances like detour distance, monophonic distance, Steiner distance, etc., have been introduced and studied in the literature. Given a set of \(k\) vertices in a graph \(G\), the problem of demanding the shortest closed walk that travels through all these \(k\) vertices is the well-known travelling salesman problem (TSP).\N\NIn this article, the distance between two vertices of a graph, based on the shortest closed walk that travels through a set of \(k\) vertices, for all possible \(k\), called the \(k\)-TSP distance, is introduced in both graphs and digraphs. In addition, the concepts of the average \(k\)-TSP distance and \(k\)-TSP Wiener indices are defined analogously to the Steiner distance and Steiner-Wiener index of graphs for the TSP. Introducing these concepts, this article mainly focuses on comparing and relating the newly defined notions with the existing ones.\N\NIn this regard, it is proved that the \(k\)-TSP Wiener index of graphs is always less than or equal to twice the \(k\)-Steiner Wiener index of graphs, and a characterization of when the equality holds is also given (Proposition 5 and Proposition 9). A similar relation between the \(k\)-TSP Wiener index and the Wiener index of graphs, along with the characterization of when the two indices are equal (Theorem 6). These characterizations obtained showcase the relevance of the newly introduced notions, as we see that the \(k\)-TSP Wiener index of graphs coincide with the \(k\)-Steiner Wiener index or the Wiener index of graphs only in few cases.\N\NOn the other hand, it has been observed that the relation between the \(k\)-TSP Wiener index and \(k\)-Steiner Wiener index gets reversed in the case of digraphs (Proposition 10), which is interesting to note. In addition to this, certain bounds on the average TSP-distance, or equivalently \(k\)-TSP Wiener index of graphs of order \(n\), are determined based on the complete graphs and paths of order \(n\), and an estimate of the average TSP-distance of \(C_n\) is also obtained. With this estimate, they prove that the analogue of the classic DeLaViña-Waller conjecture on the geodesics of a graph is true for the \(k\)-TSP Wiener index of graphs if and only if \(k=2,3\) (Lemma 14 and Theorem 15).\N\NFinally, the notions of eccentricity, radius and diameter of graphs are extended with respect to the \(k\)-TSP distance, and some immediate observations are made on the same. In conclusion, this article offers a huge scope for extension as a new variant of distance with respect to TSP is introduced, and how it stands out from the existing related or analogous notions is proved here. From verifying if this new variant of distance is a metric on graphs, to define and study different distance-related concepts based on the \(k\)-TSP distance of graphs, this article puts forth a lot of opportunities for further research.