# A Quasi-Hole Detection Algorithm for Recognizing \(k\)-Distance-Hereditary Graphs, with \(k<2\)
## 4 A Characterization Based on Cycle-Chord Conditions  
For the class of distance-hereditary graphs, [PERSON] provided the following well known characterization based on cycle-chord conditions. **Theorem 4** (from [1]). : _Let \(G\) be a graph. \(G\in\mathrm{DH}(1)\) if and only if each cycle \(C_{n}\), \(n\geq 5\), of \(G\) has two crossing chords._  
In [12], this result has been reformulated in terms of chord distance:  
**Theorem 5** (from [12]). : _Let \(G\) be a graph. \(G\in\mathrm{DH}(1)\) if and only if \(cd(C_{n})>1\) for each cycle \(C_{n}\), \(n\geq 5\), of \(G\)._  
In the remainder of this section, we provide a similar characterization for graphs belonging to \(s\mathrm{DH}(2)\). **Lemma 3**. : _Let \(G\) be a graph. If \(s(G)=2\) then \(G\) contains, as induced subgraph, a cycle \(C_{6}\) with chord distance at most 1._  
Proof. : According to Lemma 1, consider an inducing-stretch cycle \(G[x,y]\) of \(G\). Since \(s(G)=2\), assume that \(G[x,y]\) is formed by the vertices of the induced paths \(P_{G}(x,y)=(x,u_{1},u_{2},\ldots,u_{2s-1},y)\) and \(p_{G}(x,y)=(x,v_{1},v_{2},\ldots,v_{s-1},y)\), with \(s\geq 2\). If \(s=2\) then the proof is concluded. In fact, cycle \(G[x,y]\) has 6 vertices and every chord of \(G[x,y]\) (if any) is incident to \(v_{1}\). In the remainder of the proof assume \(s\geq 3\). In this case, according to Lemma 2, \(v_{1}\) is incident to chords of \(G[x,y]\). Let \((v_{1},u_{r_{1}})\) be the rightmost chord incident to \(v_{1}\). We analyze different cases according to the value of \(r_{1}\). * Assume \(r_{1}>4\). In this case, the induced paths \((x,u_{1},u_{2},\ldots,u_{r_{1}})\) and \((x,v_{1},u_{r_{1}})\) provide a stretch number \(s_{G}(x,u_{r_{1}})\geq\frac{r_{1}}{2}>2\), a contradiction. * Assume \(r_{1}\leq 2\). In this case, the induced paths \((v_{1},u_{r_{1}},u_{r_{1}+1},\ldots,u_{2s-1},y)\) and \((v_{1},v_{2},\ldots,v_{s-1},y)\) provide the following lower bound on \(s_{G}(v_{1},y)\): \[s_{G}(v_{1},y)\geq\frac{2s-r_{1}+1}{s-1}\geq\frac{2s-2+1}{s-1}=2+\frac{1}{s-1}.\]  
Figure 5: The _minimal_ forbidden subgraphs of any graph with stretch number less than 2. Dashed lines represent paths of length at least one. This contradicts \(s(G)=2\). It follows that either \(r_{1}=4\) or \(r_{1}=3\). In the first case the cycle \((v_{1},x,u_{1},u_{2},u_{3},u_{4})\) represents the requested cycle \(C_{6}\): chords of \(G[x,y]\) (if any) are all incident to \(v_{1}\). In the second case consider the induced paths \((v_{1},u_{r_{1}},u_{r_{1}+1},\ldots,u_{2s-1},y)\) and \((v_{1},v_{2},\ldots,v_{s-1},y)\). These paths induce the following lower bound on \(s_{G}(v_{1},y)\):  
\[s_{G}(v_{1},y)\geq\frac{2s-r_{1}+1}{s-1}=\frac{2s-3+1}{s-1}=2.\]  
Hence, the above paths induce a proper subgraph \(G^{\prime}\) of \(G\) with stretch number 2. Hence, this proof can be recursively applied to \(G^{\prime}\). Lemma 4: _Let \(G\) be a graph. \(s(G)\geq 2\) if and only if \(G\) contains, as an induced subgraph, a cycle \(C_{n}\), \(n\geq 6\), with chord distance at most 1._  
Proof. : (\(\Leftarrow\)) Trivial. (\(\Rightarrow\)) If \(s(G)=2\), then it is sufficient to use Lemma 3. Now, let us assume that \(s(G)=p/q>2\) such that \(p\) and \(q\) are coprime. By Lemma 1, if \(G[x,y]\) is an inducing-stretch cycle of \(G\), according to the hypotheses, we may assume that \(G[x,y]\) is formed by the vertices of the induced paths \(P_{G}(x,y)=(x,u_{1},u_{2},\ldots,u_{p\cdot s-1},y)\) and \(p_{G}(x,y)=(x,v_{1},v_{2},\ldots,v_{q\cdot s-1},y)\), with \(s\geq 1\). If \(d(x,y)=2\), then \(G[x,y]\) contains at least 6 vertices and all its chords (if any) are incident to \(v_{1}\). Then, \(G[x,y]\) corresponds to the requested cycle. In the remainder, assume that \(d(x,y)\geq 3\). In this case, by Lemma 2, vertex \(v_{1}\) is incident to chords of \(G[x,y]\): let \((v_{1},u_{r_{1}})\) be the rightmost chord incident to it.