Geodesic
Distance-balanced graphs and travelling salesman problems
Ars Mathematica Contemporanea, Tome 19 (2020) no. 2, pp. 311-324.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.2096.c9d
Keywords: Distance-balanced graph, pTS-distance-balanced graph, total distance, wreath product of graphs 
@article{10_26493_1855_3974_2096_c9d,
     author = {Matteo Cavaleri and Alfredo Donno},
     title = {Distance-balanced graphs and travelling salesman problems},
     journal = {Ars Mathematica Contemporanea},
     pages = {311--324},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2020},
     doi = {10.26493/1855-3974.2096.c9d},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2096.c9d/}
}
TY  - JOUR
AU  - Matteo Cavaleri
AU  - Alfredo Donno
TI  - Distance-balanced graphs and travelling salesman problems
JO  - Ars Mathematica Contemporanea
PY  - 2020
SP  - 311
EP  - 324
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2096.c9d/
DO  - 10.26493/1855-3974.2096.c9d
LA  - en
ID  - 10_26493_1855_3974_2096_c9d
ER  - 
%0 Journal Article
%A Matteo Cavaleri
%A Alfredo Donno
%T Distance-balanced graphs and travelling salesman problems
%J Ars Mathematica Contemporanea
%D 2020
%P 311-324
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2096.c9d/
%R 10.26493/1855-3974.2096.c9d
%G en
%F 10_26493_1855_3974_2096_c9d
Matteo Cavaleri; Alfredo Donno. Distance-balanced graphs and travelling salesman problems. Ars Mathematica Contemporanea, Tome 19 (2020) no. 2, pp. 311-324. doi : 10.26493/1855-3974.2096.c9d. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2096.c9d/

Cité par Sources :