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.
Keywords
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