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 ∑$$ 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 γ$$ (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 γ$$ (G).
Keywords: Restrained Italian dominating function, restrained Italian domination number, restrained domination number, trees, domination number, NP-hard
@article{RO_2021__55_2_319_0,
author = {Samadi, Babak and Alishahi, Morteza and Masoumi, Iman and Mojdeh, Doost Ali},
title = {Restrained {Italian} domination in graphs},
journal = {RAIRO. Operations Research},
pages = {319--332},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {2},
doi = {10.1051/ro/2021022},
mrnumber = {4234142},
zbl = {1468.05220},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021022/}
}
TY - JOUR AU - Samadi, Babak AU - Alishahi, Morteza AU - Masoumi, Iman AU - Mojdeh, Doost Ali TI - Restrained Italian domination in graphs JO - RAIRO. Operations Research PY - 2021 SP - 319 EP - 332 VL - 55 IS - 2 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021022/ DO - 10.1051/ro/2021022 LA - en ID - RO_2021__55_2_319_0 ER -
%0 Journal Article %A Samadi, Babak %A Alishahi, Morteza %A Masoumi, Iman %A Mojdeh, Doost Ali %T Restrained Italian domination in graphs %J RAIRO. Operations Research %D 2021 %P 319-332 %V 55 %N 2 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021022/ %R 10.1051/ro/2021022 %G en %F RO_2021__55_2_319_0
Samadi, Babak; Alishahi, Morteza; Masoumi, Iman; Mojdeh, Doost Ali. Restrained Italian domination in graphs. RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 319-332. doi: 10.1051/ro/2021022
[1] , , and , Roman -domination. Discrete Appl. Math. 204 (2016) 22–28. | MR | Zbl | DOI
[2] , , and , Roman domination in graphs. Discrete Math. 278 (2004) 11–22. | MR | Zbl | DOI
[3] , , , and , Restrained domination in graphs. Discrete Math. 203 (1999) 61–69. | MR | Zbl | DOI
[4] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York, USA (1979). | Zbl
[5] , and , Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). | MR
[6] and , Italian domination in trees. Discrete Appl. Math. 217 (2017) 557–564. | MR | Zbl | DOI
[7] and , On the restrained Roman domination in graphs. Manuscript (2015).
[8] and , Restrained Roman domination in graphs. Trans. Comb. 4 (2015) 1–17. | MR | Zbl
[9] and , Algorithms for vertex partitioning problems on partial -trees. SIAM J. Discrete Math. 10 (1997) 529–550. | MR | Zbl | DOI
[10] , Introduction to Graph Theory, 2nd edition. Prentice Hall, USA (2001). | MR | Zbl
Cité par Sources :
