# A Quasi-Hole Detection Algorithm for Recognizing \(k\)-Distance-Hereditary Graphs, with \(k<2\)
## 1 Introduction  
Distance-hereditary graphs have been introduced by [PERSON] [1], and are defined as those graphs in which every connected induced subgraph is isometric; that is, the distance between any two vertices in the subgraph is equal to the one in the whole graph. Therefore, any connected induced subgraph of any distance-hereditary graph \(G\) \"inherits\" its distance function from \(G\). Formally:  
**Definition 1** (from [1]). : _A graph \(G\) is a distance-hereditary graph if, for each connected induced subgraph \(G^{\prime}\) of \(G\), the following holds: \(d_{G^{\prime}}(x,y)=d_{G}(x,y)\), for each \(x,y\in G^{\prime}\)._  
This kind of graph have been rediscovered many times (e.g., see [2]). Since their introduction, dozens of papers have been devoted to them, and different kinds of characterizations have been found: metric, forbidden subgraphs, cycle/chord conditions, level/neighborhood conditions, generative, and more (e.g., see [3]). Among such results, the generative properties resulted as the most fruitful for algorithmic applications, since they allowed researchers to efficiently solve many combinatorial problems in the class of distance-hereditary graphs (e.g., see [4, 5, 6, 7, 8, 9]). From an applicative point of view, distance-hereditary graphs are mainly attractive due to their basic metric property. For instance, these graphs can model unreliable communication networks [10, 11] in which vertex failures may occur: at a given time, if sender and receiver are still connected, any message can be still delivered without increasing the length of the path used to reach the receiver. Since in communication networks this property could be considered too restrictive, in [12] the class of \(k\)_-distance-hereditary graphs_ has been introduced. These graphs can model unreliable networks in which messages can eventually reach the destination traversing a path whose length is at most \(k\) times the length of a shortest path computed in absence of vertex failures. The minimum \(k\) a network guarantees regardless the failed vertices is called _stretch number_. Formally:  
**Definition 2** (from [12]). : _Given a real number \(k\geq 1\), a graph \(G\) is a \(k\)-distance-hereditary graph if, for each connected induced subgraph \(G^{\prime}\) of \(G\), the following holds: \(d_{G^{\prime}}(x,y)\leq k\cdot d_{G}(x,y)\), for each \(x,y\in G^{\prime}\)._  
The class of all the \(k\)-distance-hereditary graphs is denoted by \(\mathrm{DH}(k)\). Concerning this class of graphs, the following relationships hold:  
* \(\mathrm{DH}(1)\) coincides with the class of distance-hereditary graphs;
* \(\mathrm{DH}(k_{1})\subseteq\mathrm{DH}(k_{2})\), for each \(k_{1}\leq k_{2}\). Additional results about the class hierarchy \(\mathrm{DH}(k)\) can be found in [13; 14]. It is worth to notice that this hierarchy is _fully general_; that is, for each arbitrary graph \(G\) there exists a number \(k\) such that \(G\in\mathrm{DH}(k)\). It follows that the stretch number of \(G\), denoted as \(s(G)\), is the smallest number \(t\) such that \(G\) belongs to \(\mathrm{DH}(t)\). In [12], it has been shown that the stretch number \(s(G)\) of any connected graph \(G\) can be computed as follows:  
* the stretch number of any pair \(\{u,v\}\) of distinct vertices is defined as \(s_{G}(u,v)=D_{G}(u,v)/d_{G}(u,v)\), where \(D_{G}(u,v)\) is the length of any longest induced path between \(u\) and \(v\), and \(d_{G}(u,v)\) is the distance between the same pair of vertices;
* \(s(G)=\max_{\{u,v\}}s_{G}(u,v)\). It follows that for any non-trivial graph \(G\) with \(n\geq 4\) vertices, by simply maximizing \(D(u,v)\) and minimizing \(d(u,v)\), we get \(s(G)\leq(n-2)/2\). From the above relationship about \(s(G)\), we get that the stretch number is always a rational number. Interestingly, it has been shown that there are some rational numbers that cannot be stretch numbers. Formally, a positive rational number \(t\) is called _admissible stretch number_ if there exists a graph \(G\) such that \(s(G)=t\).