Please use this identifier to cite or link to this item:
Title: Protection of Graphs. Generic results with emphasis on Cartesian and Lexicographic product of graphs
Author: Valveny Juncosa, Magdalena
Tutor: Rodríguez Velázquez, Juan Alberto
Keywords: graph
lexicographic product of graphs
protection of graphs
weak roman domination
secure domination
cartesian product of graphs
Issue Date: 13-Sep-2020
Publisher: Universitat Oberta de Catalunya (UOC)
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.
Language: English
Appears in Collections:Bachelor thesis, research projects, etc.

Files in This Item:
File Description SizeFormat 
mvalvenyTFM0920memory.pdfMemory of TFM644.4 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons