The average solution of a TSP instance in a graph

MaRDI QIDQ6410043zbMATH OpenFDO

Authors Stijn Cambie

Publication date 7 September 2022

Mathematics Subject Classification ID

Trees (05C05) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Distance in graphs (05C12) Extremal problems in graph theory (05C35)

Abstract: We define the average $k$-TSP distance $m{u}_{tsp,k}$ of a graph $G$ as the average length of a shortest walk visiting $k$ vertices, i.e. the expected length of the solution for a random TSP instance with $k$ uniformly random chosen vertices. We prove relations with the average $k$-Steiner distance and characterize the cases where equality occurs. We also give sharp bounds for $m{u}_{tsp,k}(G)$ given the order of the graph.

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 Q6410043)