Strong resolvability in product graphs.

Abstract

En aquesta tesi s'estudia la dimensió mètrica forta de grafs producte. Els resultats més importants de la tesi se centren en la recerca de relacions entre la dimensió mètrica forta de grafs producte i la dels seus factors, juntament amb altres invariants d'aquests factors. Així, s'han estudiat els següents productes de grafs: producte cartesià, producte directe, producte fort, producte lexicogràfic, producte corona, grafs unió, suma cartesiana, i producte arrel, d'ara endavant "grafs producte".

Hem obtingut fórmules tancades per la dimensió mètrica forta de diverses famílies no trivials de grafs producte que inclouen, per exemple, grafs bipartits, grafs vèrtexs transitius, grafs hamiltonians, arbres, cicles, grafs complets, etc, i hem donat fites inferiors i superiors generals, expressades en termes d'invariants dels grafs factors, com ara, l'ordre, el nombre d'independència, el nombre de cobriment de vèrtexs, el nombre d'aparellament, la connectivitat algebraica, el nombre de cliqué, i el nombre de cliqué lliure de bessons. També hem descrit algunes classes de grafs producte, on s'assoleixen aquestes fites.

És conegut que el problema de trobar la dimensió mètrica forta d'un graf connex es pot transformar en el problema de trobar el nombre de cobriment de vèrtexs de la seva corresponent graf de resolubilitat forta. En aquesta tesi hem aprofitat aquesta eina i hem trobat diverses relacions entre el graf de resolubilitat forta de grafs producte i els grafs de resolubilitat forta dels seus factors. Per exemple, és notable destacar que el graf de resolubilitat forta del producte cartesià de dos grafs és isomorf al producte directe dels grafs de resolubilitat forta dels seus factors.

En esta tesis se estudia la dimensión métrica fuerte de grafos producto. Los resultados más importantes de la tesis se centran en la búsqueda de relaciones entre la dimensión métrica fuerte de grafos producto y la de sus factores, junto con otros invariantes de estos factores. Así, se han estudiado los siguientes productos de grafos: producto cartesiano, producto directo, producto fuerte, producto lexicográfico, producto corona, grafos unión, suma cartesiana, y producto raíz, de ahora en adelante "grafos producto".

Hemos obtenido fórmulas cerradas para la dimensión métrica fuerte de varias familias no triviales de grafos producto que incluyen, por ejemplo, grafos bipartitos, grafos vértices transitivos, grafos hamiltonianos, árboles, ciclos, grafos completos, etc, y hemos dado cotas inferiores y superiores generales, expresándolas en términos de invariantes de los grafos factores, como por ejemplo, el orden, el número de independencia, el número de cubrimiento de vértices, el número de emparejamiento, la conectividad algebraica, el número de cliqué, y el número de cliqué libre de gemelos. También hemos descrito algunas clases de grafos producto, donde se alcanzan estas cotas.

Es conocido que el problema de encontrar la dimensión métrica fuerte de un grafo conexo se puede transformar en el problema de encontrar el número de cubrimiento de vértices de su correspondiente grafo de resolubilidad fuerte. En esta tesis hemos aprovechado esta herramienta y hemos encontrado varias relaciones entre el grafo de resolubilidad fuerte de grafos producto y los grafos de resolubilidad fuerte de sus factores. Por ejemplo, es notable destacar que el grafo de resolubilidad fuerte del producto cartesiano de dos grafos es isomorfo al producto directo de los grafos de resolubilidad fuerte de sus factores.

In this thesis we study the strong metric dimension of product graphs. The central results of the thesis are focused on finding relationships between the strong metric dimension of product graphs and that of its factors together with other invariants of these factors. We have studied the following products: Cartesian product graphs, direct product graphs, strong product graphs, lexicographic product graphs, corona product graphs, join graphs, Cartesian sum graphs, and rooted product graphs, from now on ``product graphs''.

We have obtained closed formulaes for the strong metric dimension of several nontrivial families of product graphs involving, for instance, bipartite graphs, vertex-transitive graphs, Hamiltonian graphs, trees, cycles, complete graphs, etc., or we have given general lower and upper bounds, and have expressed these in terms of invariants of the factor graphs like, for example, order, independence number, vertex cover number, matching number, algebraic connectivity, clique number, and twin-free clique number. We have also described some classes of product graphs where these bounds are achieved.

It is known that the problem of finding the strong metric dimension of a connected graph can be transformed to the problem of finding the vertex cover number of its strong resolving graph. In the thesis we have strongly exploited this tool. We have found several relationships between the strong resolving graph of product graphs and that of its factor graphs. For instance, it is remarkable that the strong resolving graph of the Cartesian product of two graphs is isomorphic to the direct product of the strong resolving graphs of its factors.