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⊆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

Main Subjects

References

[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.
Transactions on Combinatorics
Volume 5, Issue 3 - Serial Number 3
September 2016
Pages 33-38

Files

History

  • Receive Date: 24 November 2014
  • Revise Date: 16 February 2016
  • Accept Date: 16 February 2016
  • Published Online: 01 September 2016

Share

How to cite

Statistics