# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs  
A graph in which every set of five vertices induces at most one \(P_{4}\) is \(P_{4}\)-_sparse_[57] (Figure 3 depicts the seven forbidden subgraphs for the class of \(P_{4}\)-sparse graphs). The \(P_{4}\)-sparse graphs are perfect and also perfectly orderable [57] and properly contain many graph classes, such as the cographs, the \(P_{4}\)-reducible graphs, etc (see [37; 38; 58]). They have received considerable attention in recent years and find applications in applied mathematics and computer science (e.g., communications, transportation, clustering, scheduling, computational semantics) in problems that deal with graphs featuring \"local density\" properties. Figure 3: The forbidden subgraphs for the class of \(P_{4}\)-sparse graphs [38]. Figure 2: The tree representation of a quasi-threshold graph. For a \(P_{4}\)-sparse graph, either the graph or its complement is disconnected with the connected components inducing \(P_{4}\)-sparse graphs or it induces a spider. A graph \(H\) is called a _spider_ if its vertex set \(V(H)\) admits a partition into sets \(S,K,R\) such that:  
* The set \(S\) is an independent set, the set \(K\) is a clique and \(|S|=|K|\geq 2\);
* Every vertex in \(R\) is adjacent to every vertex in \(K\) and to no vertex in \(S\);
* There exists a bijection \(f:S\to K\) such that for each vertex \(s\in S\) either \(N_{G}(s)\cap K=\{f(s)\}\) or \(N_{G}(s)\cap K=K-\{f(s)\}\); in the former case, the spider is _thin_, in the latter it is _thick_ (see Figure 4). Note that for \(|S|=|K|=2\), the spider is simultaneously thin and thick. To avoid ambiguity, in the following, for thick spiders we assume that \(|K|\geq 3\). In [38], [PERSON] and [PERSON] showed that each \(P_{4}\)-sparse graph \(G\) admits a unique tree representation, up to isomorphism, called the \(P_{4}\)-_sparse tree_\(T(G)\) of \(G\), which is a rooted tree such that:  
* Each internal node of \(T(G)\) has at least two children provided that \(|V(G)|\geq 2\);
* The internal nodes are labeled by one of 0, 1 or 2 (0-, 1-, 2-nodes, respectively) and the parent node of each 0- or 1-node \(t\) has a different label than \(t\);
* The leaves of the \(P_{4}\)-sparse tree are in a one-to-one correspondence with the vertices of \(G\); if the least common ancestor of the leaves corresponding to two vertices \(v_{i},v_{j}\) of \(G\) is a 0-node (1-node, resp.) then the vertices \(v_{i},v_{j}\) are non-adjacent (adjacent, resp.) in \(G\), whereas the vertices corresponding to the leaves of a subtree rooted at a 2-node induce a spider. The structure of the \(P_{4}\)-sparse tree implies the following lemma. Lemma 4: _Let \(G\) be a \(P_{4}\)-sparse graph and let \(H=(S,K,R)\) be a thin spider of \(G\). Moreover, let \(s\in S\) and \(k\in K\) be vertices that are adjacent in the spider._  
* _Every vertex of the spider is adjacent to all vertices in_ \(N_{G}(s)\setminus\{k\}\)_._
* _Every vertex_ \(z\in K\setminus\{k\}\) _is adjacent to all vertices in_ \(N_{G}(k)\setminus\{s,z\}\)_._  
Let \(G\) be a given graph to which we want to add the tail \(uw\) with \(u\in V(G)\). Let \(t_{0}t_{1}\cdots t_{h}u\) be the path from the root \(t_{0}\) of the \(P_{4}\)-sparse tree \(T_{G}\) of \(G\) to the leaf associated with \(u\). Moreover, let \(V_{i}\) (\(0\leq i<h\)) be the set of vertices associated with the leaves of the subtrees rooted at the children of \(t_{i}\) except for \(t_{i+1}\), and \(V_{h}\) be the set of vertices associated with the leaves of the subtrees rooted at the children of \(t_{h}\) except for the leaf associated with \(u\) (see Figure 5). The sets \(V_{0},V_{1},\ldots,V_{h}\) form a partition of \(V(G)\setminus\{u\}\). We show that there always exists a minimum \(P_{4}\)-sparse completion of the graph \(G+uw\) in which \(u\) and \(w\) appear together in a small number of different formations. Lemma 5: _Let \(G\) be a \(P_{4}\)-sparse graph and \(T_{G}\) be its \(P_{4}\)-sparse tree. Consider the addition of a tail \(uw\) incident on a node \(u\) of \(G\).