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

  1. Estrada Moreno, Alejandro
unter der Leitung von:
  1. Ismael González Yero Doktorvater/Doktormutter
  2. Juan Alberto Rodríguez Velázquez Doktorvater/Doktormutter

Universität der Verteidigung: Universitat Rovira i Virgili

Fecha de defensa: 29 von März von 2016

Gericht:
  1. Sergio Bermudo Navarrete Präsident
  2. Carlos Luis García Gómez Sekretär/in
  3. Juan Carlos Valenzuela Tripodoro Vocal

Art: Dissertation

Teseo: 413613 DIALNET lock_openTDX editor

Zusammenfassung

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.