A new construction for vertex decomposable graphs

Document Type: Research Paper


1 Department of Mathematics, Science and Research branch, Islamic Azad University, Tehran, Iran

2 Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran


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


Main Subjects

[1] L. J. Billera and J. S. Provan, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res, 5 no. 4 (1980) 576–594.
[2] A. Björner and M. Wachs, Shellable nonpure complexes and posets. I, Trans. Amer. Math. Soc., 348 no. 4 (1996) 1299–1327.
[3] A. Dochtermann and A. Engström, Algebraic properties of edge ideals via combinatorial topology, Elec-
tron.J.Combin., 16 no. 2 (2009) pp. 24.
[4] C. A. Francisco and H. T. H‘a, Whiskers and sequentially Cohen- Macaulay graphs, J. Combin. Theory Ser. A., 115 no. 2 (2008) 304–316.
[5] C. A. Francisco and A. Van Tuyl, Sequentially Cohen-Macaulay edge ideals, Proc. Amer. Math. Soc., 135 no. 8 (2007) 2327–2337.
[6] J. Herzog and T. Hibi, Monomial Ideals, Graduate Texts in Mathematics, 260, Springer-Verlag London, Ltd., London, 2011.
[7] R. H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math., 66 no. 3 (1990) 277–293.

[8] R. Woodroofe, vertex decomposable graphs and obstructions to shellability, Proc. Amer. Math. Soc., 137 no. 10 (2009) 3235–3246.