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.

Pravice

URN

URN:NBN:SI:DOC-E3QSAC72

COBISSID

44729091

Objavljeno

28.04.2021

Metapodatki

Citiranje

APA:

Cavaleri, Matteo, Donno, Alfredo (2020). Distance-balanced graphs and travelling salesman problems. Ars mathematica contemporanea, letnik 19, številka 2, str. 311-324. URN:NBN:SI:DOC-E3QSAC72 from http://www.dlib.si

MLA:

Cavaleri, Matteo, Donno, Alfredo. "Distance-balanced graphs and travelling salesman problems." Ars mathematica contemporanea letnik 19. številka 2 (2020) str. 311-324.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-E3QSAC72>

Ars mathematica contemporanea
2008-
(Zbirni zapis)