{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T05:55:54Z","timestamp":1783058154026,"version":"3.54.6"},"reference-count":35,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T00:00:00Z","timestamp":1712880000000},"content-version":"vor","delay-in-days":42,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"CAPES","doi-asserted-by":"crossref","award":["Finance Code 01"],"award-info":[{"award-number":["Finance Code 01"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["311892\/2021-3"],"award-info":[{"award-number":["311892\/2021-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001807","name":"FAPESP","doi-asserted-by":"crossref","award":["2015\/11937-9"],"award-info":[{"award-number":["2015\/11937-9"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005283","name":"FUNCAP","doi-asserted-by":"crossref","award":["186-155.01.00\/2021"],"award-info":[{"award-number":["186-155.01.00\/2021"]}],"id":[{"id":"10.13039\/501100005283","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,2,15]]},"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:p>In a graph <jats:italic>G<\/jats:italic>, a set <jats:italic>C<\/jats:italic> \u2286 <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) is an identifying code if, for all vertices <jats:italic>v<\/jats:italic> in <jats:italic>G<\/jats:italic>, the sets <jats:italic>N<\/jats:italic>[<jats:italic>v<\/jats:italic>] \u2229 <jats:italic>C<\/jats:italic> are all nonempty and pairwise distinct, where <jats:italic>N<\/jats:italic>[<jats:italic>v<\/jats:italic>] denotes the closed neighbourhood of <jats:italic>v<\/jats:italic>. We focus on the minimum density of identifying codes of infinite hexagonal grids <jats:italic>H<jats:sub>k<\/jats:sub><\/jats:italic> with <jats:italic>k<\/jats:italic> rows, denoted by <jats:italic>d<jats:sup>*<\/jats:sup><\/jats:italic>(<jats:italic>H<jats:sub>k<\/jats:sub><\/jats:italic>), and present optimal solutions for <jats:italic>k<\/jats:italic> \u2264 5. Using the discharging method, we also prove a lower bound in terms of maximum degree for the minimum-density identifying codes of well-behaved infinite graphs. We prove that <jats:italic>d<jats:sup>*<\/jats:sup><\/jats:italic>(<jats:italic>H<\/jats:italic><jats:sub>2<\/jats:sub>) = 9\/20, <jats:italic>d<jats:sup>*<\/jats:sup><\/jats:italic>(<jats:italic>H<\/jats:italic><jats:sub>3<\/jats:sub>) = 6\/13 \u2248 0.4615, <jats:italic>d<jats:sup>*<\/jats:sup><\/jats:italic>(<jats:italic>H<\/jats:italic><jats:sub>4<\/jats:sub>) = 7\/16 = 0.4375 and <jats:italic>d<jats:sup>*<\/jats:sup><\/jats:italic>(<jats:italic>H<\/jats:italic><jats:sub>5<\/jats:sub>) = 11\/25 = 0.44. We also prove that <jats:italic>H<\/jats:italic><jats:sub>2<\/jats:sub> has a unique periodic identifying code with minimum density.<\/jats:p>","DOI":"10.1051\/ro\/2024046","type":"journal-article","created":{"date-parts":[[2024,2,17]],"date-time":"2024-02-17T19:57:10Z","timestamp":1708199830000},"page":"1633-1651","source":"Crossref","is-referenced-by-count":5,"title":["Density of identifying codes of hexagonal grids with finite number of rows"],"prefix":"10.1051","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5889-5183","authenticated-orcid":false,"given":"Rudini M.","family":"Sampaio","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2612-9032","authenticated-orcid":false,"given":"Gabriel A.G.","family":"Sobral","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8229-3139","authenticated-orcid":false,"given":"Yoshiko","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"250","published-online":{"date-parts":[[2024,4,12]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1137\/S0895480104444089","volume":"19","author":"Ben-Haim","year":"2005","journal-title":"SIAM J. Discrete Math."},{"key":"R2","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/978-3-319-41168-2_7","volume":"11","author":"Bouznif","year":"2016","journal-title":"Lecture Notes Comput. Sci."},{"key":"R3","doi-asserted-by":"crossref","first-page":"21","DOI":"10.37236\/1565","volume":"8","author":"Charon","year":"2001","journal-title":"Electron. J. Comb"},{"key":"R4","doi-asserted-by":"crossref","first-page":"25","DOI":"10.37236\/12156","volume":"9","author":"Charon","year":"2002","journal-title":"Electron. J. Comb"},{"key":"R5","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/S0012-365X(03)00306-6","volume":"276","author":"Charon","year":"2004","journal-title":"Discrete Math."},{"key":"R6","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1137\/S0895480199360990","volume":"13","author":"Cohen","year":"2000","journal-title":"SIAM J. Discrete Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1090\/dimacs\/056\/07","volume":"56","author":"Cohen","year":"2001","journal-title":"DIMACS Ser. Discrete Math. Theoret. Comput. Sci."},{"key":"R8","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1016\/j.disc.2016.11.022","volume":"340","author":"Cranston","year":"2017","journal-title":"Discrete Math."},{"key":"R9","first-page":"16","volume":"16","author":"Cranston","year":"2009","journal-title":"Electron. J. Comb"},{"key":"R10","doi-asserted-by":"crossref","first-page":"2910","DOI":"10.1016\/j.dam.2013.06.002","volume":"161","author":"Cukierman","year":"2013","journal-title":"Discrete Appl. Math."},{"key":"R11","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/j.tcs.2004.02.007","volume":"319","author":"Daniel","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"R12","doi-asserted-by":"crossref","first-page":"1584","DOI":"10.1016\/j.disc.2017.02.015","volume":"340","author":"Dantas","year":"2017","journal-title":"Discrete Math."},{"key":"R13","doi-asserted-by":"crossref","first-page":"2708","DOI":"10.1016\/j.disc.2018.06.035","volume":"341","author":"Dantas","year":"2018","journal-title":"Discrete Math."},{"key":"R14","unstructured":"Foucaud F., Combinatorial and algorithmic aspects of identifying codes in graphs. Ph.D. thesis, Universit\u00e9 Sciences et Technologies (2012)."},{"key":"R15","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1002\/net.3230230607","volume":"23","author":"Hartmann","year":"1993","journal-title":"Networks"},{"key":"R16","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s00373-003-0531-2","volume":"19","author":"Honkala","year":"2003","journal-title":"Graphs Comb."},{"key":"R17","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s00454-002-0730-2","volume":"29","author":"Honkala","year":"2003","journal-title":"Discrete Comput. Geom."},{"key":"R18","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.jctb.2003.10.002","volume":"91","author":"Honkala","year":"2004","journal-title":"J. Comb. Theory Ser. B"},{"key":"R19","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.ipl.2003.09.009","volume":"89","author":"Honkala","year":"2004","journal-title":"Inf. Process. Lett."},{"key":"R20","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/S0097539703433110","volume":"33","author":"Honkala","year":"2004","journal-title":"SIAM J. Comput."},{"key":"R21","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1006\/jctb.2001.2106","volume":"85","author":"Honkala","year":"2002","journal-title":"J. Comb. Theory Ser. B"},{"key":"R22","unstructured":"Jean D., Watching systems, identifying, locating-dominating and discriminating codes in graphs. Accessed on July 2023 https:\/\/dragazo.github.io\/bibdom\/main.pdf (2023)."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Jean D. and Seo S., Fault-tolerant locating-dominating sets with error-correction, Preprint arXiv:2212.08193v1 (2022).","DOI":"10.2139\/ssrn.4520715"},{"key":"R24","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/j.ipl.2018.03.007","volume":"135","author":"Jiang","year":"2018","journal-title":"Inf. Process. Lett."},{"key":"R25","first-page":"16","volume":"19","author":"Junnila","year":"2012","journal-title":"Electron. J. Comb"},{"key":"R26","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"Karp","year":"1978","journal-title":"Discrete Math."},{"key":"R27","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/18.661507","volume":"44","author":"Karpovsky","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"R28","first-page":"16","volume":"17","author":"Martin","year":"2010","journal-title":"Electron. J. Comb"},{"key":"R29","unstructured":"Salo V. and T\u00f6rm\u00a8a I., Finding codes on infinite grids automatically. Preprint arXiv.2303.00557 (2023)."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"Sampaio R., Sobral G. and Wakabayashi Y., Minimum density of identifying codes of hexagonal grids with a finite number of rows, in Anais do VII Encontro de Teoria da Computa\u00e7\u00e3o (Porto Alegre, RS, Brasil). SBC (2022) 145\u2013148.","DOI":"10.5753\/etc.2022.223348"},{"key":"R31","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0012-365X(01)00244-8","volume":"249","author":"Slater","year":"2002","journal-title":"Discrete Math."},{"key":"R32","unstructured":"Sobral G., Sampaio R. and Wakabayashi Y., Identifying codes. https:\/\/gitlab.uspdigital.usp.br\/gagsobral\/identifying-codes (2023)."},{"key":"R33","unstructured":"Stolee D., Automated discharging arguments for density problems in grids. Preprint arXiv.1409.5922 (2014)."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Xiao Z. and Baas B., A hexagonal processor and interconnect topology for many-core architecture with dense on-chip networks, in VLSI-SoC: From Algorithms to Circuits and System-on-Chip Design. Springer Berlin Heidelberg (2013) 125\u2013143.","DOI":"10.1007\/978-3-642-45073-0_7"},{"key":"R35","first-page":"1","volume":"10","author":"Zerovnik","year":"2008","journal-title":"Discrete Math. Theor. Comput. Sci."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024046\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T08:27:05Z","timestamp":1712910425000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024046"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":35,"journal-issue":{"issue":"2"},"alternative-id":["ro230161"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024046","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3]]}}}