## 4 Identifying Subproblem Solutions and Defining the Recursive Formulas
**Case 3:**\(p+(\ell-1)\cdot d<\max\{x,y\}\). Then, \(f(v)>p+(\ell-1)\cdot d\). This contradicts the requirement that \(f(v)\in\{p,p+d,\ldots,p+(\ell-1)\cdot d\}\). Consequently, \(\tau^{d,\ell}_{p,1}(x,y)(G_{\alpha})=\infty\). **Lemma 7**. : _Suppose that \(G\) is a distance-hereditary graph and \(G_{\alpha}=G_{\alpha_{1}}\bigodot G_{\alpha_{2}}\) is an induced subgraph of \(G\) formed from two disjoint distance-hereditary graphs \(G_{\alpha_{1}}\) and \(G_{\alpha_{2}}\). Let \(p\in\{0,-1\}\), and let \(d,\ell,x,y,z\) be integers such that \(d,\ell\in\mathbb{Z}^{+}\) are fixed, and \(p\cdot\omega(G)\leq x,y,z\leq(p+(\ell-1)\cdot d)\cdot\omega(G)\). Then, \(\tau^{d,\ell}_{p,0}(x,y)(G_{\alpha})\), \(\tau^{d,\ell}_{p,1}(x,y)(G_{\alpha})\), and \(\tau^{d,\ell}_{p,2}(x,y,z)(G_{\alpha})\) can be computed as follows:_  
1. _Assume that_ \(C_{T}(G_{\alpha})=\emptyset\) _and_ \(C_{\overline{T}}(G_{\alpha})\
eq\emptyset\)_;_ 1. \(\tau^{d,\ell}_{p,1}(x,y)(G_{\alpha})=\infty\)_;_ 1. \(\tau^{d,\ell}_{p,2}(x,y,z)(G_{\alpha})=\infty\)_;_ 1. \(\tau^{d,\ell}_{p,0}(x,y)(G_{\alpha})=\tau^{d,\ell}_{p,0}(x,y)(G_{\alpha_{1}})+ \tau^{d,\ell}_{p,0}(x,y)(G_{\alpha_{2}})\)_._
2. _Assume that_ \(C_{T}(G_{\alpha})\
eq\emptyset\) _and_ \(C_{\overline{T}}(G_{\alpha})=\emptyset\)_;_ 2. \(\tau^{d,\ell}_{p,0}(x,y)(G_{\alpha})=\infty\)_;_ 2. \(\tau^{d,\ell}_{p,2}(x,y,z)(G_{\alpha})=\infty\)_;_ 3. _Let_ \(w=\max\{x,y\}\)_. Then,_ \(\tau^{d,\ell}_{p,1}(x,y)(G_{\alpha})=\tau^{d,\ell}_{p,1}(w,w)(G_{\alpha_{1}})+ \tau^{d,\ell}_{p,1}(w,w)(G_{\alpha_{2}})\)_._
3. _Assume that_ \(C_{T}(G_{\alpha})\
eq\emptyset\) _and_ \(C_{\overline{T}}(G_{\alpha})\
eq\emptyset\)_;_ 3. \(\tau^{d,\ell}_{p,0}(x,y)(G_{\alpha})=\infty\)_;_ 3. \(\tau^{d,\ell}_{p,1}(x,y)(G_{\alpha})=\infty\)_;_ 3. _Let_ \(i\in\{1,2\}\)_._ \(\tau^{d,\ell}_{p,2}(x,y,z)(G_{\alpha})\) _can be computed as follows:_ 3. _If_ \(C_{T}(G_{\alpha_{1}})\
eq\emptyset\) _and_ \(C_{\overline{T}}(G_{\alpha_{1}})\
eq\emptyset\)_, and_ \(C_{T}(G_{\alpha_{2}})\
eq\emptyset\) _and_ \(C_{\overline{T}}(G_{\alpha_{2}})\
eq\emptyset\)_, then_ 3. _If_ \(C_{T}(G_{\alpha_{1}})\
eq\emptyset\) _and_ \(C_{\overline{T}}(G_{\alpha_{1}})\
eq\emptyset\)_, and_ \(C_{T}(G_{\alpha_{2}})\
eq\emptyset\) _and_ \(C_{\overline{T}}(G_{\alpha_{2}})=\emptyset\)_, then_ 3. _If_ \(C_{T}(G_{\alpha_{1}})\
eq\emptyset\) _and_ \(C_{\overline{T}}(G_{\alpha_{1}})\
eq\emptyset\)_, and_ \(C_{T}(G_{\alpha_{2}-i})=\emptyset\)_, then_ 3. \(\tau^{d,\ell}_{p,2}(x,y,z)(G_{\alpha})=\min_{i\in\{1,2\}}\Big{\{}\tau^{d,\ell}_{p,2}(x,y,z)(G_{\alpha_{1}})+\tau^{d,\ell}_{p,1}(y,z)(G_{\alpha_{2}-i})\Big{\}}\)_;_ 3. _If_ \(C_{T}(G_{\alpha_{1}})\
eq\emptyset\) _and_ \(C_{\overline{T}}(G_{\alpha_{2}})=\emptyset\)_, and_ \(C_{T}(G_{\alpha_{2}-i})\
eq\emptyset\)_, then_ 3. \(\tau^{d,\ell}_{p,2}(x,y,z)(G_{\alpha})=\min_{i\in\{1,2\}}\Big{\{}\tau^{d,\ell}_{p,1}(y,z)(G_{\alpha_{1}})+\tau^{d,\ell}_{p,0}(x,z)(G_{\alpha_{2}-i})\Big{\}}\)_._  
Proof. : By definition, an induced subgraph of a distance-hereditary graph is also distance-hereditary. The graph \(G_{\alpha}\) is distance-hereditary and \(C(G_{\alpha})=C_{T}(G_{\alpha})\cup C_{\overline{T}}(G_{\alpha})\). If \(C_{T}(G_{\alpha})=\emptyset\) and \(C_{\overline{T}}(G_{\alpha})=\emptyset\), then \(G_{\alpha}\) has no vertices. Therefore, only three cases need to be considered based on their emptiness:  
* \(C_{T}(G_{\alpha})=\emptyset\) and \(C_{\overline{T}}(G_{\alpha})\
eq\emptyset\);
* \(C_{T}(G_{\alpha})\
eq\emptyset\) and \(C_{\overline{T}}(G_{\alpha})=\emptyset\);
* \(C_{T}(G_{\alpha})\
eq\emptyset\) and \(C_{\overline{T}}(G_{\alpha})\
eq\emptyset\). **(i) Assume that \(C_{T}(G_{\alpha})=\emptyset\) and \(C_{\overline{T}}(G_{\alpha})\
eq\emptyset\). ** By Definition 7, \(\tau^{d,\ell}_{p,1}(x,y)(G_{\alpha})=\infty\) and \(\tau^{d,\ell}_{p,2}(x,y,z)(G_{\alpha})=\infty\). Statements (1.1) and (1.2) therefore hold. Now, let us consider Statement (1.3).