Paper Info
Title
Distance-Balanced Graphs And Travelling Salesman Problems
Abstract
For every probability p is an element of [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.
Year
DOI
Venue
2020
10.26493/1855-3974.2096.c9d
ARS MATHEMATICA CONTEMPORANEA
Keywords
DocType
Volume
Distance-balanced graph, pTS-distance-balanced graph, total distance, wreath product of graphs
Journal
19
Issue
ISSN
Citations 
2
1855-3966
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Matteo Cavaleri102.03
Alfredo Donno2278.03