On [k]-Roman domination subdivision number of graphs. Issue 3 (2nd September 2022)

• Record Type: Journal Article
• Authors: Haghparast, K.; Amjadi, J.; Chellali, M.; Sheikholeslami, S. M.
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 19:Issue 3(2022)
• Page Start: 261
• Page End: 267
• Publication Date: 2022-09-02
• Subjects: [k]-Roman domination number -- [k]-Roman domination subdivision number; 05C69
• DOI: 10.1080/09728600.2022.2134836
• Languages: English
• ISSNs: 0972-8600

Abstract

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.