UP - logo
E-resources
Full text
Peer reviewed Open access
  • Restrained {2}-domination i...
    Haghparast, Kazhal; Amjadi, Jafar; Chellali, Mustapha; Sheikholeslami, Seyed Mahmoud

    R.A.I.R.O. Recherche opérationnelle, 09/2023, Volume: 57, Issue: 5
    Journal Article

    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.