AKCE International Journal of Graphs and Combinatorics (Sep 2022)

On [k]-Roman domination subdivision number of graphs

  • K. Haghparast,
  • J. Amjadi,
  • M. Chellali,
  • S. M. Sheikholeslami

DOI
https://doi.org/10.1080/09728600.2022.2134836
Journal volume & issue
Vol. 19, no. 3
pp. 261 – 267

Abstract

Read online

AbstractLet [Formula: see text] be an integer and G a simple graph with vertex set V(G). Let f be a function that assigns labels from the set [Formula: see text] to the vertices of G. For a vertex [Formula: see text] the active neighbourhood AN(v) of v is the set of all vertices w adjacent to v such that [Formula: see text] A [k]-Roman dominating function (or [k]-RDF for short) is a function [Formula: see text] satisfying the condition that for any vertex [Formula: see text] with f(v) < k, [Formula: see text] The weight of a [k]-RDF is [Formula: see text] and the [k]-Roman domination number [Formula: see text] 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[Formula: see text] 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[Formula: see text] is NP-hard. Then various properties and bounds are established.

Keywords