Details

Autor(en) / Beteiligte

• Valveny, Magdalena
• Pérez-Rosés, Hebert
• Rodríguez-Velázquez, Juan A.

Titel

On the weak Roman domination number of lexicographic product graphs

Ist Teil von

• Discrete Applied Mathematics, 2019-06, Vol.263, p.257-270

Ort / Verlag

Amsterdam: Elsevier B.V

Erscheinungsjahr

2019

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• A vertex v of a graph G=(V,E) is said to be undefended with respect to a function f:V⟶{0,1,2} if f(v)=0 and f(u)=0 for every vertex u adjacent to v. We call the function f a weak Roman dominating function if for every v such that f(v)=0 there exists a vertex u adjacent to v such that f(u)∈{1,2} and the function f′:V⟶{0,1,2} defined by f′(v)=1, f′(u)=f(u)−1 and f′(z)=f(z) for every z∈V∖{u,v}, has no undefended vertices. The weight of f is w(f)=∑v∈V(G)f(v). The weak Roman domination number of a graph G, denoted by γr(G), is the minimum weight among all weak Roman dominating functions on G. Henning and Hedetniemi (2003) showed that the problem of computing γr(G) is NP-Hard, even when restricted to bipartite or chordal graphs. This suggests finding γr(G) for special classes of graphs or obtaining good bounds on this invariant. In this article, we obtain closed formulae and tight bounds for the weak Roman domination number of lexicographic product graphs in terms of invariants of the factor graphs involved in the product.