# Adding a Tail in Classes of Perfect Graphs
## 1 Introduction  
Given a graph \(G\), an edge connecting a vertex \(w\
ot\in V(G)\) to a vertex \(u\) of \(G\) is a tail added to \(G\); let us denote the resulting graph as \(G+uw\). If \(G\) belongs to a class \(\mathcal{C}\) of graphs, this need not hold for the graph \(G+uw\). Hence, we are interested in computing the number of non-edges of \(G\) in a minimum \(\mathcal{C}\)-completion of \(G+uw\), i.e., the minimum number of non-edges (excluding the tail \(uw\)) to be added to \(G+uw\) so that the resulting graph belongs to \(\mathcal{C}\); such non-edges are called fill edges. The problem is trivial for several graph classes (e.g., planar, bipartite, chordal, weakly chordal, [gem]-free, [house,hole,domino]-free, perfect graphs) but is not so for many other classes. Furthermore, we note that this problem is an instance of the more general \((\mathcal{C},+k)\)-MinEdgeAddition problem [1] in which we add \(k\) given non-edges in a graph belonging to a class \(\mathcal{C}\) and we want to compute a minimum \(\mathcal{C}\)-completion of the resulting graph.  
Computing a minimum completion of an arbitrary graph into a specific graph class is an important and well-studied problem with applications in areas involving graph modeling with missing edges due to lacking data, e.g., molecular biology and numerical algebra [2; 3]. Unfortunately, minimum completions into many interesting graph classes, such as split graphs, chordal graphs and cographs, are NP-hard to compute [4; 5; 6; 7; 8]. This led researchers towards the computation of minimal completions [9; 10; 11; 12; 13; 14; 15; 16], the solution of problems with restricted input [17; 18; 19; 20; 21], parameterized algorithms [22; 23; 24; 25] and approximation algorithms [26].  
A related field is that of the dynamic recognition (or on-line maintenance) problem on graphs: a series of requests for the addition or the deletion of an edge or a vertex (potentially incident on a number of edges) are submitted and each is executed only if the resulting graph remains in the same class of graphs. Several authors have studied this problem for different classes of graphs and have given algorithms supporting some or all the above operations [27; 28; 29; 30; 31].  
The motivation of our work is that many classes of perfect graphs arise quite naturally in real-world applications. More specifically, split, cographs, threshold, quasi-threshold, \(P_{4}\)-sparse graphs are used in computer storage optimization, analysis of genetic structure,information hiding, synchronization of parallel processes, etc [32]. The classes of threshold and quasi-threshold graphs find applications in set-packing problems, parallel processing and resource allocation problems [33; 34; 35]. The importance of the study of \(P_{4}\)-sparse graphs in practical applications is due to the fact that graphs that are unlikely to have more than a few chordless paths of length 3 appear in a number of contexts [36]; applications in scheduling, clustering and computational semantics have been the driving forces behind the study of \(P_{4}\)-sparse graphs, as well as their natural generalization of cographs, which have a nice tree structure and bounded clique width, implying efficient algorithms for several problems [37; 38; 39; 40].  
In this paper, we consider the tail addition problem, a special case of the general completion problem and we show that it admits minimum completions for the classes of split, threshold, quasi-threshold and \(P_{4}\)-sparse graphs. Given the \((K,S)\)-partition of a given split graph or the tree representation of a given quasi-threshold, threshold or \(P_{4}\)-sparse graph, our algorithms run in optimal \(O(n)\) time where \(n\) is the number of vertices of \(G\). These algorithms are a first step towards the solution of the \((\mathcal{C},+1)\)-MinEdgeAddition problem [1] for each of these four classes \(\mathcal{C}\) of graphs.