On the (k, t)-metric dimension of a graph

Abstract

En aquesta tesi s'estudia la dimensió (k,t)-mètrica dels grafs. Particularment s'emfatitza en la dimensió k-mètrica i la dimensió de k-adjacència. Al primer capítol es dedica als conceptes bàsics i les notacions emprades a la tesi. Al segon capítol es determina el més gran enter k, de manera que hi ha una base (k,t) -mètrica d'un graf. Es mostra, a més, que la complexitat temporal de calcular aquest valor de k és cúbica, pel que fa a l'ordre del graf. Al tercer capítol, s'obtenen fórmules tancades i cotes per a la dimensió (k,t) -mètrica d'alguns grafs. Així mateix, es delimita el valor de la dimensió k-mètrica en funció de paràmetres relacionats amb la distància, i es descriuen les classes de grafs en què s’aconsegueixen aquestes cotes com, per exemple, en els arbres. En particular, per a aquests últims, s'estableix una fórmula per calcular la dimensió k-mètrica de qualsevol arbre. També s'estudia la dimensió de k-adjacència de diversos grafs perquè s'ha trobat una forta relació entre la dimensió k-mètrica de productes de grafs i la dimensió de k-adjacència d'un dels seus factors. Aquesta relació permet obtenir nombrosos resultats per al producte lexicogràfic i per al producte corona. A l'últim capítol, es demostra que trobar el més gran enter k, de manera que hi hagi una base (k,t) –mètrica d’un graf, es pot resoldre en temps cúbic pel que fa a l'ordre del graf. Es prova, a més, que el problema de calcular la dimensió és NP-complex a través d'una transformació polinòmica al 3-SAT. Malgrat tot, per la fórmula obtinguda per a la dimensió k-mètrica d’arbres (que es demostra al capítol 3), es proposa un algoritme que es pot resoldre en temps lineal per determinar la dimensió k-mètrica i una base k-mètrica de qualsevol arbre.

En esta tesis se estudia la dimensión (k, t)-métrica de los grafos. Particularmente se enfatiza en la dimensión k-métrica y la dimensión de k-adyacencia. El primer capítulo se dedica a los conceptos básicos y las notaciones empleadas en la tesis. En el segundo capítulo se determina el mayor entero k, de modo que existe una base (k, t)-métrica de un grafo. Se muestra, además, que la complejidad temporal de calcular este valor de k es cúbica, con respecto al orden del grafo. En el tercer capítulo, se obtiene fórmulas cerradas y cotas para la dimensión (k, t)-métrica de algunos grafos. Asimismo, se acota el valor de la dimensión k-métrica en función de parámetros relacionados con la distancia, y se describe las clases de grafos donde estas cotas son alcanzadas, como por ejemplo en los árboles. En particular, para estos últimos, se establece una fórmula para calcular la dimensión k-métrica de cualquier árbol. También se estudia la dimensión de k-adyacencia de varios grafos debido a que se ha encontrado una fuerte relación entre la dimensión k-métrica de productos de grafos y la dimensión de k-adyacencia de uno de sus factores. Esta relación permite obtener numerosos resultados para el producto lexicográfico y el producto corona. En el último capítulo, se demuestra que encontrar el mayor entero k, de modo que exista una base (k, t)-métrica de un grafo, puede resolverse en tiempo cúbico con respecto al orden del grafo. Se prueba además que el problema de calcular la dimensión es NP-complejo a través de una transformación polinómica al 3-SAT. No obstante, por la fórmula obtenida para la dimensión k-métrica de árboles (demostrada en el capítulo 3), se propone un algoritmo que puede ser resuelto en tiempo lineal para determinar la dimensión k-métrica y una base k-métrica de cualquier árbol.

In this thesis we study the (k, t)-metric dimension of graphs. The central results of the thesis are focused on the k-metric dimension and the k-adjacency dimension. The first chapter is devoted to the basic concepts and the notations used in the thesis. In the second chapter we find the largest integer k such that there exists a (k,t)-metric basis of a graph. We also show that the time complexity of computing this value k is cubic with respect to the order of the graph. In the third chapter, we obtain closed formulae and bounds for the (k,t)-metric dimension of some graphs. We also bound the value for the k-metric dimension of graphs in terms of parameters related to the distance and we describe some classes of graphs where these bounds are achieved, such as trees. In particular, we give a formula for computing the k-metric dimension of any tree. We also study the k-adjacency dimension of several graphs due to we have found a strong relationship between the k-metric dimension of product graphs and the k-adjacency dimension of one of its factors. This relationship allows us to obtain several results for the lexicographic product and corona product. In the last chapter, we prove that finding the value k such that there exists a $(k,t)$-metric basis of a graph can be solved in cubic time with respect to the order of the graph. We also show that the problem of computing the k-metric dimension of a graph is NP-Hard through a polynomial transformation from the 3-SAT problem. However, by using a obtained formula for the k-metric dimension of trees (proven in Chapter 3), we propose algorithms, which can be solved in linear time, for determining the k-metric dimension and a k-metric basis of any tree.