Adding a Tail in Classes of Perfect Graphs

Abstract

Consider a graph $G$ which belongs to a graph class $\mathcal{C}$. We are interested in connecting a node $w\notin V(G)$ to $G$ by a single edge $uw$ 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 $\mathcal{C}$, we want to compute a minimum $\mathcal{C}$-completion of $G+w$, 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}$. 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.