Constructing vertex decomposable graphs

Document Type : Research Paper


1 Department of Mathematics‎, ‎Science and Research‎ ‎branch‎, ‎Islamic Azad University(IAU)‎, ‎Tehran‎, ‎Iran.

2 Department of Mathematics‎, ‎University of Kurdistan‎, ‎P.O‎. ‎Box 66177-15175‎, ‎Sanadaj‎, ‎Iran‎.


‎Recently‎, ‎some techniques such as adding whiskers and attaching graphs to vertices of a given graph‎, ‎have been proposed for constructing a new vertex decomposable graph‎. ‎In this paper‎, ‎we present a new method for constructing vertex decomposable graphs‎. ‎Then we use this construction to generalize the result due to Cook and Nagel‎.


Main Subjects

A. Bjorner and M. Wachs, Shellable nonpure complexes and posets, I, Trans. Amer. Math. Soc. 348 (1996), no. 4, 1299--1327.
D. Cook II, U. Nagel, Cohen-Macaulay graph and face vector of ag complexes, SIAM J. Discrete Math. 26 (2012), no. 1, 89--101.
A. Dochtermann and A. Engstrom, Algebraic properties of edge ideals via combinatorial topology, Electron. J. Combin. 16 (2009), no. 2, Special volume in honor of Anders Bjorner, 24 pages.
D. Hang, N. C^ong Minh and T. Nam Trung, On the Cohen-Macaulay graphs and girth, preprint, (2013), arXiv:1204.5561v2, 16 pages.
T. Hibi, A. Higashitani, K. Kimura and A. B. O'Keefe, Algebraic study on Cameron Walker graphs, J. Algebra 422 (2015) 257--269.
A. Mousivand, S. A. S. Fakhari and S. Yassemi, A new construction for Cohen-Macaulay graphs, Comm. Algebra 43 (2015), no. 12, 5104--5112.
B. Randerath and L. Volkmann, A characterization of well covered block-cactus graphs, Australas. J. Combin. 9 (1994) 307--314.
J. Scott Provan and Louis J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5 (1980), no. 4, 576--594.
R. H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math. 66 (1990), no. 3, 277--293.
R.Woodroofe, Vertex decomposable graphs and obstructions to shellability, Proc. Amer. Math. Soc. 137 (2009), no. 10, 3235--3246.
Volume 42, Issue 4 - Serial Number 4
August 2016
Pages 809-817
  • Receive Date: 27 March 2015
  • Revise Date: 20 August 2016
  • Accept Date: 30 April 2015
  • First Publish Date: 01 August 2016