# A Quasi-Hole Detection Algorithm for Recognizing \(k\)-Distance-Hereditary Graphs, with \(k<2\)
## 2 Notation and Basic Concepts  
We consider finite, simple, loop-less, undirected, and unweighted graphs \(G=(V,E)\) with vertex set \(V\) and edge set \(E\). A _subgraph_ of \(G\) is a graph having all its vertices and edges in \(G\). Given \(S\subseteq V\), the _induced subgraph_\(G[S]\) of \(G\) is the maximal subgraph of \(G\) with vertex set \(S\). Given \(u\in V\), \(N_{G}(u)\) denotes the set of _neighbors_ of \(u\) in \(G\), and \(N_{G}[u]=N_{G}(u)\cup\{u\}\). A sequence of pairwise distinct vertices \((x_{0},x_{1},\ldots,x_{k})\) is a _path_ in \(G\) if \((x_{i},x_{i+1})\in E\) for \(0\leq i<k\); vertex \(x_{i}\), for each \(0<i<k\), is an _internal vertex_ of that path. A _chord_ of a path is any edge joining two non-consecutive vertices in the path, and a path is an _induced path_ if it has no chords. We denote by \(P_{k}\) any induced path with \(k\geq 3\) vertices (e.g., an induced path on three vertices is denoted as \(P_{3}\) whereas an induced path on four vertices is denoted as \(P_{4}\)). Two vertices \(x\) and \(y\) are _connected_ in \(G\) if there exists a path \((x,\ldots,y)\) in \(G\). A graph is _connected_ if every pair of vertices is connected. A _cycle_ in \(G\) is a path \((x_{0},x_{1},\ldots,x_{k-1})\) where also \((x_{0},x_{k-1})\in E\). Two vertices \(x_{i}\) and \(x_{j}\) are _consecutive_ in the cycle \((x_{0},x_{1},\ldots,x_{k-1})\) if \(j=(i+1)\) mod \(k\) or \(i=(j+1)\) mod \(k\). A _chord_ of a cycle is an edge joining two non-consecutive vertices in the cycle. We denote by \(C_{k}\) any cycle with \(k\geq 3\) vertices, whereas \(H_{k}\) denotes a _hole_, i.e., a cycle \(C_{k}\), \(k\geq 5\), without chords. The _chord distance_ of a cycle \(C_{k}\) is denoted by \(cd(C_{k})\) and is defined as the minimum number of consecutive vertices in \(C_{k}\) such that every chord of \(C_{k}\) is incident to some of such vertices (see Figure 1 for an example of chord distance). We assume \(cd(H_{k})=0\). The length of any shortest path between two vertices \(x\) and \(y\) in a graph \(G\) is called _distance_ and is denoted by \(d_{G}(x,y)\). Moreover, the length of any longest induced path between them is denoted by \(D_{G}(x,y)\). If \(x\) and \(y\) are distinct vertices, we use the symbols \(p_{G}(x,y)\) and \(P_{G}(x,y)\) to denote any shortest and any longest induced path between \(x\) and \(y\), respectively. Sometimes, when no ambiguity occurs, we also use \(p_{G}(x,y)\) and \(P_{G}(x,y)\) to denote the sets of vertices belonging to the corresponding paths. If \(d_{G}(x,y)\geq 2\), then \(\{x,y\}\) is a _cycle-pair_ if there exist two induced paths \(p_{G}(x,y)\) and \(P_{G}(x,y)\) such that \(p_{G}(x,y)\cap P_{G}(x,y)=\{x,y\}\). In other words, if \(\{x,y\}\) is a cycle-pair, then there exist induced paths \(p_{G}(x,y)\) and \(P_{G}(x,y)\) such that the vertices in \(p_{G}(x,y)\cup P_{G}(x,y)\) form a cycle in \(G\); this cycle is denoted by \(G[x,y]\). In Figure 1\(\{v_{3},v_{6}\}\) is a cycle-pair that induces the cycle \((v_{3},v_{4},v_{5},v_{6},v_{1})\); in particular, \(G[v_{3},v_{6}]\) is induced by \(p_{G}(v_{3},v_{6})=(v_{3},v_{1},v_{6})\) and \(P_{G}(v_{3},v_{6})=(v_{3},v_{4},v_{5},\(\{\{x,y\}:s_{G}(x,y)=s(G)\}\). The following lemma states that cycle-pairs are useful to determine the stretch number. **Lemma 1** (from [12]). : _Let \(G\) be a graph such that \(s(G)>1\). The following relationships hold:_  
\((i)\): \(d_{G}(u,v)\geq 2\) _for each pair_ \(\{u,v\}\) _such that_ \(\{u,v\}\in\mathcal{S}(G)\)_,_  
\((ii)\): _there exists a cycle-pair_ \(\{u,v\}\) _that induces the stretch number of_ \(G\)_, that is_ \(\{u,v\}\in\mathcal{S}(G)\)_._  
This lemma suggests that studying \(s(G)\) concerns the analysis of cycles in \(G\). In particular, if \(\{u,v\}\) is a cycle-pair that belongs to \(\mathcal{S}(G)\), then the cycle \(G[u,v]\) is called _inducing-stretch cycle_ for \(G\).