Empreu aquest identificador per citar o enllaçar aquest ítem:
http://hdl.handle.net/10609/122346
Títol: | Protection of Graphs. Generic results with emphasis on Cartesian and Lexicographic product of graphs |
Autoria: | Valveny Juncosa, Magdalena |
Tutor: | Rodriguez Velazquez, Juan Alberto |
Resum: | Suposem que una o més entitats estan estacionades en alguns dels vèrtexs d'un gràfic G i que una entitat en un vèrtex pot tractar un problema en qualsevol vèrtex del seu veïnat tancat. De manera informal, diem que G està protegit sota una ubicació determinada d'entitats si hi ha almenys una entitat disponible per gestionar un problema en qualsevol vèrtex. Cockayne et al. [Butlletí de l'Institut de Combinatòria i les seves Aplicacions 39 (2003) 87 {100] va proposar quatre propietats d'aquestes funcions en virtut de les quals es pot protegir tot el gràfic segons una determinada estratègia. En cada cas, el paràmetre d'interès serà el pes mínim d'una funció de la subclasse (nombre mínim d'entitats utilitzades). En aquest treball, obtenim fórmules tancades i límits ajustats per a dos d'aquests tipus de protecció: nombre de dominació romà feble i nombre de dominació segur; centrant-se en gràfics de productes lexicogràfics i cartesians en termes d'invariants dels gràfics de factors implicats en el producte. Es demostra que el problema de calcular el dèbil nombre de dominació romana (Henning i Hedetniemi [Discrete Math. 266 (2003) 239-251]) i el nombre de dominació segura (Boumediene Merouane i Chellali [Inform. Process. Lett. 115 (10)] (2015) 786 {790.]) És NP-Hard, fins i tot quan es limita a gràfics bipartits o acords. Això suggereix trobar el número de dominació per a classes especials de gràfics o obtenir bons límits en aquest invariant. |
Paraules clau: | gràfics protecció de gràfics feble dominació romana dominació segura producte lexicogràfic de gràfics producte cartesià de gràfics |
Tipus de document: | info:eu-repo/semantics/report |
Data de publicació: | 13-set-2020 |
Llicència de publicació: | http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
Apareix a les col·leccions: | Treballs finals de carrera, treballs de recerca, etc. |
Arxius per aquest ítem:
Arxiu | Descripció | Mida | Format | |
---|---|---|---|---|
mvalvenyTFM0920memory.pdf | Memory of TFM | 644,4 kB | Adobe PDF | Veure/Obrir |
Comparteix:
Aquest ítem està subjecte a una llicència de Creative Commons Llicència Creative Commons