On the local metric dimension of graphs

Abstract

La dimensió mètrica d'un espai mètric general es va introduir el 1953, però va atreure poca atenció fins que, uns vint anys més tard, es va aplicar a les distàncies entre els vèrtexs d'un graf. Des de llavors s'ha utilitzat amb freqüència en la teoria de grafs, la química, la biologia, la robòtica i moltes altres disciplines. A causa de la multiplicitat de situacions de les que pot sorgir el problema de distingir els vèrtexs d'un graf, diverses variants del concepte original de la dimensió mètrica ha anat apareixent en la literatura especialitzada. En aquesta tesi s'estudia una d'aquestes variants, és a dir, la dimensió mètrica local. En concret, aquesta tesi ens centrem en el problema de calcular la dimensió mètrica local de grafs. En primer lloc, presentem l'estat de l'art de la dimensió mètrica local i obtenim alguns resultats originals en els que caracteritzem tots els grafs que atenyen algunes fites conegudes. En segon lloc, obtenim fórmules tancades i fites tenses per a la dimensió mètrica local de diverses famílies de grafs, incloent grafs producte fort, grafs corona i grafs producte lexicogràfic. Finalment, introduïm l'estudi de la dimensió mètrica local simultània i donem alguns resultats generals en aquesta nova línia d'investigació.

La dimensión métrica de un espacio métrico general fue introducida en 1953, pero atrajo poca atención hasta que, aproximadamente veinte años más tarde, se aplicó a las distancias entre vértices de un gráfico. Desde entonces se ha utilizado con frecuencia en la teoría de los gráficos, la química, la biología, la robótica y muchas otras disciplinas. Debido a la multiplicidad de situaciones desde las que puede surgir el problema de distinguir los vértices de un gráfico, en la literatura especializada han aparecido varias variantes del concepto original de dimensión métrica. En esta tesis estudiamos una de estas variantes, a saber, la dimensión métrica local. En particular, nos centramos en el problema de calcular la dimensión métrica local de grafos. Primero presentamos el estado del arte de la dimensión métrica local y presentamos algunos resultados originales en los que caracterizamos todos los grafos que alcanzan algunas de las cotas conocidas. En segundo lugar, obtenemos fórmulas cerradas y cotas tensas para la dimensión métrica local de varias familias de grafos, entre los que destacamos los grafos producto fuerte, grafos corona y grafos producto lexicográfico. Finalmente, introducimos el estudio de la dimensión métrica local simultánea y damos algunos resultados generales en esta nueva línea de investigación.

The metric dimension of a general metric space was introduced in 1953 but attracted little attention until, about twenty years later, it was applied to the distances between vertices of a graph. Since then it has been frequently used in graph theory, chemistry, biology, robotics and many other disciplines. Due to the variety of situations from which the problem of distinguishing the vertices of a graph can arise, several variants of the original concept of metric dimension have been appearing in specialized literature. In this thesis we study one of these variants, namely, the local metric dimension. Specifically, we focus on the problem of computing the local metric dimension of graphs. We first report on the state of the art on the local metric dimension and present some original results in which we characterize all graphs that reach some known bounds. Secondly, we obtain closed formulas and tight bounds on the local metric dimension of several families of graphs, including strong product graphs, corona product graphs, rooted product graphs and lexicographic product graphs. Finally, we introduce the study of simultaneous local metric dimension and we give some general results on this new research line.