# Total Outer-Independent Domination Number: Bounds and Algorithms  
[PERSON]  
1 Facultad de Ingenierieria, Universidad del Desarrollo, Santiago 7550000, Chile; [EMAIL_ADDRESS]  
[PERSON]  
2 Cento de Investigacion en Ciencias, Universidad Autonoma del Estado de Morelos, Cuernavaca 62209, Mexico 22 Cento de Investigacion en Ciencias, Universidad Autonoma del Estado de Morelos, Cuernavaca 62209, Mexico 2  
[PERSON]  
3 Facultad de Matematicas, Universidad Autonoma de Guerrero, Chilpancingo 39070, Mexico 3  
[PERSON]  
4 Facultad de Matematicas, Universidad Autonoma de Guerrero, Acapulco de Juarez 39650, Mexico; [PERSON]## 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\in 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 \(\gamma_{t}^{oi}(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 \(\gamma_{t}^{oi}(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. graph theory; total outer-independent dominating set; integer linear program; heuristic algorithm; time complexity +
Footnote †: journal: _Algorithms_  
0000-0001-9999-4000-0001-9999-4000-00001-9999-4000-00001-9999-40000-00001-9999-40000-00001-9999-40000-00001-9999-4000001-9  
\(\delta(x)=\delta_{V(G)}(x)=|N_{V(G)}(x)|\). For ease of notation, we will often use \(N(x)\) and \(N[x]\) to refer to \(N_{V(G)}(x)\) and \(N_{V(G)}[x]\), respectively. The _maximum degree_ of \(G(V,E)\) is defined as \(\Delta(G)=\max_{x\in V(G)}\delta(x)\), and the _minimum degree_ as \(\delta(G)=\min_{x\in V(G)}\delta(x)\). Vertices \(x\in V(G)\) are _leaf vertices_ if \(|N(x)|=1\), while _support vertices_ are any vertices adjacent to leaf vertices. \(S(G)\) and \(L(G)\) denote the sets of support and leaf vertices, respectively. A set \(I\subset V(G)\) is an independent set of \(G(V,E)\) if \(G[I]\) is an edgeless graph, and \(\alpha(G)\), the independence number, is the size of the largest independent set in \(G(V,E)\)[6; 7; 8]. A nonempty set \(T\) is called a _total dominating set_ (TDS) if, for every \(x\in V(G)\), there exists an edge \((x,y)\in E(G)\) such that \(y\in T\). The _total domination number_, denoted by \(\gamma_{t}(G)\), is the smallest number of elements in any TDS of \(G(V,E)\). A TDS containing exactly \(\gamma_{t}(G)\) vertices is referred to as a \(\gamma_{t}(G)\)_-set_. Since total domination cannot be defined for graphs containing isolated vertices, all graphs considered in this paper are assumed to have no isolated vertices. Please note that by the previous definitions, \(2\leq\gamma_{t}(G)\leq n\). For additional details on total domination, refer to [3; 8; 9; 10; 11]. If \(T\) is a TDS such that the subgraph induced by \(V(G)\setminus T\) forms an independent set, then \(T\) is called a _total outer-independent dominating set_ (TOIDS). The _total outer-independent domination number_, represented as \(\gamma_{t}^{ai}(G)\), refers to the smallest cardinality of any TOIDS. A TOIDS with cardinality \(\gamma_{t}^{ai}(G)\) is called a \(\gamma_{t}^{ai}(G)\)_-set_. This concept was first presented in [12] and was briefly studied in [13], where it was referred to as the total co-independent domination number. Please note that by the previous definitions, \(\delta(G)\leq\gamma_{t}^{ai}(G)\leq n-1\), for \(n\geq 3\).