Unique response strong Roman dominating functions of graphs

Abstract

Given a simple graph G=(V,E) with maximum degree Δ. Let (V₀, V₁, V₂) be an ordered partition of V, where V_i = {v ∈ V : f(v)=i} for i = 0, 1 and V₂ = {v ∈ V : f(v)≥2}. A function f : V → {0, 1, …, ⌈Δ/2⌉+1} is a strong Roman dominating function (StRDF) on G, if every v ∈ V₀ has a neighbor w ∈ V₂ and f(w)≥1 + ⌈1/2|N(w)∩V₀|⌉. A function f : V → {0, 1, …, ⌈Δ/2⌉+1} is a unique response strong Roman function (URStRF), if w ∈ V₀, then |N(w)∩V₂|≤1 and w ∈ V₁ ∪ V₂ implies that |N(w)∩V₂|=0. A function f : V → {0, 1, …, ⌈Δ/2⌉+1} is a unique response strong Roman dominating function (URStRDF) if it is both URStRF and StRDF. The unique response strong Roman domination number of G, denoted by u_StR(G), is the minimum weight of a unique response strong Roman dominating function. In this paper we approach the problem of a Roman domination-type defensive strategy under multiple simultaneous attacks and begin with the study of several mathematical properties of this invariant. We obtain several bounds on such a parameter and give some realizability results for it. Moreover, for any tree T of order n ≥ 3 we prove the sharp bound u_StR(T)≤8n/9.