# Adding a Tail in Classes of Perfect Graphs
## 3 Split Graphs  
Split graphs were first studied by [PERSON] and [PERSON] [41] and independently introduced by [PERSON] and [PERSON] [42]; since then, they have been the focus of many research papers. An undirected graph \(G\) is _split_ if its vertex set \(V(G)\) admits a partition \(K\cup S\) such that \(K\) induces a clique and \(S\) induces an independent set [32; 43]; the partition into \(K,S\) can be computed in time proportional to the size of the graph [44]. It also holds that a graph is split if and only if it contains no induced \(C_{4}\), \(C_{5}\) or \(2K_{2}\). As a result of the definition, the complement and every induced subgraph of a split graph is split.  
Lemma 1: _Let \(G\) be a split graph with vertex partition into a clique \(K\) and an independent set \(S,u\) a vertex of \(G\), \(uw\) a tail and \(Q_{K,S}\) the set of vertices in \(K\) that have no neighbors in \(S\). Then, in a minimum split-completion of the graph \(G+uw\), the number of fill edges (excluding the tail \(uw\)) is \(0\) if \(u\in K\), \(|K|-deg_{G}(u)\) if \(u\in S\) and \(Q_{K,S}=\emptyset\) and \(|K|-1-deg_{G}(u)\) if \(u\in S\) and \(Q_{K,S}\
eq\emptyset\)._  
Proof: If \(u\in K\), no fill edge (in addition to \(uw\)) is needed, which is optimal, since \(G+uw\) is a split graph with clique \(K\) and independent set \(S\cup\{w\}\). Below, we consider that \(u\in S\).  
First, assume that \(Q_{K,S}=\emptyset\). A split completion of \(G+uw\) can be obtained by connecting \(u\) to all its non-neighbors in \(K\); the resulting graph is split with clique \(K\cup\{u\}\) and independent set \(S\cup\{w\}\). To prove its optimality, suppose for contradiction that there existed a split completion of \(G+uw\) that uses fewer than \(|K|-deg_{G}(u)\) fill edges. Then, there would exist a vertex \(a\in K\setminus N_{G}(u)\) which is not incident on any fill edge. If there existed one more vertex \(b\in K\setminus(N_{G}(u)\cup\{a\})\) not incident on any fill edge as well, then the edges \(ab\) and \(uw\) would form a \(2K_{2}\), a contradiction. Thus, all the fill edges would be incident on the vertices in \(K\setminus(N_{G}(u)\cup\{a\})\); note that these vertices induce a clique in \(G\). However, then, because \(Q_{K,S}=\emptyset\), there exists \(z\in S\cap N_{G}(a)\) and the edges \(az\) and \(uw\) would form a \(2K_{2}\), a contradiction again.  
Next assume that \(u\in S\) and \(Q_{K,S}\
eq\emptyset\); let \(p\) be any vertex in \(Q_{K,S}\). Then, the graph \(G\) is split with clique \(K^{\prime}=K\setminus\{p\}\) and independent set \(S^{\prime}=S\cup\{p\}\) and for each \(x\in K^{\prime}\), it holds that \(N_{G}(x)\cap S^{\prime}\
eq\emptyset\), which implies that \(Q_{K^{\prime},S^{\prime}}=\emptyset\). Then, from the case for \(u\in S\) and \(Q_{K,S}=\emptyset\), we conclude that the number of fill edges (excluding \(uw\)) in a minimum split-completion of \(G+uw\) is \(|K^{\prime}|-deg_{G}(u)=|K|-1-deg_{G}(u)\).  
We note that the above case is a special case of the minimum completion for the vertex addition case in [28].  
Lemma 1 directly implies that given a split partition of the given graph \(G\) with a _maximal_ independent set, the minimum number of fill edges can be computed in \(O(|V(G)|)\) time; otherwise, the time complexity is \(O(|V(G)|+|E(G)|)\).