# A Quasi-Hole Detection Algorithm for Recognizing \(k\)-Distance-Hereditary Graphs, with \(k<2\)
## 3 A Characterization Based on Forbidden Subgraphs  
A well known characterization based on _minimal forbidden subgraphs_ has been provided for the class of distance-hereditary graphs. **Theorem 2** (from [2]). : _A graph \(G\) is a distance-hereditary graph if and only if it does not contain, as an induced subgraph, any of the following graphs: the hole \(H_{n}\), \(n\geq 5\), the house, the fan, and the domino (cf. Figure 2)._  
This result can be easily reformulated, and simplified, by using the notion of chord distance. In particular, it is possible to characterize in a compact way all the forbidden subgraphs by using just the notion of chord distance as follows:  
* \(G\) _is a distance-hereditary graph if and only if the following graphs are not induced subgraphs of_ \(G\)_:_ \((i)\): \(H_{n}\)_, for each_ \(n\geq 5\)_;_ \((ii)\): _cycles_ \(C_{5}\) _with_ \(cd(C_{5})=1\)_;_ \((iii)\): _cycles_ \(C_{6}\) _with_ \(cd(C_{6})=1\)_._  
It is worth to notice that in this way we do not consider the minimal subgraphs only (cf. Figure 3). Figure 1: The chord distance of this \(C_{6}\) graph is two because: (i) vertices \(v_{1}\) and \(v_{2}\) are consecutive in the cycle, (ii) every chord is incident to one of such vertices, and (iii) there is no other set with less than two vertices with the same properties. Figure 2: The minimal forbidden subgraphs of distance-hereditary graphs: from left to right, the _hole_, the _house_, the _fan_, and the _domino_. Dashed lines represent paths of length at least one. In the following we provide a characterization similar to that of Theorem 2 for any graph \(G\in\mathrm{SDH}(2)\). Before giving such a result, we need to recall the following technical lemma. Lemma 2: _Let \(G\) be a graph and let \(G[x,y]\) be an inducing-stretch cycle of \(G\) defined by 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)\). If \(d(x,y)\geq 3\) then \(v_{1}\) must be incident to chords of the cycle \(G[x,y]\)._  
Proof. : Since \(G[x,y]\) is an inducing-stretch cycle of \(G\), then \(s(G)=\frac{p}{q}\). If \(v_{1}\) is not incident to any chords of \(G[x,y]\), then the induced paths \(P_{G}(v_{1},y)=(v_{1},x,u_{1},u_{2},\ldots,u_{p-1},y)\) and \(p_{G}(v_{1},y)=(v_{1},v_{2},\ldots,v_{q-1},y)\) imply \(s_{G}(v_{1},y)=\frac{p+1}{q-1}>\frac{p}{q}\), a contradiction. Let \(G\) be any graph. According to Lemma 1, let us consider an inducing-stretch cycle \(G[x,y]\) of \(G\). 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-1},y)\) and \(p_{G}(x,y)=(x,v_{1},v_{2},\ldots,v_{q-1},y)\). Since \(P_{G}(x,y)\) and \(p_{G}(x,y)\) are induced paths, each chord of \(G[x,y]\) (if any) joins vertices \(v_{i}\) and \(u_{i}\), with \(1\leq i\leq q-1\) and \(1\leq j\leq p-1\). When some vertex \(v_{i}\) is incident to chords of \(G[x,y]\), we denote by \((v_{i},u_{i_{j}})\) and \((v_{i},u_{i_{j}})\) the _leftmost_ and _rightmost_ chords of \(v_{i}\), respectively. Formally, the indices \(l_{i}\) and \(r_{i}\) are defined as follows:  
* \(l_{i}=\min\{i^{\prime}\ |\ 1\leq i^{\prime}\leq p-1\text{ and }(v_{i},u_{i^{\prime}})\text{ is a chord of }G[x,y]\}\)
* \(r_{i}=\max\{i^{\prime}\ |\ 1\leq i^{\prime}\leq p-1\text{ and }(v_{i},u_{i^{\prime}})\text{ is a chord of }G[x,y]\}\)  
Theorem 3: _Let \(G\) be a graph. \(G\in\mathrm{SDH}(2)\) if and only if the following graphs are not induced subgraphs of \(G\):_  
* \(H_{n}\)_, for each_ \(n\geq 6\)_;_
* _cycles_ \(C_{6}\) _with_ \(cd(C_{6})=1\)_;_
* _cycles_ \(C_{7}\) _with_ \(cd(C_{7})=1\)_;_
* _cycles_ \(C_{8}\) _with_ \(cd(C_{8})=1\)_._  
Proof. : (\(\Rightarrow\)) Each provided hole and cycle has stretch number greater or equal to 2, and hence it cannot be an induced subgraph of \(G\). (\(\Leftarrow\)) We prove that if \(s(G)\geq 2\), then \(G\) contains one of the subgraphs in items \((i)\), \((ii)\), \((iii)\), or \((iv)\), or \(G\) contains a proper induced subgraph \(G^{\prime}\) such that \(s(G^{\prime})\geq 2\).