  Consider a graph $G$ which belongs to a graph class ${\cal C}$. We are
interested in connecting a node $w \not\in V(G)$ to $G$ by a single edge $u w$
where $u \in V(G)$; we call such an edge a \emph{tail}. As the graph resulting
from $G$ after the addition of the tail, denoted $G+uw$, need not belong to the
class ${\cal C}$, we want to compute a minimum ${\cal C}$-completion of $G+w$,
i.e., the minimum number of non-edges (excluding the tail $u w$) to be added to
$G+uw$ so that the resulting graph belongs to ${\cal C}$. In this paper, we
study this problem for the classes of split, quasi-threshold, threshold, and
$P_4$-sparse graphs and we present linear-time algorithms by exploiting the
structure of split graphs and the tree representation of quasi-threshold,
threshold, and $P_4$-sparse graphs.
