Propostes PFC - DEIM
[ Inici | Properes Lectures ]
Professor/a Juan A. Rodríguez-Velázquez ( MAT )
Títol Protecció de grafs: dominació romana feble en grafs producte lexicogràfic graphs
Tema
Descripció Un vèrtex v d'un graf G=(V,E) es considera que no està defensat respecte a una funció f: V --> {0,1,2} si f(v)=0 i f(u)=0 per tots els vèrtexs u adjacents a v. Anomenem a la funció f una funció romana feble si per cada v tal que f(v)=0 existeix un vèrtex u adjacent a v tal que f(u) en {1,2} i la funció f': V--> {0,1,2} definida per f'(v)=1, f'(u)=f(u)-1 i f'(z)=f(z) per tots els vèrtexs zin V {u,v}, no té vèrtexs no defensats. El pes de f és w(f)=sum_{vin V(G)}f(v).
El nombre de dominació romana feble d'un graf G, denotat per gamma_r(G), és el mínim pes entre totes les funcions romanes febles sobre G. Henning i Hedetniemi [Discrete Math. 266 (2003) 239-251] van demostrar que el problema de calcular gamma_r(G) és NP-Hard, fins i tot quan es restringeix a grafs bipartits o cordals. Això suggereix trobar fórmules per gamma_r(G) per a classes de grafs en especial o obtenir cotes ajustades en aquest invariant.
En aquest treball, s'obtenen fórmules tancades i fites tenses per al nombre de dominació romana feble en el producte lexicogràfic de grafs en termes d'invariants dels grafs involucrats en el producte.
A més, amb l'objectiu de comprovar com d'ajustades són algunes fites, hem desenvolupat un programa capaç de calcular el nombre de dominació romana feble per grafs petits.
Aquest treball ha estat acceptat per ser publicat a la revista Discrete Applied Mathematics.
Materies Algorísmica - Programació - Matemàtica discreta.
Coneixements Assignatures: Matemàtica Discreta I, Programació, Estructures de dades.
Teoria de grafs i programació
Tecnologia
Ensenyament GEI
Dificultat Molt alta
Assignat a MAGDALENA VALVENY JUNCOSA
Documentació 1. Memòria (.pdf). Memòria
 
Projecte finalitzat i defensat !!