Vertex Decomposable Graph


N. Hajisharifi, S. Yassemi




Let $G$ be a simple graph on the vertex set $V(G)$ and $S=\{x_{11},\ldots,x_{n1}\}$ a subset of $V(G)$. Let $m_1,\ldots,m_n\geq 2$ be integers and $G_1,\ldots,G_n$ connected simple graphs on the vertex sets $V(G_i)=\{x_{i1},\ldots,x_{im_i}\}$ for $i=1,\ldots,n$. The graph $G(G_1,\ldots,G_n)$ is obtained from $G$ by attaching $G_i$ to $G$ at the vertex $x_{i1}$ for $i=1,\ldots,n$. We give a characterization of $G(G_1,\ldots,G_n)$ for being vertex decomposable. This generalizes a result due to Mousivand, Seyed Fakhari, and Yassemi.