{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:07Z","timestamp":1740144487452,"version":"3.37.3"},"reference-count":35,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T00:00:00Z","timestamp":1718668800000},"content-version":"vor","delay-in-days":48,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"CAPES - Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,5,2]]},"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:p>For a positive integer<jats:italic>k<\/jats:italic>, a subset<jats:italic>S<\/jats:italic>of vertices of a graph<jats:italic>G<\/jats:italic>is<jats:italic>k<\/jats:italic>-independent if each vertex in<jats:italic>S<\/jats:italic>has at most<jats:italic>k<\/jats:italic>\u2212 1 neighbors in<jats:italic>S<\/jats:italic>. We consider<jats:italic>k<\/jats:italic>-independent sets in two graph products: Cartesian and complementary prism. We show that the problem of determining<jats:italic>k<\/jats:italic>-independence remains NP-complete even for Cartesian products and complementary prisms. Furthermore, we present results on<jats:italic>k<\/jats:italic>-independence in the Cartesian product of two paths, known as grid graphs.<\/jats:p>","DOI":"10.1051\/ro\/2024098","type":"journal-article","created":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T19:12:51Z","timestamp":1715109171000},"page":"2367-2378","source":"Crossref","is-referenced-by-count":0,"title":["Complexity results on<i>k<\/i>-independence in some graph products"],"prefix":"10.1051","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1888-7802","authenticated-orcid":false,"given":"Marcia","family":"Cappelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erika","family":"Coelho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Otavio","family":"Mortosa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3002-5172","authenticated-orcid":false,"given":"Julliano","family":"Nascimento","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,6,18]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.7151\/dmgt.1527","volume":"31","author":"Abay-Asmerom","year":"2011","journal-title":"Discuss. Math. Graph Theory"},{"key":"R2","first-page":"283","volume":"137","author":"Barbosa","year":"2018","journal-title":"Ars Comb."},{"key":"R3","unstructured":"Berge C., Graphs. North Holland, Amsterdam (1985)."},{"key":"R4","doi-asserted-by":"crossref","first-page":"151","DOI":"10.7151\/dmgt.1398","volume":"28","author":"Blidia","year":"2008","journal-title":"Discuss. Math. Graph Theory"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Bondy J.A. and Murty U.S.R., Graph Theory with Applications. Macmillan, London (1976).","DOI":"10.1007\/978-1-349-03521-2"},{"key":"R6","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/S0012-365X(03)00194-8","volume":"272","author":"Bre\u0161ar","year":"2003","journal-title":"Discrete Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1142\/S0129054121500027","volume":"32","author":"Camargo","year":"2021","journal-title":"Int. J. Found. Comput. Sci."},{"key":"R8","doi-asserted-by":"crossref","first-page":"33","DOI":"10.37236\/2646","volume":"20","author":"Caro","year":"2012","journal-title":"Electron. J. Comb."},{"key":"R9","doi-asserted-by":"crossref","first-page":"265","DOI":"10.7151\/dmgt.1492","volume":"30","author":"Chellali","year":"2010","journal-title":"Discuss. Math. Graph Theory"},{"key":"R10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00373-011-1040-3","volume":"28","author":"Chellali","year":"2012","journal-title":"Graphs Combin."},{"key":"R11","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"Clark","year":"1990","journal-title":"Discrete Math."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Dehgardi N., Sheikholeslami S.M., Valinavaz M., Aram H. and Volkmann L., Domination number, independent domination number and 2-independence number in trees. Discuss. Math. Graph Theory (2021) 39\u201349.","DOI":"10.7151\/dmgt.2165"},{"key":"R13","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s10878-015-9968-5","volume":"33","author":"Duarte","year":"2017","journal-title":"J. Comb. Optim."},{"key":"R14","unstructured":"Favaron O., Graduate Course in the University of Blida (2005)."},{"key":"R15","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0012-365X(01)00236-9","volume":"249","author":"Favaron","year":"2002","journal-title":"Discrete Math."},{"key":"R16","unstructured":"Fink J.F. and Jacobson M.S., n-Domination in graphs. In: Graph Theory with Applications to Algorithms and Computer Science (1985) 283\u2013300."},{"key":"R17","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York, NY, USA (1979)."},{"key":"R18","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1137\/11082574","volume":"25","author":"Gon\u00e7alves","year":"2011","journal-title":"SIAM J. Discrete Math."},{"key":"R19","first-page":"149","volume":"43","author":"Hagauer","year":"1996","journal-title":"Ars Comb."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Hammack R.H., Imrich W., Klav\u017ear S., Imrich W. and Klav\u017ear S., Handbook of Product Graphs, Vol. 2. CRC press, Boca Raton (2011).","DOI":"10.1201\/b10959"},{"key":"R21","first-page":"21","volume":"51","author":"Haynes","year":"2007","journal-title":"Bull. Inst. Combin. Appl."},{"key":"R22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s10878-007-9135-8","volume":"18","author":"Haynes","year":"2009","journal-title":"J. Comb. Optim."},{"key":"R23","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0012-365X(92)00480-F","volume":"127","author":"Hell","year":"1994","journal-title":"Discrete Math."},{"key":"R24","first-page":"7","volume":"68","author":"Jacobson","year":"1989","journal-title":"Congr. Numer."},{"key":"R25","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0893-9659(94)90018-3","volume":"7","author":"Jha","year":"1994","journal-title":"Appl. Math. Lett."},{"key":"R26","first-page":"2","volume":"24","author":"Kogan","year":"2017","journal-title":"Electron. J. Comb."},{"key":"R27","first-page":"P1","volume":"1","author":"Mao","year":"2018","journal-title":"Art Discrete Appl. Math."},{"key":"R28","first-page":"73","volume":"60","author":"Martin","year":"2001","journal-title":"Ars Comb."},{"key":"R29","first-page":"211","volume":"48","author":"Mortosa","year":"2021","journal-title":"Math. Contemp."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"Mortosa O.S., Cappelle M.R. and Coelho E., k-independ\u00eancia em prismas complementares \u00e9 NP-completo. In: Anais do VII Encontro de Teoria da Computa\u00e7\u00e3o. SBC (2022) 133\u2013136.","DOI":"10.5753\/etc.2022.223266"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il J., Representations of graphs by means of products and their complexity. In: Mathematical Foundations of Computer Science 1981: Proceedings, 10th Symposium \u0160trbsk\u00e9 Pleso, Czechoslovakia August 31\u2013September 4, 1981 10. Springer (1981) 94\u2013102.","DOI":"10.1007\/3-540-10856-4_76"},{"key":"R32","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1155\/2023\/2601205","volume":"2023","author":"Pleanmani","year":"2023","journal-title":"J. Math."},{"key":"R33","unstructured":"Talon A. and Rao M., The 2-domination and roman domination numbers of grid graphs. Discrete Math. Theor. Comput. Sci. 21 (2019)."},{"key":"R34","first-page":"33","volume":"9","author":"Vizing","year":"1963","journal-title":"Vycisl. Sistemy"},{"key":"R35","doi-asserted-by":"crossref","first-page":"2350007","DOI":"10.1142\/S021926592350007X","volume":"24","author":"Wang","year":"2024","journal-title":"J. Interconnect. Netw."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024098\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T06:45:08Z","timestamp":1731912308000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024098"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":35,"journal-issue":{"issue":"3"},"alternative-id":["ro230110"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024098","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,5]]}}}