Distance-balanced graphs and travelling salesman problems - Cavaleri, Matteo (Ars mathematica contemporanea, 2020)
Za 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 faktorjev.
Keywords: distance-balanced graph; popolna razdalja; pTS-distance-balanced graph; pTS-razdaljno uravnotežen graf; razdaljno uravnotežen graf; total distance; venčni produkt grafov; wreath product of graphs