2024 : 6 : 20
Doost Ali Mojdeh

Doost Ali Mojdeh

Academic rank: Professor
Education: PhD.
Faculty: Faculty of Mathematical Sciences
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Phone: 011-35302448


Restrained Italian domination in graphs
Restrained Italian dominating function, restrained Italian domination number, restrained domination number, trees, domination number, NP-hard.
Researchers Babak Samadi ، Morteza Alishahi ، Iman Masoumi ، Doost Ali Mojdeh


For a graph G = (V(G), E(G)), an Italian dominating function (ID function) f : V(G) → {0,1,2} has the property that for every vertex v ∈ V(G) with f(v) = 0, either v is adjacent to a vertex assigned 2 under f or v is adjacent to least two vertices assigned 1 under f. The weight of an ID function is ∑v∈V(G) f(v). The Italian domination number is the minimum weight taken over all ID functions of G. In this paper, we initiate the study of a variant of ID functions. A restrained Italian dominating function (RID function) f of G is an ID function of G for which the subgraph induced by {v ∈ V(G) | f(v) = 0} has no isolated vertices, and the restrained Italian domination number γrI (G) is the minimum weight taken over all RID functions of G. We first prove that the problem of computing this parameter is NP-hard, even when restricted to bipartite graphs and chordal graphs as well as planar graphs with maximum degree five. We prove that γrI(T) for a tree T of order n ≥ 3 different from the double star S2,2 can be bounded from below by (n + 3)/2. Moreover, all extremal trees for this lower bound are characterized in this paper. We also give some sharp bounds on this parameter for general graphs and give the characterizations of graphs G with small or large γrI (G).