The average solution of a TSP instance in a graph
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.
- A lower bound for the steiner tree problem in directed graphs
- An asymptotic resolution of a problem of Plesník
- scientific article; zbMATH DE number 687700 (Why is no real title available?)
- On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs
- On the sum of all distances in a graph or digraph
- Spanning trees with many leaves and average distance
- Steiner distance in graphs
- The average Steiner distance of a graph
- The Steiner Wiener index of a graph
- The traveling salesman problem and its variations
This page was built for publication: The average solution of a TSP instance in a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6978645)
