A new construction for vertex decomposable graphs

Abstract

Let G be a finite simple graph on the vertex set V(G) and let S⊆V(G). Adding a whisker to G at x means adding a new vertex y and edge xy to G where x∈V(G). The graph G∪W(S) is obtained from G by adding a whisker to every vertex of S. We prove that if G∖S is either a graph with no chordless cycle of length other than 3 or 5, chordal graph or C5, then G∪W(S) is a vertex decomposable graph.

Keywords

• vertex decomposable
• shellabel
• Cohen-Macaulay