# Total Outer-Independent Domination Number: Bounds and Algorithms
## 2 Bounds and Exact Results for \(\gamma_{t}^{oi}(G)\)
### Bounds
\begin{array}{ll}(V(G)\setminus S_{1})\cup(V(\overline{G})\setminus S _{2})&\text{ if }\,G\
otin\mathcal{F}_{n},\\ (V(G)\setminus S_{1})\cup(V(\overline{G})\setminus S_{2})\cup(S_{1}^{\prime} \cap S_{2})&\text{ if }\,G\in\mathcal{F}_{n}\text{ and }\alpha(G)=2,\\ (V(G)\setminus S_{1})\cup(V(\overline{G})\setminus S_{2})\cup(S_{1}\cap S_{2} ^{\prime})&\text{ otherwise.}\end{array} \right.\]  
We claim that \(S\) is a TOIDS of \(G\overline{G}\). Observe that \(V(G\overline{G})\setminus S\) is an independent set of \(G\overline{G}\). Therefore, we only need to prove that \(G\overline{G}[S]\) has no isolated vertex. Let \(v\in S\cap V(G)\). If \(v^{\prime}\
otin S_{2}\), then \(v\) is dominated by \(v^{\prime}\). Now suppose that \(v^{\prime}\in S_{2}\). If \(G\
otin\mathcal{F}_{n}\) or \(\alpha(\overline{G})\geq 3\), then there exists \(u^{\prime}\in S_{2}\) such that \(u^{\prime}\
eq v^{\prime}\) and \(u^{\prime}\
otin S_{1}^{\prime}\cap S_{2}\). As a consequence, \(v\) is dominated by \(u\in V(G)\setminus S_{1}\). On the other hand, suppose that \(G\in\mathcal{F}_{n}\) and \(\alpha(\overline{G})=2\). By Proposition 1 we have that \(\alpha(G)\geq 3\), which leads to \(S=(V(G)\setminus S_{1})\cup(V(\overline{G})\setminus S_{2})\cup(S_{1}\cap S_{2 }^{\prime})\). Hence, there exists \(u^{\prime}\in S_{2}\) such that \(u^{\prime}\
eq v^{\prime}\). In addition, we observe that \(u\in(V(G)\setminus S_{1})\cup(S_{1}\cap S_{2}^{\prime})\). Thus, \(v\) is dominated by \(u\), as desired. Analogously, we deduce that every \(v^{\prime}\in S\cap V(\overline{G})\) is dominated by \(S\). Therefore, \(S\) is a TOIDS of \(G\overline{G}\), which implies that  
\[\gamma_{t}^{oi}(G\overline{G})\leq|S|=\left\{ \begin{array}{ll}2n-\alpha(G)- \alpha(\overline{G})+1&\text{ if }\,G\in\mathcal{F}_{n},\\ 2n-\alpha(G)-\alpha(\overline{G})&\text{ otherwise.}\end{array} \right.\]A _split graph_ is a type of graph in which the vertex set is divided into a maximal clique \(K\) and an independent set \(I\)[30]. Proposition 2: _For any nontrivial connected split graph such that \(|K|\geq 3\), the following statements hold._  
(i): \(I\) _is a maximal independent set of_ \(G\) _if and only if_ \(\gamma_{t}^{ai}(G)=|K|\)_._  
(ii): \(I\) _is not a maximal independent set of_ \(G\) _if and only if_ \(\gamma_{t}^{ai}(G)=|K|-1\)_._  
Proof. : First, we observe that \(K\) is a TOIDS of \(G\), which implies that \(\gamma_{t}^{ai}(G)\leq|K|\). Let \(T\) be a \(\gamma_{t}^{ai}(G)\)-set such that \(T\cap K\) is maximum among all \(\gamma_{t}^{ai}(G)\)-sets. If \(K\subseteq T\), then \(\gamma_{t}^{ai}(G)=|T|\geq|K|\). If \(K\setminus T\
eq\emptyset\), then there exists \(v\in K\setminus T\). This implies that \((K\setminus\{v\})\cup N_{I}(v)\subseteq T\). It follows that  
\[|T|\geq|K\setminus\{v\}|+|N_{I}(v)|=|K|-1+|N_{I}(v)|. \tag{3}\]  
Thus,  
\[|K|-1\leq\gamma_{t}^{ai}(G)\leq|K| \tag{4}\]  
We now move on to proving (i). Suppose that \(I\) is a maximal independent set of \(G\). By Equation (4) we only need to prove that \(\gamma_{t}^{ai}(G)\geq|K|\). Since \(I\) is a maximal independent set, every \(v\in K\) satisfies \(|N_{I}(v)|\geq 1\). This fact together with (3) lead to \(\gamma_{t}^{ai}(G)=|T|\geq|K|\), as desired. Now, suppose that \(\gamma_{t}^{ai}(G)=|K|\). If \(I\) is not a maximal independent set of \(G\), then there exists \(v\in K\) such that \(N_{I}(v)=\emptyset\). As a consequence, \(K\setminus\{v\}\) is a TOIDS of \(G\). It follows that \(\gamma_{t}^{ai}(G)\leq|K|-1\), a contradiction. Therefore, \(I\) is a maximal independent set of \(G\), which completes the proof of (i). Finally, observe that (ii) is a consequence of (i) and Equation (4). If we remove the vertices \(x_{1}\) and \(x_{2}\) in the graph from Figure 2, then \(N_{I}(u_{4})=\emptyset\), and the vertex \(u_{4}\) can be removed from the \(\gamma_{t}^{ai}(G)\)-set. Then, \(\gamma_{t}^{ai}(G)=|K|-1\). A set \(S\subseteq V(G)\) is an independent dominating set of \(G\) if every vertex in \(V(G)\setminus S\) has a neighbor in \(S\), and \(S\) is an independent set.