On [k]-Roman domination subdivision number of graphs
| Autor: | K. Haghparast, J. Amjadi, M. Chellali, S. M. Sheikholeslami |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | AKCE International Journal of Graphs and Combinatorics, Vol 19, Iss 3, Pp 261-267 (2022) |
| Druh dokumentu: | article |
| ISSN: | 09728600 2543-3474 0972-8600 |
| DOI: | 10.1080/09728600.2022.2134836 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|