# Total Outer-Independent Domination Number: Bounds and Algorithms
## 2 Bounds and Exact Results for \(\gamma_{t}^{oi}(G)\)
### Bounds
As a consequence, \(G\) has a triangle, a contradiction. Hence \(\alpha(H_{1})\geq 2\) or \(\alpha(H_{2})\geq 2\), which implies that \(\alpha(G)\geq 3\), as desired. Consider a graph \(G\) with \(|V(G)|=n\), and let \(\overline{G}\) denote its complement. For every \(v\in V(G)\), we denote by \(v^{\prime}\) the vertex corresponding to \(v\) in \(\overline{G}\). The complementary prism, denote by \(G\overline{G}\), is the graph with vertex set \(V(G\overline{G})=V(G)\cup V(\overline{G})\) and edge set \(E(G\overline{G})=E(G)\cup E(\overline{G})\cup\{vv^{\prime}:\ v\in V(G)\}\). Various domination parameters have been analyzed in the context of complementary prisms. For example, in [27; 28; 29]. Figure 1 shows a graph \(G\) and \(G\overline{G}\). The set of black colored vertices describes a \(\gamma_{t}^{oi}(G\overline{G})\)-set. The following theorem provides the exact value for \(\gamma_{t}^{oi}(G\overline{G})\). For this purpose, we introduce the following family of graphs. For any integer \(k\geq 2\), let \(\mathcal{F}_{k}\) denote the family consisting of complete graphs \(K_{k}\) and graphs \(G\) of order \(k\) in which any two minimum independent sets \(D_{1}\) and \(D_{2}\) of \(G\) and \(\overline{G}\), respectively, satisfy \(|D_{1}\cap D_{2}|>0\). Please note that any two minimum independent sets \(D_{1}\) and \(D_{2}\) of \(G\) and \(\overline{G}\), respectively, satisfy \(|D_{1}\cap D_{2}|\leq 1\). **Theorem 4**. : _For any nontrivial graph \(G\) with \(n\geq 5\),_  
\[\gamma_{t}^{oi}(G\overline{G})=\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.\]  
Figure 1: Graph \(G\) and \(G\overline{G}\). **Proof. ** First, observe that \(\gamma_{t}^{oi}(K_{n}\overline{K_{n}})=n=2n-\alpha(G)-\alpha(\overline{G})+1\) and \(\gamma_{t}^{oi}(C_{5}\overline{C_{5}})=6\)\(=2n-\alpha(G)-\alpha(\overline{G})\). Therefore, from now on we suppose that \(G\
otin\{C_{5},\overline{C_{5}},K_{n},\overline{K_{n}}\}\). Now, we proceed to prove that  
\[\gamma_{t}^{oi}(G\overline{G})\geq\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.\]  
Let \(D\) be a \(\gamma_{t}^{oi}(G\overline{G})\)-set and let \(D_{1}=D\cap V(G)\) and \(D_{2}=D\cap V(\overline{G})\). Observe that \(V(G)\setminus D_{1}\) and \(V(\overline{G})\setminus D_{2}\) are independent sets of \(G\) and \(\overline{G}\), respectively. As a consequence,  
\[2n-|D_{1}|-|D_{2}|=|V(G)\setminus D_{1}|+|V(\overline{G})\setminus D_{2}| \leq\alpha(G)+\alpha(\overline{G}). \tag{1}\]  
Furthermore, if \(G\in\mathcal{F}_{n}\), then \(V(G)\setminus D_{1}\) and \(V(\overline{G})\setminus D_{2}\) cannot both be independent sets of minimum cardinality of \(G\) and \(\overline{G}\), respectively. Hence, \(|V(G)\setminus D_{1}|\leq\alpha(G)-1\) or \(|V(\overline{G})\setminus D_{2}|\leq\alpha(\overline{G})-1\). In any case, we obtain that  
\[2n-|D_{1}|-|D_{2}|=|V(G)\setminus D_{1}|+|V(\overline{G})\setminus D_{2}| \leq\alpha(G)+\alpha(\overline{G})-1. \tag{2}\]  
Using Equations (1) and (2), we derive that  
\[\gamma_{t}^{oi}(G\overline{G})=|D_{1}|+|D_{2}|\geq\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.\]  
Now we proceed to prove that  
\[\gamma_{t}^{oi}(G\overline{G})\leq\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.\]  
Let \(S_{1}\) and \(S_{2}\) be independent sets of minimum cardinality of \(G\) and \(\overline{G}\) (respectively) such that \(|S_{1}\cap S_{2}|\) is minimum. Let \(S_{1}^{\prime}=\{v^{\prime}\in V(\overline{G}):\ v\in S_{1}\}\) and let \(S_{2}^{\prime}=\{v\in V(G):\ v^{\prime}\in S_{2}\}\). We consider the set  
\[S=\left\{