Restrained Italian reinforcement number in graphs

AbstractA restrained Italian dominating function (RID-function) on a graph [Formula: see text] is a function [Formula: see text] satisfying: (i) [Formula: see text] for every vertex [Formula: see text] with [Formula: see text], where [Formula: see text] is the set of vertices adjacent to u; (ii) the...

Full description

Saved in:
Bibliographic Details
Published in:AKCE international journal of graphs and combinatorics 2023-09, Vol.20 (3), p.227-234
Main Authors: Ebrahimi, N., Amjadi, J., Chellali, M., Sheikholeslami, S. M.
Format: Article
Language:English
Subjects:
NP-hardness
Restrained Italian domination
restrained Italian reinforcement
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:AbstractA restrained Italian dominating function (RID-function) on a graph [Formula: see text] is a function [Formula: see text] satisfying: (i) [Formula: see text] for every vertex [Formula: see text] with [Formula: see text], where [Formula: see text] is the set of vertices adjacent to u; (ii) the subgraph induced by the vertices assigned 0 under f has no isolated vertices. The weight of an RID-function is the sum of its function value over the whole set of vertices, and the restrained Italian domination number is the minimum weight of an RID-function on G. In this paper, we initiate the study of the restrained Italian reinforcement number [Formula: see text] of a graph G defined as the cardinality of a smallest set of edges that we must add to the graph to decrease its restrained Italian domination number. We begin by showing that the decision problem associated with the restrained Italian reinforcement problem is NP-hard for arbitrary graphs. Then several properties as well as some sharp bounds of the restrained Italian reinforcement number are presented.
ISSN:0972-8600
2543-3474
DOI:10.1080/09728600.2023.2218438