On [k]-Roman domination subdivision number of graphs. Issue 3 (2nd September 2022) - Haghparast, K.; Amjadi, J.; Chellali, M.; Sheikholeslami, S. M.
Abstract: Let k ≥ 1 be an integer and G a simple graph with vertex set V ( G ). Let f be a function that assigns labels from the set { 0, 1, 2, …, k + 1 } to the vertices of G . For a vertex v ∈ V ( G ), the active neighbourhood AN ( v ) of v is the set of all vertices w adjacent to v such that f ( w ) ≥ 1 . A [ k ]-Roman dominating function (or [ k ]-RDF for short) is a function f : V ( G ) → { 0, 1, 2, …, k + 1 } satisfying the condition that for any vertex v ∈ V ( G ) with f ( v ) < k, f ( N [ v ] ) ≥ | A N ( v ) | + k . The weight of a [ k ]-RDF is ω ( f ) = Σ v ∈ V ( G ) f ( v ), and the [ k ]-Roman domination number γ [ k R ] ( G ) of G is the minimum weight of an [ k ]-RDF on G . In this paper we shall be interested in the study of the [ k ]-Roman domination subdivision number sd γ [ k R ] ( G ) of G defined as the minimum number of edges that must be subdivided, each once, in order to increase the [ k ]-Roman domination number. We first show that the decision problem associated with sd γ [ k R ] ( G ) is NP-hard. Then various properties and bounds are established.