{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T01:54:49Z","timestamp":1774662889239,"version":"3.50.1"},"reference-count":27,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2022,2,7]],"date-time":"2022-02-07T00:00:00Z","timestamp":1644192000000},"content-version":"vor","delay-in-days":37,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["001"],"award-info":[{"award-number":["001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2022,1,4]]},"published-print":{"date-parts":[[2022]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic> be a finite, simple, and undirected graph and let <jats:italic>S<\/jats:italic> \u2286 <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>). In the geodetic convexity, <jats:italic>S<\/jats:italic> is <jats:italic>convex<\/jats:italic> if all vertices belonging to any shortest path between two vertices of <jats:italic>S<\/jats:italic> lie in <jats:italic>S<\/jats:italic>. The <jats:italic>convex hull H<\/jats:italic>(<jats:italic>S<\/jats:italic>) of <jats:italic>S<\/jats:italic> is the smallest convex set containing <jats:italic>S<\/jats:italic>. The <jats:italic>hull number h<\/jats:italic>(<jats:italic>G<\/jats:italic>) is the minimum cardinality of a set <jats:italic>S<\/jats:italic> \u2286 <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) such that <jats:italic>H<\/jats:italic>(<jats:italic>S<\/jats:italic>) = <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>). The <jats:italic>complementary prism<\/jats:italic> <jats:italic>G<\/jats:italic><jats:italic>G\u0305<\/jats:italic> of a graph <jats:italic>G<\/jats:italic> arises from the disjoint union of the graph <jats:italic>G<\/jats:italic> and <jats:italic>G\u0305<\/jats:italic> by adding the edges of a perfect matching between the corresponding vertices of <jats:italic>G<\/jats:italic> and <jats:italic>G\u0305<\/jats:italic>. Previous works have determined <jats:italic>h<\/jats:italic>(<jats:italic>G<\/jats:italic><jats:italic>G\u0305<\/jats:italic>) when both <jats:italic>G<\/jats:italic> and <jats:italic>G\u0305<\/jats:italic> are connected and partially when <jats:italic>G<\/jats:italic> is disconnected. In this paper, we characterize convex sets in <jats:italic>G<\/jats:italic><jats:italic>G\u0305<\/jats:italic> and we present equalities and tight lower and upper bounds for <jats:italic>h<\/jats:italic>(<jats:italic>G<\/jats:italic><jats:italic>G\u0305<\/jats:italic>). This fills a gap in the literature and allows us to show that <jats:italic>h<\/jats:italic>(<jats:italic>G<\/jats:italic><jats:italic>G\u0305<\/jats:italic>) can be determined in polynomial time, for any graph <jats:italic>G<\/jats:italic>.<\/jats:p>","DOI":"10.1051\/ita\/2022001","type":"journal-article","created":{"date-parts":[[2022,2,7]],"date-time":"2022-02-07T09:09:12Z","timestamp":1644224952000},"page":"1","source":"Crossref","is-referenced-by-count":2,"title":["A polynomial time algorithm for geodetic hull number for complementary prisms"],"prefix":"10.1051","volume":"56","author":[{"given":"Erika M.M.","family":"Coelho","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hebert","family":"Coelho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3002-5172","authenticated-orcid":false,"given":"Julliano R.","family":"Nascimento","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayme L.","family":"Szwarcfiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2022,2,7]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1155\/S016117127900020X","volume":"2","author":"Akiyama","year":"1979","journal-title":"Int. J. Math. Math. Sci"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Albenque M. and \nKnauer K., Convexity in partial cubes: the hull number, in \nLATIN 2014: Theoretical Informatics. \nSpringer \n(2014) 421\u2013432.","DOI":"10.1007\/978-3-642-54423-1_37"},{"key":"R3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2012.12.035","volume":"475","author":"Araujo","year":"2013","journal-title":"Theor. Comput. Sci"},{"key":"R4","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.dam.2015.03.019","volume":"210","author":"Araujo","year":"2016","journal-title":"Discr. Appl. Math"},{"key":"R5","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1137\/17M1131726","volume":"32","author":"Bessy","year":"2018","journal-title":"SIAM J. Discr. Math"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s B., \nThe Art of Mathematics: Coffee Time in Memphis. \nCambridge University Press \n(2006).","DOI":"10.1017\/CBO9780511816574"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Camargo P.P., \nSouza U.S. and \nNascimento J.R., \nRemarks on k-clique, k-independent set and 2-contamination in complementary prisms. \nInt. J. Found. Comput. Sci. \n(2021) 1\u201316.","DOI":"10.1142\/S0129054121500027"},{"key":"R8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2013.11.006","volume":"521","author":"Cappelle","year":"2014","journal-title":"Theor. Comput. Sci"},{"key":"R9","doi-asserted-by":"crossref","first-page":"S2403","DOI":"10.1051\/ro\/2020089","volume":"55","author":"Castonguay","year":"2021","journal-title":"RAIRO-Oper. Res"},{"key":"R10","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1002\/jgt.3190110405","volume":"11","author":"Chv\u00e1tal","year":"1987","journal-title":"J. Graph Theory"},{"key":"R11","unstructured":"Coelho E.M.M., \nCoelho H., \nNascimento J.R. and \nSzwarcfiter J.L., \nOn the geodetic hull number of complementary prisms. \nPreprint arXiv:1807.08295 \n(2018)."},{"key":"R12","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.dam.2018.04.024","volume":"253","author":"Coelho","year":"2019","journal-title":"Discr. Appl. Math"},{"key":"R13","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"Corneil","year":"1981","journal-title":"Discr. Appl. Math"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Domingos P. and \nRichardson M., Mining the network value of customers. In \nProceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201901. \nACM, \nNew York, NY, USA \n(2001) 57\u201366.","DOI":"10.1145\/502512.502525"},{"key":"R15","doi-asserted-by":"crossref","first-page":"5668","DOI":"10.1016\/j.disc.2008.04.020","volume":"309","author":"Dourado","year":"2009","journal-title":"Discr. Math"},{"key":"R16","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.tcs.2016.05.047","volume":"640","author":"Dourado","year":"2016","journal-title":"Theor. Comp. Sci"},{"key":"R17","doi-asserted-by":"crossref","first-page":"1615","DOI":"10.1016\/j.dam.2008.09.012","volume":"157","author":"Dreyer","year":"2009","journal-title":"Discr. Appl. Math"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Duarte M.A., \nPenso L., \nRautenbach D. and \ndos Santos Souza U., \nComplexity properties of complementary prisms. \nJ. Combinat. Optim. \n(2015) 1\u20138.","DOI":"10.1007\/s10878-015-9968-5"},{"key":"R19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0012-365X(85)90174-8","volume":"57","author":"Everett","year":"1985","journal-title":"Discr. Math"},{"key":"R20","unstructured":"Farrugia A., \nSelf-complementary graphs and generalisations: a comprehensive reference manual. \nUniversity of Malta \n(1999)."},{"key":"R21","unstructured":"Foldes S. and \nHammer P.L., Split graphs, in \nProceedings 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, \nLouisiana State University, \nBaton Rouge, LA \n(1977) 311\u2013315."},{"key":"R22","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"Hammer","year":"1981","journal-title":"Combinatorica"},{"key":"R23","first-page":"21","volume":"51","author":"Haynes","year":"2007","journal-title":"Bull. Inst. Combinator. Appl."},{"key":"R24","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1137\/15M1013389","volume":"30","author":"Kant\u00e9","year":"2016","journal-title":"SIAM J. Discr. Math"},{"key":"R25","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s00373-011-1028-z","volume":"28","author":"Karami","year":"2012","journal-title":"Graphs Combinator"},{"key":"R26","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0304-3975(01)00055-X","volume":"282","author":"Peleg","year":"2002","journal-title":"Theor. Comput. Sci"},{"key":"R27","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0012-365X(87)90142-7","volume":"65","author":"Xu","year":"1987","journal-title":"Discr. Math"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2022001\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,7]],"date-time":"2022-02-07T09:09:31Z","timestamp":1644224971000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2022001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":27,"alternative-id":["ita210034"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2022001","relation":{},"ISSN":["0988-3754","2804-7346"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"2804-7346","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]}}}