Restrained {2}-domination in graphs

¹ Department of Mathematics Azarbaijan Shahid Madani University, Tabriz, Iran
² LAMDA-RO Laboratory, Department of Mathematics University of Blida, Blida, Algeria

^* Corresponding author: s.m.sheikholeslami@azaruniv.ac.ir; sm_sheikholeslami@yahoo.com

Received: 3 May 2023
Accepted: 8 August 2023

Abstract

A restrained {2}-dominating function (R{2}DF) on a graph G = (V, E) is a function f : V → {0, 1, 2} such that : (i) f(N[v]) ≥ 2 for all v ∈ V, where N[v] is the set containing v and all vertices adjacent to v; (ii) the subgraph induced by the vertices assigned 0 under f has no isolated vertices. The weight of an R{2}DF is the sum of its function values over all vertices, and the restrained {2}-domination number γ_r{2}(G) is the minimum weight of an R{2}DF on G. In this paper, we initiate the study of the restrained {2}-domination number. We first prove that the problem of computing this parameter is NP-complete, even when restricted to bipartite graphs. Then we give various bounds on this parameter. In particular, we establish upper and lower bounds on the restrained {2}-domination number of a tree T in terms of the order, the numbers of leaves and support vertices.