On vertex decomposability and regularity of graphs

Abstract

There are two motivating questions in [M. Mahmoudi, A. Mousivand, M. Crupi, G. Rinaldo, N. Terai and S. Yassemi, arXiv:1006.1087v1] and [M. Mahmoudi, A. Mousivand, M. Crupi, G. Rinaldo, N. Terai and S. Yassemi, J. Pure Appl. Algebra, 215(10) (2011), 2473-2480] about Castelnuovo-Mumford regularity and vertex decomposability of simple graphs. In this paper, we give negative answers to the questions by providing two counterexamples.

Keywords

• Vertex decomposable graph
• edge ideal
• Castelnuovo-Mumford regularity

References

1. H. N. Aziz, A. Mafi and F. Seyfpour, Bi-sequentially Cohen-Macaulay bipartite graphs, to appear in J. Algebra Appl., (2023).
2. J. Earl, K. N. Vander Meulen and A. Van Tuyl, Independence complexes of well-covered circulant Graphs, Exp. Math., 25(4) (2016), 441-451.
3. D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
4. H. T. Ha and A. Van Tuyl, Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers, J. Algebraic Combin., 27(2) (2008), 215-245.
5. J. Herzog and T. Hibi, Componentwise linear ideals, Nagoya Math. J., 153 (1999), 141-153.
6. J. Herzog and T. Hibi, Monomial Ideals, Graduate Texts in Mathematics, 260, Springer-Verlag London, Ltd., London, 2011.
7. H. Higashidaira, On the sequentially Cohen-Macaulay properties of almost complete multipartite graphs, Comm. Algebra, 45(6) (2017), 2478-2493.
8. M. Katzmann, Characteristic-independence of Betti numbers of graph ideals, J. Combin. Theory Ser. A, 113(3) (2006), 435-454.

9. F. Khosh-Ahang and S. Moradi, Regularity and projective dimension of the edge ideal of $C_5$-free vertex decomposable graphs, Proc. Amer. Math. Soc., 142(5) (2014), 1567-1576.
10. M. Kummini, Regularity, depth and arithmetic rank of bipartite edge ideals, J. Algebraic Combin., 30(4) (2009), 429-445.
11. M. Mahmoudi, A. Mousivand, M. Crupi, G. Rinaldo, N. Terai and S. Yassemi, Vertex decomposability and regularity of very well-covered graphs, arXiv:1006.1087v1.
12. M. Mahmoudi, A. Mousivand, M. Crupi, G. Rinaldo, N. Terai and S. Yassemi, Vertex decomposability and regularity of very well-covered graphs, J. Pure Appl. Algebra, 215(10) (2011), 2473-2480.
13. R. P. Stanley, Combinatorics and Commutative Algebra, Second edition, Progress in Mathematics, 41. Birkhäuser Boston, Inc., Boston, MA, 1996.
14. A. Van Tuyl, Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity, Arch. Math. (Basel) 93(5) (2009), 451-459.
15. R. H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math., 66(3) (1990), 277-293.
16. R. Woodroofe, Vertex decomposable graphs and obstructions to shellability, Proc. Amer. Math. Soc., 137(10) (2009), 3235-3246.
17. X. Zheng, Resolutions of facet ideals, Comm. Algebra, 32(6) (2004), 2301-2324.