# Adding a Tail in Classes of Perfect Graphs
## 4 Threshold and Quasi-Threshold Graphs
Then, we remove \(u\) (that is, we assume that \(V_{p,j}\) becomes empty) and add the formation of Figure 1(right) just above each node storing \(V_{\ell,1}\) for \(0\leq\ell\leq h\) which results in fill edges connecting \(u\) to all vertices in \((\bigcup_{r=p}^{h}V_{r,1})\cup\bigcup_{s=\ell+1}^{h}\bigcup_{t=2}^{k_{s}}V_{s,t}\) and \(w\) to all vertices in \(\bigcup_{s=0}^{\ell-1}V_{s,1}\) which yields the number of fill edges stated in the lemma taking into account that \(\sum_{t=2}^{k_{s}}|V_{s,t}|=k_{s}-1\) and that if \(\ell<p\) we must subtract \(1\) for the removed \(u\). The number of fill edges in Lemma 2 results from using the formation in Figure 1(right) above each node in the path from the node storing \(V_{p,1}\) to the root of \(T_{G}\) in Case (i) and above each node in the path from the node storing \(V_{h,1}\) to the root of \(T_{G}\) in Case (ii) taking into account the removal of the node storing the set \(V_{p,j}=\{u\}\). Lemma 2 implies that given the tree representation \(T_{G}\) of the given threshold graph \(G\), the minimum number of fill edges can be computed in \(O(|V(G)|)\) time; otherwise, the time complexity is \(O(|V(G)|+|E(G)|)\). **Quasi-threshold Graphs**. A graph \(G\) is called _quasi-threshold_ or QT-graph for short, if \(G\) contains no induced \(C_{4}\) or \(P_{4}\)[46; 47; 48; 34]. The class of quasi-threshold graphs is a subclass of the class of cographs and properly contains the class of threshold graphs [49; 32; 50; 51]. [PERSON] et al. [52] proposed the heuristic Quasi-Threshold Mover algorithm to solve the problem of transforming a given graph into a quasi-threshold graph using a small number of edge additions and deletions, which they later used to solve the inclusion-minimal version of the problem [53]. [PERSON] and [PERSON] [54] have shown, among other properties, a unique rooted tree representation of QT-graphs which is a generalization of the tree representation of threshold graphs (Figure 2): the tree nodes store disjoint vertex subsets, each inducing a clique and the vertex sets stored in the tree nodes on a path from a tree node to any of its descendants, induce a clique. It has been proven that a graph is QT-graph if and only if it admits such a tree representation [55; 56]. Then, by generalizing the approach in Case (i) of Lemma 2, we can show the following lemma. Lemma 3: _Let \(G\) be a QT-graph and \(T_{G}\) its tree representation. Moreover, let \(u\) be a vertex of \(G\) for which we assume without loss of generality that \(u\in V_{p,1}\) and that the vertex sets stored in the tree nodes on the path from the root of \(T_{G}\) to the node storing \(V_{p,1}\) are in order \(V_{0,1},V_{1,1},\ldots,V_{p,1}\). Consider the addition of a tail \(uv\) to \(G\). Then, any minimum \(QT\) completion of the graph \(G+uw\) uses \(\min_{0\leq\ell\leq p}\left\{\left(\sum_{s=\ell+1}^{p}\sum_{t=2}^{k_{s}}|V_{s,t}|\right)+\sum_{s=0}^{\ell-1}|V_{s,1}|\right\}\) fill edges (excluding the tail \(uw\))._  
As previously, Lemma 3 implies that given the tree representation of the given quasi-threshold graph \(G\), the minimum number of fill edges can be computed in \(O(|V(G)|)\) time; otherwise, the time complexity is \(O(|V(G)|+|E(G)|)\).