Please use this identifier to cite or link to this item:
http://hdl.handle.net/10609/122346
Title: | Protection of Graphs. Generic results with emphasis on Cartesian and Lexicographic product of graphs |
Author: | Valveny Juncosa, Magdalena |
Tutor: | Rodriguez Velazquez, Juan Alberto |
Abstract: | Suppose that one or more entities are stationed at some of the vertices of a graph G and that an entity at a vertex can deal with a problem at any vertex in its closed neighbourhood. Informally, we say that G is protected under a given placement of entities if there exists at least one entity available to handle a problem at any vertex. Cockayne et al. [Bulletin of the Institute of Combinatorics and its Applications 39 (2003) 87{100] proposed four properties of such functions under which the entire graph may be protected according to a certain strategy. In each case the parameter of interest will be the minimum weight of a function in the subclass (minimum number of entities used). In this work, we obtain closed formulae and tight bounds for two of these protection types: weak Roman domination number and secure domination number; focusing in lexicographic and Cartesian product graphs in terms of invariants of the factor graphs involved in the product. It is shown that the problem of computing the weak Roman domination number (Henning and Hedetniemi [Discrete Math. 266 (2003) 239-251]) and secure domination number (Boumediene Merouane and Chellali [Inform. Process. Lett. 115 (10) (2015) 786{790.]) is NP-Hard, even when restricted to bipartite or chordal graphs. This suggests nding the domination number for special classes of graphs or obtaining good bounds on this invariant. |
Keywords: | graph lexicographic product of graphs protection of graphs weak roman domination secure domination cartesian product of graphs |
Document type: | info:eu-repo/semantics/report |
Issue Date: | 13-Sep-2020 |
Publication license: | http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
Appears in Collections: | Treballs finals de carrera, treballs de recerca, etc. |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
mvalvenyTFM0920memory.pdf | Memory of TFM | 644,4 kB | Adobe PDF | View/Open |
Share:
This item is licensed under a Creative Commons License