# On the Outer-Independent Roman Domination in Graphs
## 2 Bounds and Relationships with Other Parameters
_There exist an_ \(\alpha(G)\)_-set_ \(S\) _and a vertex_ \(v\in S\) _such that_ \(V(G)\setminus S\subseteq N(v)\)_._  
Proof: We first suppose that (i) holds, i.e., \(\gamma_{oiR}(G)=\alpha(G)+1\). Let \(f(V_{0},V_{1},V_{2})\) be a \(\gamma_{oiR}(G)\)-function such that \(|V_{2}|\) is maximum. Hence, \(V_{2}\
eq\emptyset\). Let \(v\in V_{2}\). Since \(V_{1}\cup V_{2}\) is a vertex cover of \(G\), it follows that \(\alpha(G)+1\leq(|V_{1}|+|V_{2}|)+|V_{2}|=\gamma_{oiR}(G)=\alpha(G)+1\). Hence, we have equalities in the previous inequality chain, which implies that \(S=V_{1}\cup V_{2}\) is an \(\alpha(G)\)-set and \(V_{2}=\{v\}\). So, \(V(G)\setminus S=V_{0}\subseteq N(V_{2})=N(v)\). Therefore, (ii) follows. On the other hand, suppose that (ii) holds, i.e., suppose there exist an \(\alpha(G)\)-set \(S\) and \(v\in S\) such that \(V(G)\setminus S\subseteq N(v)\). Observe that the function \(g(W_{0},W_{1},W_{2})\), defined by \(W_{2}=\{v\}\), \(W_{1}=S\setminus\{v\}\) and \(W_{0}=V(G)\setminus S\), is an OIRDF on \(G\). Therefore, and using the lower bound given in the Theorem 1, we obtain that \(\alpha(G)+1\leq\gamma_{oiR}(G)\leq\omega(g)=|S|+1=\alpha(G)+1\). Hence, \(\gamma_{oiR}(G)=\alpha(G)+1\), which completes the proof. A tree \(T\) is an acyclic connected graph. A leaf vertex of \(T\) is a vertex of degree one. The set of leaves is denoted by \(L(T)\). We say that a vertex \(v\in V(T)\) is a support vertex (strong support vertex) if \(|N(v)\cap L(T)|\geq 1\) (\(|N(v)\cap L(T)|\geq 2\)). The set of support vertices and strong support vertices are denoted by \(S(T)\) and \(S_{s}(T)\), respectively. With this notation in mind, we next characterize the trees \(T\) with \(\gamma_{oiR}(T)=\alpha(T)+1\). Before we do this, we shall need to state the following useful lemma, in which \(diam(T)\) represents the diameter of \(T\). Lemma 1: _If \(T\) is a tree such that \(\gamma_{oiR}(T)=\alpha(T)+1\), then the following statements hold._  
1. \(diam(T)\leq 4\)_._
2. \(V(T)=L(T)\cup S(T)\)_._  
Proof: We first proceed to prove (i). By Theorem 3 there exist an \(\alpha(T)\)-set \(S\) and \(v\in S\) such that \(V(T)\setminus S\subseteq N(v)\). Now, we suppose that \(k=diam(T)\geq 5\). Let \(P=v_{0}v_{1}\cdots v_{k-1}v_{k}\) be a diametrical path of \(T\). Hence, \(\emptyset\
eq\{v_{0},v_{1},v_{k-1},v_{k}\}\cap(V(T)\setminus S)\
ot\subseteq N (v)\), which is a contradiction. Therefore, \(diam(T)\leq 4\), as desired. Finally, we proceed to prove (ii). By (i) we have that \(diam(T)\leq 4\). If \(V(T)\setminus(L(T)\cup S(T))\
eq\emptyset\), then for every \(\alpha(T)\)-set \(S\) and \(v\in S\) it follows that \(V(T)\setminus S\
ot\subseteq N(v)\), which is a contradiction with Theorem 3. Hence, \(V(T)=L(T)\cup S(T)\), which completes the proof. Let \(\mathcal{T}\) be the family of trees \(T_{r,s}\) of order \(r+s+1\) with \(r\geq 1\) and \(r-1\geq s\geq 0\), obtained from a star \(K_{1,r}\) by subdividing \(s\) edges exactly once. In Figure 2 we show the tree \(T_{5,3}\). **Theorem 4**: _Let \(T\) be a nontrivial tree. Then \(\gamma_{oiR}(T)=\alpha(T)+1\) if and only if \(T\in\mathcal{T}\)._  
If \(T\in\mathcal{T}\), then it is easy to check that \(\gamma_{oiR}(T)=\alpha(T)+1\). Now, we prove the converse. Let \(T\) be a nontrivial tree such that \(\gamma_{oiR}(T)=\alpha(T)+1\). By Lemma 1-(i) we have that \(diam(T)\leq 4\). If \(diam(T)\leq 2\), then \(T\cong T_{r,0}\in\mathcal{T}\). If \(diam(T)=3\), then \(T\cong T_{r,1}\in\mathcal{T}\). We now suppose that \(diam(T)=4\). By Lemma 1-(ii) we have that \(V(T)=L(T)\cup S(T)\). We claim that for any diametrical path \(P=v_{0}v_{1}v_{2}v_{3}v_{4}\) of \(T\), it follows that \(v_{1},v_{3}\in S(T)\setminus S_{s}(T)\). First, we observe that \(v_{1},v_{3}\in S(T)\). Without loss of generality, suppose that \(v_{1}\in S_{s}(T)\). Hence, \(v_{1}\) belongs to every \(\alpha(T)\)-set. By Theorem 3 there exist an \(\alpha(T)\)-set \(S\) and \(v\in S\) such that \(V(T)\setminus S\subseteq N(v)\). Since \(v_{0}\in V(T)\setminus S\), then \(v=v_{1}\).