# Adding a Tail in Classes of Perfect Graphs
## 4 Threshold and Quasi-Threshold Graphs  
**Threshold Graphs**. A well-known subclass of perfect graphs called threshold graphs are those whose independent vertex set subsets can be distinguished by using a single linear inequality: a graph \(G\) is _threshold_ if there exists a threshold assignment \([\alpha,t]\) consisting of a labeling \(\alpha\) of the vertices by non-negative integers and an integer threshold \(t\) such that a set \(S\subseteq V(G)\) is independent if and only if \(\alpha(v_{1})+\alpha(v_{2})+\cdots+\alpha(v_{p})\leq t\) where \(v_{i}\in S,1\leq i\leq p\). [PERSON] and [PERSON] [33] first proposed threshold graphs in 1973 and proved that the threshold graphs are precisely the graphs that contain no induced \(C_{4}\), \(P_{4}\) or \(2K_{2}\). [PERSON] [45] proved that every threshold graph admits a unique rooted tree representation as shown in Figure 1(left): each tree node stores a vertex set \(V_{i,j}\) (these sets partition the vertex set of the graph) with each \(V_{i,1}\) inducing a clique and each of the remaining sets containing a single vertex (note that the tree nodes that store these singleton sets have no descendants) and the vertices in the union of the sets stored in the nodes on a path from a tree node to any one of its descendants induce a clique. Thus, the vertices in \(V_{k,1}\) are adjacent to all the vertices in \(\bigcup_{i>k}V_{i,j}\), the vertices in \(\bigcup_{i}V_{i,1}\) induce a clique and the vertices in \(\bigcup_{i}\bigcup_{j\geq 2}V_{i,j}\) form an independent set. Regarding the addition of a tail to a threshold graph, we show the following lemma. Lemma 2: _Let \(G\) be a threshold graph and let the nodes of its tree representation \(T_{G}\) store the sets \(V_{i,j}\) for all \(0\leq i\leq h\) and \(1\leq j\leq k_{i}\) where \(k_{0}=1\) and \(k_{i}\geq 2\) for \(i\geq 1\) (Figure 1(left)). Consider the addition of a tail \(uw\) where \(u\in V(G)\). Then, there exists a minimum threshold completion of the graph \(G+uw\) which uses \(f\) fill edges (excluding the tail \(uw\)) where:_  
_(i) If \(u\in V_{p,1}\), then \(f=\min_{0\leq\ell\leq p}\Bigl{\{}\Bigl{(}\sum_{s=\ell+1}^{p}(k_{s}-1)\Bigr{)} +\sum_{s=0}^{\ell-1}|V_{s,1}|\Bigr{\}}\);_  
Figure 1: **(left)** The structure of the tree representation of a threshold graph [45]; **(right)** Formation for the addition of the tail \(uw\). _._ _If_ \(u\in V_{p,j}\) _where_ \(2\leq j\leq k_{p}\)_, then_ \(f=\min\{f_{1},f_{2}\}\) _where_ \(f_{1}=\sum_{r=p}^{h}|V_{r,1}|+\min_{p\leq\ell\leq h}\left\{\left(\sum_{s=\ell+1 }^{h}(k_{s}-1)\right)+\sum_{s=0}^{\ell-1}|V_{s,1}|\right\}\) _and_ \(f_{2}=\sum_{r=p}^{h}|V_{r,1}|+\min_{0\leq\ell\leq p-1}\left\{\left(\sum_{s=\ell +1}^{h}(k_{s}-1)\right)+\sum_{s=0}^{\ell-1}|V_{s,1}|\right\}-1\)_._  
Proof. : Let \(G_{OPT}\) be a minimum threshold completion of the graph \(G+uw\) whose tree representation \(T_{OPT}\) has nodes storing sets \(V^{\prime}_{i,j}\) where \(0\leq i\leq h^{\prime}\), \(1\leq j\leq k^{\prime}_{i}\) where \(k^{\prime}_{0}=1\) and \(k^{\prime}_{i}\geq 2\) for \(i\geq 1\); moreover, let \(K^{\prime}=\bigcup_{s=0}^{h^{\prime}}V^{\prime}_{s,1}\) and \(S^{\prime}=\bigcup_{s=1}^{h^{\prime}}\bigcup_{t=2}^{k^{\prime}}V^{\prime}_{s,t }=(V(G)\cup\{w\})\setminus K^{\prime}\). Below, we give the properties of the structure of \(T_{OPT}\). Since \(u,w\) are adjacent in \(G_{OPT}\), \(u,w\) cannot both belong to \(S^{\prime}\). Additionally, we can assume that \(u\in K^{\prime}\); if \(u\in S^{\prime}\) then \(w\in K^{\prime}\) which implies that \(N_{G_{OPT}}[u]\subseteq K^{\prime}\subseteq N_{G_{OPT}}[w]\) and thus we can exchange \(u\) and \(w\), obtaining a threshold completion of \(G+uw\) using the same number of fill edges in which \(u\in K^{\prime}\). The \(u,w\) exchange can also be applied if \(u\in V^{\prime}_{i,1}\) and \(w\in V^{\prime}_{j,1}\) with \(i>j\); thus, if \(u,w\in K^{\prime}\) with \(u\in V^{\prime}_{i,1}\) and \(w\in V^{\prime}_{j,1}\), we can assume that \(i\leq j\).