Total Outer-Independent Domination Number: Bounds and Algorithms
Journal
Algorithms
ISSN
1999-4893
Date Issued
2025-03-10
Author(s)
Ernesto Parra Inza
Ismael Rios Villamar
José Luis Sánchez-Santiesteban
Type
journal-article
Abstract
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 γtoi(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 γtoi(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.
Subjects
consensus algorithm
;
graph algorithms
;
heuristic algorithms
;
integer programming
;
mixed-integer linear programming
;
network theory (graphs)
;
heuristics algorithm
;
in networks
;
independent dominating set
;
independent domination number
;
integer linear programs
;
its applications
;
network design
;
time complexity
;
total dominating sets
;
total outer-independent dominating set
;
integer linear programming
;
graph theory
;
heuristic algorithm
;
integer linear program
;
time complexity
;
total outer-independent dominating set