Secure w-domination in graphs

Identificador:  imarina:9138920

Handle: https://hdl.handle.net/20.500.11797/imarina9138920

Autors:  Cabrera Martinez, Abel; Estrada-Moreno, Alejandro; Rodriguez-Velazquez, Juan A

Resum:
© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This paper introduces a general approach to the idea of protection of graphs, which encompasses the known variants of secure domination and introduces new ones. Specifically, we introduce the study of secure w-domination in graphs, where w = (w0, w1, …, wl) is a vector of nonnegative integers such that w0 ≥ 1. The secure w-domination number is defined as follows. Let G be a graph and N(v) the open neighborhood of v ∈ V(G). We say that a function f: V(G) −→ {0, 1, …, l} is a w-dominating function if f (N(v)) = ∑u N(v) f (u) ≥ wi for every vertex v with f (v) = i. The weight of f is defined to be ω(f) = ∑v∈V(G) f (v). Given a w-dominating function f and any pair of adjacent vertices v, u V(G) with f (v) = 0 and f (u) > 0, the function fu→v is defined by fu→v (v) = 1, fu→v (u) = f (u) − 1 and fu→v (x) = f (x) for every x V(G) \ {u, v}. We say that a w-dominating function f is a secure w-dominating function if for every v with f (v) = 0, there exists u N(v) such that f (u) > 0 and fu→v is a w-dominating function as well. The secure w-domination number of G, denoted by γw(G),s is the minimum weight among all secure w-dominating functions. This paper provides fundamental results on γw(G)s and raises the challenge of conducting a detailed study of the topic.