293 KB35 KB200820252020Cavaleri, MatteoDonno, Alfredoletnik:19številka:2str. 311-324ISSN:1855-3974COBISSID_HOST:44729091URN:URN:NBN:SI:doc-E3QSAC72enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneadistance-balanced graphpopolna razdaljapTS-distance-balanced graphpTS-razdaljno uravnotežen grafrazdaljno uravnotežen graftotal distancevenčni produkt grafovwreath product of graphsDistance-balanced graphs and travelling salesman problems|For every probability ?$p \in 0, 1$? we define a distance-based graph property, the ?$p$?TS 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 ?$p$?TS-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 ?$p$?TS-distance-balancedness of the factorsZa poljubno verjetnost ?$p \in 0, 1$? definiramo lastnost grafa, ki temelji na razdalji, in jo imenujemo ?$p$?TS-razdaljna uravnotežljivost. Za ?$p=0$? sovpada s standarno lastnostjo razdaljne uravnotežljivosti, za ?$p=1$? pa je povezana s hamiltonsko povezljivostjo grafa. Po analogiji s klasičnim primerom, pri katerem je razdaljna uravnotežljivost grafa ekvivalentna lastnosti biti sebi medianski, karakteriziramo ?$p$?TS-razdaljno uravnotežene grafe z neko verjetnostno mero centralnosti, ki izhaja iz problema trgovskega potnika. Dokažemo, da je mogoče razpoznati to lastnost tako, da preverimo klasično razdaljno uravnotežljivost oziroma klasične probleme centralnosti venčnega produkta grafov. Drugače povedano, karakteriziramo razdaljno uravnotežljivost grafov tega produkta s ?$p$?TSrazdaljno uravnotežljivostjo njegovih faktorjevTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije