{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:27:48Z","timestamp":1740144468626,"version":"3.37.3"},"reference-count":19,"publisher":"EDP Sciences","issue":"5","license":[{"start":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T00:00:00Z","timestamp":1695081600000},"content-version":"vor","delay-in-days":18,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,8,8]]},"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:p>A restrained {2}-dominating function (R{2}DF) on a graph <jats:italic>G<\/jats:italic> = (<jats:italic>V<\/jats:italic>,\u00a0<jats:italic>E<\/jats:italic>) is a function <jats:italic>f<\/jats:italic>\u00a0:\u00a0<jats:italic>V<\/jats:italic>\u00a0\u2192\u00a0{0,\u00a01,\u00a02} such that : (i) <jats:italic>f<\/jats:italic>(<jats:italic>N<\/jats:italic>[<jats:italic>v<\/jats:italic>])\u00a0\u2265\u00a02 for all <jats:italic>v<\/jats:italic>\u00a0\u2208\u00a0<jats:italic>V<\/jats:italic>, where <jats:italic>N<\/jats:italic>[<jats:italic>v<\/jats:italic>] is the set containing <jats:italic>v<\/jats:italic> and all vertices adjacent to <jats:italic>v<\/jats:italic>; (ii) the subgraph induced by the vertices assigned 0 under <jats:italic>f<\/jats:italic> 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 <jats:italic>\u03b3<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic><\/jats:sub>{2}(<jats:italic>G<\/jats:italic>) is the minimum weight of an R{2}DF on <jats:italic>G<\/jats:italic>. 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 <jats:italic>T<\/jats:italic> in terms of the order, the numbers of leaves and support vertices.<\/jats:p>","DOI":"10.1051\/ro\/2023120","type":"journal-article","created":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T18:58:56Z","timestamp":1691607536000},"page":"2393-2410","source":"Crossref","is-referenced-by-count":0,"title":["Restrained {2}-domination in graphs"],"prefix":"10.1051","volume":"57","author":[{"given":"Kazhal","family":"Haghparast","sequence":"first","affiliation":[]},{"given":"Jafar","family":"Amjadi","sequence":"additional","affiliation":[]},{"given":"Mustapha","family":"Chellali","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2298-4744","authenticated-orcid":false,"given":"Seyed Mahmoud","family":"Sheikholeslami","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2023,9,19]]},"reference":[{"key":"R1","first-page":"75","volume":"1","author":"Abdollahzadeh Ahangar","year":"2016","journal-title":"Commun. Comb. Optim."},{"key":"R2","first-page":"575","volume":"8","author":"Amjadi","year":"2023","journal-title":"Commun. Comb. Optim."},{"key":"R3","doi-asserted-by":"crossref","first-page":"10731","DOI":"10.3934\/math.2022599","volume":"7","author":"Cabrera-Mart\u00ednez","year":"2022","journal-title":"AIMS Math."},{"key":"R4","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.dam.2017.08.017","volume":"235","author":"Bonomo","year":"2018","journal-title":"Discrete Appl. Math."},{"key":"R5","doi-asserted-by":"crossref","first-page":"2892","DOI":"10.1016\/j.camwa.2011.07.059","volume":"62","author":"Chen","year":"2011","journal-title":"Comput. Math. Appl."},{"key":"R6","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0012-365X(99)00016-3","volume":"203","author":"Domke","year":"1999","journal-title":"Discrete Math."},{"key":"R7","unstructured":"Domke G.S., Hedetniemi S.T., Laskar R.C. and Fricke G.H., Relationships between Integer and Fractional Parameters of Graphs, In Vol. 2 of Graph theory, combinatorics, and applications: proceedings of the sixth quadrennial international conference on the theory and applications of graphs. Western Michigan University, John Wiley and Sons Inc. (1991) 371\u2013387."},{"key":"R8","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completness, Freeman, San Francisco (1979)."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Hattingh J.H. and Joubert E.J., Restrained and total restrained domination in graphs, edited by Haynes T.W., Hedetniemi S.T. and Henning M.A.. In: Topics in domination in graphs. Springer International Publishing (2020).","DOI":"10.1007\/978-3-030-51117-3_5"},{"key":"R10","first-page":"201","volume":"55","author":"Harary","year":"2000","journal-title":"Ars Combin."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Haynes T.W., Hedetniemi S.T. and Slater P.J., Fundamental of Domination in Graphs. Marcel Deker, New York (1998).","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F"},{"key":"R12","unstructured":"Haynes T.W., Hedetniemi S.T. and Slater P.J., Domination in Graphs: Advanced Topics. Marcel Dekker Inc., New York (1998)."},{"key":"R13","first-page":"73","volume":"5","author":"Kala","year":"2008","journal-title":"J Graphs Comb."},{"key":"R14","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1051\/ro\/2021022","volume":"55","author":"Samadi","year":"2021","journal-title":"RAIRO: OR"},{"key":"R15","first-page":"127554","volume":"438","author":"Samadi","year":"2023","journal-title":"Appl. Math. Comput."},{"key":"R16","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"Telle","year":"1997","journal-title":"SIAM J. Discrete Math."},{"key":"R17","first-page":"183","volume":"8","author":"Volkmann","year":"2023","journal-title":"Commun. Comb. Optim."},{"key":"R18","first-page":"1","volume":"8","author":"Volkmann","year":"2023","journal-title":"Commun. Comb. Optim."},{"key":"R19","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/s40840-022-01408-8","volume":"46","author":"Xi","year":"2023","journal-title":"Bull. Malays. Math. Sci. Soc."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023120\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T08:20:20Z","timestamp":1695111620000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9]]},"references-count":19,"journal-issue":{"issue":"5"},"alternative-id":["ro230312"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023120","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2023,9]]}}}