A new construction for vertex decomposable graphs

Document Type: Research Paper

Authors

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

Abstract

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.

Keywords

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.