Protection of Graphs. Generic results with emphasis on Cartesian and Lexicographic product of graphs

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.

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.

Suponga que una o más entidades están ubicadas en algunos de los vértices de un gráfico G y que una entidad en un vértice puede resolver un problema en cualquier vértice en su vecindad cerrada. De manera informal, decimos que G está protegido bajo una ubicación determinada de entidades si existe al menos una entidad disponible para manejar un problema en cualquier vértice. Cockayne y col. [Boletín del Instituto de Combinatoria y sus Aplicaciones 39 (2003) 87 {100] propuso cuatro propiedades de tales funciones bajo las cuales todo el gráfico puede protegerse de acuerdo con una determinada estrategia. En cada caso, el parámetro de interés será el peso mínimo de una función en la subclase (número mínimo de entidades utilizadas). En este trabajo, obtenemos fórmulas cerradas y límites estrechos para dos de estos tipos de protección: número de dominación romana débil y número de dominación segura; centrándose en gráficos de productos lexicográficos y cartesianos en términos de invariantes de los gráficos de factores involucrados en el producto. Se muestra que el problema de calcular el número de dominación romana débil (Henning y Hedetniemi [Discrete Math. 266 (2003) 239-251]) y el número de dominación segura (Boumediene Merouane y Chellali [Inform. Process. Lett. 115 (10)) (2015) 786 {790.]) Es NP-Hard, incluso cuando se restringe a gráficos bipartitos o cordales. Esto sugiere encontrar el número de dominación para clases especiales de gráficos u obtener buenos límites en este invariante.