# A Quasi-Hole Detection Algorithm for Recognizing \(k\)-Distance-Hereditary Graphs, with \(k<2\)
## 1 Introduction
The following result characterizes which numbers are admissible stretch numbers. **Theorem 1** (from [14]). : _A rational number \(t\) is an admissible stretch number if and only if \(t=2-\frac{1}{t}\), for some integer \(i\geq 1\), or \(t\geq 2\)._  
Apart from the interesting general results found for the classes \(\mathrm{DH}(k)\), the original motivation was studying how (if possible) to extend the known algorithmic results from the base class, namely \(\mathrm{DH}(1)\), to \(\mathrm{DH}(k)\) for some constant \(k>1\). According to Theorem 1, in this work we are interested in studying the class containing each graph \(G\) such that \(s(G)<2\). Since this class contains graphs with stretch number _strictly_ less than two, throughout this paper it will be denoted by \(\mathrm{sDH}(2)\). **Results. ** In this work, we provide three results for the class \(\mathrm{sDH}(2)\), namely two different characterizations and a recognition algorithm (notice that the characterizations have already been presented in [13] but with omitted proofs). The first characterization is based on listing all the minimal forbidden subgraphs for each graph in the class. It is interesting to observe the similarity with the corresponding result for the class \(\mathrm{DH}(1)\):  
* **(adapted from [2])**\(G\in\mathrm{DH}(1)\) if and only if the following graphs are not induced subgraphs of \(G\): **-**: holes \(H_{n}\), for each \(n\geq 5\); **-**: cycles \(C_{5}\) with \(cd(C_{5})=1\); **-**: cycles \(C_{6}\) with \(cd(C_{6})=1\). * **(this paper)**\(G\in\mathrm{sDH}(2)\) if and only if the following graphs are not induced subgraphs of \(G\): **-**: holes \(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\). Here we used the notion of \"chord distance\" \(cd(C)\) to express the position of possible chords within any cycle \(C\) (see Section 2 for a formal definition). Notice that in [14] a similar result has been provided for the generic class \(\mathrm{DH}(2-\frac{1}{i})\), \(i>1\). The second result is a characterization based on a cycle-chord property. As in the previous case, notice the similarity with the corresponding result for the class \(\mathrm{DH}(1)\):  
* **(from [12])**\(G\in\mathrm{DH}(1)\) if and only if \(cd(C_{n})>1\) for each cycle \(C_{n}\), \(n\geq 5\), of \(G\);
* **(this paper)**\(G\in\mathrm{sDH}(2)\) if and only if \(cd(C_{n})>1\) for each cycle \(C_{n}\), \(n\geq 6\), of \(G\). The last result is a recognition algorithm for graphs belonging to \(\mathrm{sDH}(2)\) that works in \(O(n^{2}m^{2})\) time and \(O(m^{2})\) space. Basically, this algorithm exploits the result based on the cycle-chord property and, as a consequence, simply detects _quasi-holes_ in any graph. A quasi-hole is any cycle with at least five vertices and chord-distance at most one (i.e., all the possible chords of the cycle must be incident to the same vertex). This algorithm is obtained by adapting the algorithm provided in [15] for detecting holes (i.e., any cycle with at least five vertices and no chords). **Outline. ** The paper is organized as follows. In Section 2, we introduce notation and basic concepts used throughout the paper. Sections 3 and 4 are devoted to providing the characterization based on minimal forbidden subgraphs and cycle-chord conditions for graphs in \(\mathrm{sDH}(2)\), respectively. In Section 5, we provide the algorithm for detecting quasi-holes and hence to solve the recognition problem for the class \(\mathrm{sDH}(2)\). Finally, Section 6 provides some concluding remarks.