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.