Substitution closures of the split graphs and matrogenic graphs

Meeting Time: Mar. 9, 2010, 2:00-2:50pm

Abstract: To \emph{substitute} a graph $G$ for a vertex $v$ in a graph $H$ is to delete $v$ and make each of its neighbors in $H$ adjacent to every vertex of $G$. The substitution closure of a graph class $\mathcal{C}$ is the smallest graph class containing $\mathcal{C}$ that is closed under vertex substitutions. Motivated by a problem on degree sequences, we study the substitution closures of the classes of split graphs and matrogenic graphs, and we characterize these in terms of finite lists of forbidden induced subgraphs.