# Total Outer-Independent Domination Number: Bounds and Algorithms
## 2 Bounds and Exact Results for \(\gamma_{t}^{oi}(G)\)
### Bounds
The corona product of two graphs \(G_{1}\) and \(G_{2}\), denoted as \(G_{1}\circ G_{2}\), is constructed by taking one instance of \(G_{1}\) and \(|V(G_{1})|\) replicas of \(G_{2}\), and then connecting each vertex in the \(i^{\text{th}}\) replica of \(G_{2}\) to the \(i^{\text{th}}\) vertex of \(G_{1}\) with an edge [22; 23]. The bound in Theorem 3.2 is attained in the corona product of \(C_{3}\circ N_{k}\), where \(k\) is a positive integer and \(N_{k}\) is the empty graph of \(k\) vertices. A subset \(P\subseteq V(G)\) is called a \(2\)-packing of \(G\) if \(N[x]\cap N[y]=\emptyset\) for all distinct vertices \(x,y\in P\). The \(2\)-packing number of \(G\), represented by \(\rho(G)\), is the largest size of any \(2\)-packing in \(G\). A \(\rho(G)\)-set is a \(2\)-packing of cardinality \(\rho(G)\). This parameter has been studied in [24; 25; 26]. Theorem 3.3: _For any nontrivial graph \(G\) of order \(n\),_  
\[\biggl{\lceil}\frac{\delta(G)(n+1)}{\Delta(G)+\delta(G)}\biggr{\rceil}\leq \gamma_{t}^{oi}(G)\leq n-\rho(G).\]  
Proof. : Let \(P\) be a \(\rho(G)\)-set such that \(|P\cap L(G)|\) is minimum among all \(\rho(G)\)-sets. We claim that \(V(G)\setminus P\) is a TOIDS. Since \(P\) is a packing set of \(G\), we have that \(P\) is an independent set. In addition, \(|N_{G}(v)\cap P|\leq 1\) for any \(v\in V(G)\setminus P\). Therefore, we only need to prove that \(G[V(G)\setminus P]\) has no isolated vertex. Let \(v\in V(G)\setminus P\). If \(\delta(v)\geq 2\), then we deduce that \(|N_{G}(v)\cap V(G)\setminus P|\geq 1\), as desired. Now suppose that \(\delta(v)=1\). If \(N_{G}(v)\cap P=\{u\}\), then the set \(P^{\prime}=(P\setminus\{u\})\cup\{v\}\) is a \(\rho(G)\)-set such that \(|P^{\prime}\cap L(G)|<|P\cap L(G)|\), a contradiction. Hence, \(|N_{G}(v)\cap V(G)\setminus P|=1\), as desired. Therefore, \(\gamma_{t}^{oi}(G)\leq|V(G)\setminus P|=n-|P|=n-\rho(G)\). Next, we establish the upper bound. Observe that  
\[\delta(G)(n-|P|)\leq|E(P,V(G)\setminus P)|\leq|P|(\Delta(G)-1).\]  
From this inequality and the fact that \(|P|\geq\delta(G)\) we deduce that \(|P|(\Delta(G)+\delta(G))\geq n\delta(G)+|P|\geq n\delta(G)+\delta(G)=\delta(G) (n+1)\). It follows that \(\gamma_{t}^{oi}(G)=|P|\geq\delta(G)\)\((n+1)/(\Delta(G)+\delta(G))\). The bounds in Theorem 3 are tight. For example, the upper bound is attained in the double-star graphs. In addition, the lower bound is attained in the corona product of \(C_{3}\circ N_{r}\), where \(r\) is a positive integer and \(N_{r}\) is the empty graph of \(r\) vertices. **Proposition 1**. : _Let \(G\) be a nontrivial graph of order \(n\geq 5\). If \(G\) is a triangle-free graph that is different from \(C_{5}\), then \(\alpha(G)\geq 3\)._  
Proof. : We consider two cases. _Case 1._\(G\) is a graph with a connected structure. Suppose that \(G\) is a tree. If \(|L(G)|=2\), then \(G=P_{n}\). Hence, \(\alpha(G)\geq 3\). If \(|L(G)|\geq 3\), then \(\alpha(G)\geq|L(G)|\geq 3\), as desired. From now on, suppose that \(G\) has a cycle of minimum length \(C=c_{1}c_{2}\cdots c_{k}c_{1}\). If \(k\geq 6\), then \(\{v_{1},v_{3},v_{5}\}\) is an independent set. Thus, \(\alpha(G)\geq 3\). Now, suppose \(k\in\{4,5\}\). Since \(n\geq 5\) and \(G\
eq C_{5}\), it follows that \(V(G)\setminus V(C)\
eq\emptyset\). In addition, by minimality of \(C\) and since \(G\) is triangle-free, there exists \(v\
otin V(C)\) such that \(v\) is adjacent to at most two nonadjacent vertices of \(V(C)\). We assume that \(N(v)\cap V(C)=\{v_{1},v_{3}\}\) without loss of generality. The set \(\{v,v_{2},v_{4}\}\) is an independent set of \(G\). Thus, we obtain that \(\alpha(G)\geq 3\), as desired. _Case 2._\(G\) is a disconnected graph. If it consists of more than two connected components, then it is evident that \(\alpha(G)\geq 3\). Therefore, suppose that \(G\) has two connected components, \(H_{1}\) and \(H_{2}\). If \(\alpha(H_{1})=\alpha(H_{2})=1\), then \(H_{1}\) and \(H_{2}\) are complete graphs. Since \(n\geq 5\), we deduce that \(|V(H_{1})|\geq 3\) or \(|V(H_{2})|\geq 3\).