{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:01:16Z","timestamp":1760058076897,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T00:00:00Z","timestamp":1741564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In graph theory, the study of domination sets has garnered significant interest due to its applications in network design and analysis. Consider a graph G(V,E); a subset of its vertices is a total dominating set (TDS) if, for each x\u2208V(G), there exists an edge in E(G) connecting x to at least one vertex within this subset. If the subgraph induced by the vertices outside the TDS has no edges, the set is called a total outer-independent dominating set (TOIDS). The total outer-independent domination number, denoted as \u03b3toi(G), represents the smallest cardinality of such a set. Deciding if a given graph has a TOIDS with at most r vertices is an NP-complete problem. This study introduces new lower and upper bounds for \u03b3toi(G) and presents an exact solution approach using integer linear programming (ILP). Additionally, we develop a heuristic and a procedure to efficiently obtain minimal TOIDS.<\/jats:p>","DOI":"10.3390\/a18030159","type":"journal-article","created":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T08:46:41Z","timestamp":1741596401000},"page":"159","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Total Outer-Independent Domination Number: Bounds and Algorithms"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5194-4173","authenticated-orcid":false,"given":"Paul","family":"Bosch","sequence":"first","affiliation":[{"name":"Facultad de Ingenier\u00eda, Universidad del Desarrollo, Santiago 7550000, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7901-4936","authenticated-orcid":false,"given":"Ernesto","family":"Parra Inza","sequence":"additional","affiliation":[{"name":"Centro de Investigaci\u00f3n en Ciencias, Universidad Aut\u00f3noma del Estado de Morelos, Cuernavaca 62209, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5190-7058","authenticated-orcid":false,"given":"Ismael","family":"Rios Villamar","sequence":"additional","affiliation":[{"name":"Facultad de Matem\u00e1ticas, Universidad Aut\u00f3noma de Guerrero, Chilpancingo 39070, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8128-3457","authenticated-orcid":false,"given":"Jos\u00e9 Luis","family":"S\u00e1nchez-Santiesteban","sequence":"additional","affiliation":[{"name":"Facultad de Matem\u00e1ticas, Universidad Aut\u00f3noma de Guerrero, Acapulco de Ju\u00e1rez 39650, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,3,10]]},"reference":[{"key":"ref_1","first-page":"115","article-title":"Domination in graph with application","volume":"2","author":"Gupta","year":"2013","journal-title":"Indian J. Res"},{"key":"ref_2","unstructured":"Farber, M. (1981). Applications of Linear Programming Duality to Problems Involving Independence and Domination, Simon Fraser University, Computing Science."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.disc.2007.12.044","article-title":"A survey of selected recent results on total domination in graphs","volume":"309","author":"Henning","year":"2009","journal-title":"Discret. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/comjnl\/bxy038","article-title":"On computational and combinatorial properties of the total co-independent domination number of graphs","volume":"62","author":"Yero","year":"2019","journal-title":"Comput. J."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"35544","DOI":"10.1109\/ACCESS.2018.2851972","article-title":"Computational complexity of outer-independent total and total Roman domination numbers in trees","volume":"6","author":"Li","year":"2018","journal-title":"IEEE Access"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.endm.2006.06.074","article-title":"Global offensive alliances in graphs","volume":"25","author":"Sigarreta","year":"2006","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s12044-012-0060-0","article-title":"Bounds on Gromov hyperbolicity constant in graphs","volume":"122","author":"Rodriguez","year":"2012","journal-title":"Proc.-Math. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"184","DOI":"10.55016\/ojs\/cdm.v19i3.75096","article-title":"A note on total co-independent domination in trees","volume":"19","author":"Martinez","year":"2024","journal-title":"Contrib. Discret. Math."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Henning, M. (2013). Total Domination in Graphs, Springer. Springer Monographs in Mathematics.","DOI":"10.1007\/978-1-4614-6525-6"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"301","DOI":"10.7151\/dmgt.2016","article-title":"On the total k-domination in graphs","volume":"38","author":"Bermudo","year":"2017","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Sigarreta, J.M. (2021). Total domination on some graph operators. Mathematics, 9.","DOI":"10.3390\/math9030241"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/j.crma.2010.11.021","article-title":"A lower bound on the total outer-independent domination number of a tree","volume":"349","author":"Krzywkowski","year":"2011","journal-title":"Comptes Rendus Math."},{"key":"ref_13","first-page":"6545","article-title":"Total co-independent domination in graphs","volume":"6","author":"Soner","year":"2012","journal-title":"Appl. Math. Sci"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.dam.2021.01.027","article-title":"On three outer-independent domination related parameters in graphs","volume":"294","author":"Mojdeh","year":"2021","journal-title":"Discret. Appl. Math."},{"key":"ref_15","first-page":"6581","article-title":"Total outer-independent domination in regular graphs","volume":"38","year":"2024","journal-title":"Filomat"},{"key":"ref_16","first-page":"153","article-title":"The total co-independent domination number of some graph operations","volume":"63","author":"Peterin","year":"2022","journal-title":"Rev. Uni\u00f3n Matem\u00e1tica Argent."},{"key":"ref_17","unstructured":"Parra Inza, E. (2025). Random Graph. Mendeley Data, V9."},{"key":"ref_18","first-page":"157","article-title":"Alliances in graphs","volume":"48","author":"Hedetniemi","year":"2004","journal-title":"J. Combin. Math. Combin. Comput"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2140","DOI":"10.1016\/j.disc.2006.10.026","article-title":"Powerful alliances in graphs","volume":"309","author":"Brigham","year":"2009","journal-title":"Discret. Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.akcej.2017.05.002","article-title":"Alliances in graphs: Parameters, properties and applications\u2014A survey","volume":"15","author":"Ouazine","year":"2018","journal-title":"AKCE Int. J. Graphs Comb."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.aml.2008.02.012","article-title":"Defensive k-alliances in graphs","volume":"22","author":"Yero","year":"2009","journal-title":"Appl. Math. Lett."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1311","DOI":"10.1007\/s00010-014-0324-0","article-title":"Hyperbolicity in the corona and join of graphs","volume":"89","author":"Carballosa","year":"2015","journal-title":"Aequationes Math."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Hern\u00e1ndez-G\u00f3mez, J.C., M\u00e9ndez-Berm\u00fadez, J., Rodr\u00edguez, J.M., and Sigarreta, J.M. (2018). Harmonic index and harmonic polynomial on graph operations. Symmetry, 10.","DOI":"10.3390\/sym10100456"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0012-365X(97)00228-8","article-title":"Packing in trees","volume":"186","author":"Henning","year":"1998","journal-title":"Discret. Math."},{"key":"ref_25","first-page":"173","article-title":"Perfect domination in random graphs","volume":"14","author":"Clark","year":"1993","journal-title":"J. Combin. Math. Combin. Comput"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"155","DOI":"10.2298\/AADM140210003B","article-title":"The differential and the Roman domination number of a graph","volume":"8","author":"Bermudo","year":"2014","journal-title":"Appl. Anal. Discret. Math."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s10878-007-9135-8","article-title":"Domination and total domination in complementary prisms","volume":"18","author":"Haynes","year":"2009","journal-title":"J. Comb. Optim."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Kazemi, A.P. (2011). k-Tuple Total Domination in Complementary Prisms. Int. Sch. Res. Not., 2011.","DOI":"10.5402\/2011\/681274"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"9555","DOI":"10.1002\/mma.9074","article-title":"Geometric and topological properties of the complementary prism networks","volume":"46","author":"Reyes","year":"2023","journal-title":"Math. Methods Appl. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","article-title":"Dominating sets for split and bipartite graphs","volume":"19","author":"Bertossi","year":"1984","journal-title":"Inf. Process. Lett."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1016\/j.disc.2012.11.031","article-title":"Independent domination in graphs: A survey and recent results","volume":"313","author":"Goddard","year":"2013","journal-title":"Discret. Math."},{"key":"ref_32","unstructured":"Parra Inza, E. (2025). Random Graph BD4. Mendeley Data, V1."},{"key":"ref_33","unstructured":"Parra Inza, E. (2025). Random Graph BD5. Mendeley Data, V1."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/3\/159\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:50:06Z","timestamp":1760028606000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/3\/159"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,10]]},"references-count":33,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["a18030159"],"URL":"https:\/\/doi.org\/10.3390\/a18030159","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,3,10]]}}}