# A Quasi-Hole Detection Algorithm for Recognizing \(k\)-Distance-Hereditary Graphs, with \(k<2\)
## 3 A Characterization Based on Forbidden Subgraphs
In the latter case, we can recursively apply to \(G^{\prime}\) the following proof. According to Lemma 1, consider an inducing-stretch cycle \(G[x,y]\) of \(G\) and assume it is formed by the vertices of the induced paths \(P_{G}(x,y)=(x,u_{1},u_{2},\ldots,u_{p-1},y)\) and \(p_{G}(x,y)=(x,v_{1},v_{2},\ldots,v_{q-1},y)\). Notice that, since \(P_{G}(x,y)\) and \(p_{G}(x,y)\) are induced paths, each possible chord of \(G[x,y]\) joins vertices \(v_{i}\) and \(u_{j}\), with \(1\leq i\leq q-1\) and \(1\leq j\leq p-1\). Since \(\frac{p}{q}\geq 2\) by hypotheses, then \(q\geq 2\) by Item \((i)\) of Lemma 1, and hence \(p\geq 4\). According to the value of \(q\), we analyze two different cases:  
* In this case, if \(G[x,y]\) is chordless, then it corresponds to a hole as described in Item \((i)\). If the chord distance of \(G[x,y]\) is equal to 1, all chords are incident to \(v_{1}\). According to \(p\), we have:  
Figure 3: The forbidden subgraphs of \(\mathrm{DH}(1)\) expressed according to the notion of chord distance. Dashed lines represent paths of length at least one. Dotted lines represent chords that may or may not exist. * \(G[x,y]\) corresponds to the cycle in Item \((ii)\);
* \(G[x,y]\) corresponds to the cycle in Item \((iii)\);
* \(G[x,y]\) corresponds to the cycle in Item \((iv)\);
* Let \((v_{1},u_{l_{1}})\) be the leftmost chord of \(v_{1}\). If \(l_{1}\geq 4\) the cycle \((v_{1},x,u_{1},u_{2},\ldots,u_{l_{1}})\) corresponds to the cycle in Item \((i)\). When \(l_{1}\leq 3\), consider the subgraph \(G^{\prime}\) induced by the vertices in the cycle \((v_{1},u_{l_{1}},u_{l_{1}+1},\ldots,u_{p-1},y)\). The induced paths \(P^{\prime}=(u_{l_{1}},u_{l_{1}+1},\ldots,u_{p-1},y)\) and \(p^{\prime}=(u_{l_{1}},v_{1},y)\) provide the following lower bound for \(s_{G^{\prime}}\): \[s_{G^{\prime}}(u_{l_{1}},y)\geq\frac{p-l_{1}}{2}\geq\frac{7-3}{2}=2.\]  
Hence, \(G^{\prime}\) is a proper subgraph of \(G\) with \(s(G^{\prime})\geq 2\). The statement follows by recursively applying to \(G^{\prime}\) this proof. * In this case, according to Lemma 2, \(v_{1}\) must be incident to chords. We now analyze two cases with respect to the value of \(r_{1}\), \((v_{1},u_{r_{1}})\) being the rightmost chord of \(v_{1}\):
* Consider the subgraph \(G^{\prime\prime}\) induced by the vertices in the cycle \((v_{1},x,u_{1},u_{2},\ldots,u_{r_{1}})\). In this case, the induced paths \(P^{\prime\prime}=(x,u_{1},u_{2},\ldots,u_{r_{1}})\) and \(p^{\prime\prime}=(x,v_{1},u_{r_{1}})\) provide the following lower bound for \(s_{G^{\prime\prime}}\): \(s_{G^{\prime\prime}}(x,u_{r_{1}})\geq r_{1}/2\geq 2\). Hence, \(G^{\prime\prime}\) is a proper subgraph of \(G\) with \(s(G^{\prime\prime})\geq 2\). The statement follows by recursively applying to \(G^{\prime\prime}\) this proof. * in this case the induced paths \(P^{\prime\prime\prime}=(v_{1},u_{r_{1}},u_{r_{1}+1},\ldots,u_{p-1},y)\) and \(p^{\prime\prime\prime}=(v_{1},v_{2},\ldots,v_{q-1},y)\) provide the following lower bound for \(s_{G}(v_{1},y)\): \[s_{G}(v_{1},y)\geq\frac{p-2}{q-1}.\]  
Since \(\frac{p-2}{q-1}\geq\frac{p}{q}\) is equivalent to \(\frac{p}{q}\geq 2\) (which holds by hypothesis), then the subgraph \(G^{\prime\prime\prime}\) induced by the vertices in both \(P^{\prime\prime\prime}\) and \(p^{\prime\prime\prime}\) is a proper subgraph of \(G\) with stretch \(p^{*}/q^{*}\geq 2\) and \(q^{*}=q-1\). Hence, the statement follows by recursively applying to \(G^{\prime\prime\prime}\) this proof. This concludes the proof. Figures 3 and 4 summarize the characterizations based on forbidden subgraphs for classes \(\mathrm{DH}(1)\) and \(s\mathrm{DH}(2)\), respectively. Figure 5 provides the list of all the _minimal_ forbidden subgraphs of any graph in \(s\mathrm{DH}(2)\). Figure 4: The forbidden subgraphs of graphs having stretch number less than 2. Dashed (dotted, respectively) lines represent paths of length at least one (chords that may or may not exist, respectively).