DSpace Repository :: Browsing by Author "Parra Inza, Ernesto"

Now showing 1 - 1 of 1

Total Outer-Independent Domination Number: Bounds and Algorithms
(2025) Bosch, Paul; Parra Inza, Ernesto; Rios Villamar, Ismael; Sánchez-Santiesteban, José Luis
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 ∈ V(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 γoit (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 lowerand upper bounds for γoit (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.