# Total Outer-Independent Domination Number: Bounds and Algorithms
## 2 Bounds and Exact Results for \(\gamma_{t}^{oi}(G)\)  
### Bounds  
A subset \(S\subseteq V(G)\) is a defensive \(k\)-alliance, with \(k\in\{-\Delta(G),\ldots,\Delta(G)\}\), if \(\delta_{S}(x)\geq\delta_{V(G)\setminus S}(x)+k\) for every \(x\in S\). The boundary of \(S\subseteq V(G)\) is the set \(\partial(S)=N(S)\setminus S\). A subset \(S\subseteq V(G)\) is a offensive \(k\)-alliance, with \(k\in\{2-\Delta(G),\ldots,\Delta(G)\}\), if \(\delta_{S}(x)\geq\delta_{V(G)\setminus S}(x)+k\) for every \(x\in\partial(S)\). A global offensive \(k\)-alliance is an offensive \(k\)-alliance \(S\) such that \(\partial(S)=V(G)\setminus S\). The global offensive \(k\)-alliance number of \(G\), represented by \(\gamma_{k}^{o}(G)\), is the smallest size of any global offensive \(k\)-alliance in the graph \(G\). A subset \(S\subseteq V(G)\) is called a powerful \(k\)-alliance if it acts as both a defensive \(k\)-alliance and an offensive \((k+2)\)-alliance. The powerful \(k\)-alliance number of \(G\), represented by \(a_{k}^{p}(G)\), is the minimum size of any powerful \(k\)-alliance in the graph \(G\). A \(a_{k}^{p}(G)\)-set is a set \(S\) of cardinality \(a_{k}^{p}(G)\) such that \(S\) is a powerful \(k\)-alliance of \(G\). Alliances in graphs have been studied extensively by many researchers. Some important results can be found in [6; 18; 19; 20; 21]. **Theorem 1**: _For any nontrivial graph \(G\) of order \(n\),_  
\[\gamma_{\delta(G)}^{o}(G)\leq\gamma_{t}^{oi}(G)\leq a_{\Delta(G)-2}^{p}(G).\]  
Proof. : We now prove the lower bound. Let \(T\) be a \(\gamma_{t}^{oi}(G)\)-set. Observe that \(N(T)=V(G)\) since \(T\) is a TDS. This fact, along with the definition of \(T\), leads to \(\partial(T)=N(T)\setminus T=V(G)\setminus T\), which is an independent set in \(G\). It follows that \(\delta_{T}(v)\geq\delta(G)=\delta_{V(G)\setminus T}(v)+\delta(G)\) for every \(v\in V(G)\setminus T\). Hence, \(T\) is a global offensive \(\delta(G)\)-alliance of \(G\). Thus, \(\gamma_{\delta(G)}^{o}(G)\leq|T|=\gamma_{t}^{oi}(G)\), as desired. Next, we establish the upper bound. Let \(S\) be a \(a_{\Delta(G)-2}^{p}\)-set. Since \(\Delta(G)\geq\delta_{S}(v)\geq\delta_{V(G)\setminus T}(v)+\Delta(G)\) for every \(v\in\partial(S)\), we deduce that \(\delta_{V(G)\setminus T}(v)=0\). Hence, \(\partial(S)\) is an independent set of \(G\). In addition, since \(G\) is a connected graph, we obtain that \(V(G)\setminus(S\cup\partial(S))=\emptyset\). Therefore, \(\partial(S)=V(G)\setminus T\) is an independent set. Finally, from the fact that \(\delta_{S}(v)\geq\delta_{V(G)\setminus T}(G)+\Delta(G)-2\) for any \(v\in S\), we deduce that \(S\) is a total dominating set of \(G\). Thus, \(S\) is a TOIDS of \(G\). Therefore, \(a_{\Delta(G)-2}^{p}(G)\geq\gamma_{t}^{oi}(G)\). The bounds in Theorem 1 are tight. For example, the lower bound is attained in complete graphs and wheel graphs. On the other hand, the upper bound is attained in complete graphs and graphs belonging to \(\mathcal{G}\), where \(\mathcal{G}\) is the family of graphs formed as follows. Let \(k\geq 2\) be an integer. \(G\in\mathcal{G}\) if is formed by a cycle \(C_{3k}\) and \(k\) vertices adjacent to only three vertices in the cycle \(C_{3k}\). Theorem 3.2: _For any nontrivial graph \(G\) of size \(m\),_  
\[\gamma_{t}^{oi}(G)\geq\max\biggl{\{}\biggl{\lceil}\frac{2m+\delta(G)}{2\Delta( G)}\biggr{\rceil},\biggl{\lceil}\frac{2m}{2\Delta(G)-1}\biggr{\rceil}\biggr{\}}.\]  
Proof. : Let \(T\) be a \(\gamma_{t}^{oi}(G)\)-set. Since \(G[V(G)\setminus T]\) is an edgeless graph and \(T\) is a TDS of \(G\), we deduce that  
\[2m =\sum_{v\in T}\delta(v)+|E(T,V(G)\setminus T)|\] \[\leq|T|\Delta(G)+|T|(\Delta(G)-1)\] \[=|T|(2\Delta(G)-1).\]  
Which implies that \(\gamma_{t}^{oi}(G)=|T|\geq 2m/(2\Delta(G)-1)\). In addition, we observe that \(|T|\geq\delta(G)\). Therefore, \(2\Delta(G)|T|\geq 2m+|T|\geq 2m+\delta(G)\). Therefore, \(\gamma_{t}^{oi}(G)=|T|\geq(2m+\delta(G))/2\Delta(G)\), as desired.