Distance-balanced graphs and travelling salesman problems

Abstract

For every probability p ∈ [0, 1] we define a distance-based graph property, the pTS-distance-balancedness, that in the case p = 0 coincides with the standard property of distance-balancedness, and in the case p = 1 is related to the Hamiltonian-connectedness. In analogy with the classical case, where the distance-balancedness of a graph is equivalent to the property of being self-median, we characterize the class of pTS-distance-balanced graphs in terms of their equity with respect to certain probabilistic centrality measures, inspired by the Travelling Salesman Problem. We prove that it is possible to detect this property looking at the classical distance-balancedness (and therefore looking at the classical centrality problems) of a suitable graph composition, namely the wreath product of graphs. More precisely, we characterize the distance-balancedness of a wreath product of two graphs in terms of the pTS-distance-balancedness of the factors.