# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs
### Adding a Tail to a Spider
The term \(R_{H}\setminus N_{H}[u]\) corresponds to making \(u\) universal in \(H[R_{H}]\), in which case the resulting graph is \(P_{4}\)-sparse (it is a thin spider with \(S=S_{H}\cup\left\{w\right\}\), \(K=K_{H}\cup\left\{u\right\}\) and \(R=R_{H}\setminus\left\{u\right\}\)). The term \(|K_{H}|+f^{\prime}\) corresponds to adding \(|K_{H}|\) fill edges connecting \(w\) to the vertices in \(K_{H}\) and then computing a minimum \(P_{4}\)-sparse completion of the graph \(H[R_{H}]+uw\). Note that no minimum \(P_{4}\)-sparse completion of \(H+uw\) exists with  
Figure 8: A transformation that reduces the number of fill edges. not being universal in \(R_{H}\) and with using fewer than \(|K_{H}|\) fill edges incident on the vertices in \(S_{H}\cup K_{H}\): if there were such a minimum \(P_{4}\)-sparse completion \(H^{\prime}\) of \(H+uw\), then in \(H^{\prime}\), there would exist a non-neighbor \(r\in R_{H}\) and a pair of adjacent vertices \(s,k\) where \(s\in S_{H}\) and \(k\in K_{H}\) such that neither \(s\) nor \(k\) would be incident on a fill edge; but then, in \(H^{\prime}\), the vertices \(u,w,r,s,k\) induce an \(F_{4}\) or an \(F_{3}\) if \(w,r\) have been connected by a fill edge or not, respectively, which leads to a contradiction. In turn, if \(H^{\prime}\) has at least \(|K_{H}\) fill edges incident on vertices in \(S_{H}\cup K_{H}\) then \(H^{\prime}[R_{H}\cup\{w\}]\) would be \(P_{4}\)-sparse using fewer than \(f^{\prime}\) fill edges in contradiction to the minimality of \(f^{\prime}\). (If \(u\in R_{H}\), the former case corresponds to making \(u\) universal in \(G[R_{H}]\) and the latter to inserting \(w\) in \(R_{H}\) by making it adjacent to all the vertices in \(K_{H}\). Furthermore, note that if \(u\in R_{H}\) and \(u\)'s parent node is the 2-node corresponding to the thin spider \(H\), then \(R_{H}=\{u\}\) and no fill edges are needed.) **Lemma 7**. : _Consider the addition of a tail \(uw\) to a thick spider \(H=(S_{H}\), \(K_{H}\), \(R_{H})\) where \(u\) is a vertex of \(H\). Then, for the number \(f\) of fill edges (excluding the tail \(uv\)) in a minimum \(P_{4}\)-sparse completion of the graph \(H+uw\), the following holds:_  
1. _If_ \(u\in S_{H}\)_,_ \[f\;=\;\left\{ \begin{array}{ll}|K_{H}|-1=2&\mbox{if $|K_{H}|=3$ and $R_{H}=\emptyset$}\\ |K_{H}|=3&\mbox{if $|K_{H}|=3$ and $|R_{H}|=1$}\\ |K_{H}|+1=4&\mbox{if $|K_{H}|=3$ and $|R_{H}|\geq 2$}\\ |K_{H}|&\mbox{if $|K_{H}|\geq 4$ and $R_{H}=\emptyset$}\\ |K_{H}|+1&\mbox{if $|K_{H}|\geq 4$ and $|R_{H}|\geq 1$;}\end{array} \right.\]
2. _If_ \(u\in K_{H}\)_,_ \(f=1\)_;_
3. _If_ \(u\in R_{H}\)_, then_ \(f=|K_{H}|+f^{\prime}\) _where_ \(f^{\prime}\) _is the number of fill edges (excluding_ \(uw\)_) in a minimum_ \(P_{4}\)_-sparse completion of the graph_ \(H[R_{H}]+uw\)_._  
Proof. : 1. Let \(v\in K_{H}\) be the non-neighbor of \(u\) in \(H\). Let us first consider the case \(|K_{H}|=3\). If \(|R_{H}|\leq 2\), we can obtain a \(P_{4}\)-sparse graph after having added the fill edges \(vu\) and \(vw\) (this implies that \(v\) becomes universal in \((V(H)\setminus\{v\})\cup\{w\}\)) and those connecting \(u\) to the vertices in \(R_{H}\) if \(R_{H}\) is non-empty; then the vertices in \((V(H)\setminus\{v\})\cup\{w\}\) induce a thin spider with \(K=(K_{H}\setminus\{v\})\cup\{u\}\), \(S=(S_{H}\setminus\{u\})\cup\{w\}\) and \(R=R_{H}\), for a total of \(|K_{H}|-1+|R_{H}|\) fill edges (excluding the tail \(uw\)). If \(|R_{H}|\geq 2\), a \(P_{4}\)-sparse graph is obtained after in addition to the tail \(uw\) we add the fill edges \(vu\), \(vw\) (again \(v\) is universal in \((V(H)\setminus\{v\})\cup\{w\}\)) and the fill edges connecting \(w\) to the vertices in \(K_{H}\setminus\{v\}\) (then the vertices in \((V(H)\setminus\{v\})\cup\{w\}\) induce a thin spider with \(K=K_{H}\setminus\{v\}\), \(S=S_{H}\setminus\{u\}\) and \(R=R_{H}\cup\{u,w\}\)), for a total of \(|K_{H}|+1\) fill edges (excluding \(uw\)). Now, consider the case that \(|K_{H}|\geq 4\).