Distance-balanced graphs and travelling salesman problems

Matteo Cavaleri, Alfredo Donno


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.


Distance-balanced graph, pTS-distance-balanced graph, total distance, wreath product of graphs

Full Text:


DOI: https://doi.org/10.26493/1855-3974.2096.c9d

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications