Vi introducerar begreppet av en centroidal lokalisering uppsättning av en graf G, det vill säga en uppsättning L av hörn så att alla hörn i G är unikt bestäms av deras relativa avstånd till hörnen av L. En centroidal lokalisering uppsättning av G av minsta storlek kallas en centroidal bas, och dess storlek är centroidal dimension CD(G). Detta begrepp, som är relaterat till tidigare begrepp, ger ett nytt sätt att identifiera hörnen i en graf. Den centroidala dimensionen av en graf G är lägre och övre bunden av den metriska dimensionen och två gånger läge-dominationen antalet G, respektive. De två sistnämnda parametrarna är standardbegrepp och välstuderade begrepp inom grafidentifieringsområdet. Vi visar att för alla diagram G med n hörn och maximal grad minst 2, (1 + o(1)) ln n ln n ≤ CD(G) ≤ n − 1. Vi diskuterar tätheten av dessa gränser och i synnerhet, vi karakteriserar uppsättningen grafer som når den övre gränsen. Vi visar sedan att för grafer där varje par av hörn är ansluten via ett begränsat antal banor, CD(G) =  och E(G), den gräns som är tight för banor och cykler. Vi undersöker slutligen den beräkningsmässiga komplexiteten i att bestämma CD(G) för en ingångsgraf G, som visar att problemet är svårt och inte ens kan approximeras effektivt upp till en faktor av o(log n). Vi ger också en O ε n n approximationsalgoritm.
Relativa avstånd och Centroidal dimension Foucaud et al. dened en variant av lösa uppsättningar, kallas centroida baser, där hörnen i en graf måste särskiljas genom sina relativa avstånd till sond hörn REF.
Centroidal bases in graphs
{'venue': 'Networks 64(2):96-108, 2014', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}