On vertex decomposability and regularity of graphs

Year 2023, , 205 - 212, 09.01.2023

Amir Mafı Dler Naderı Parasto Soufıvand

https://doi.org/10.24330/ieja.1217285

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

• H. N. Aziz, A. Mafi and F. Seyfpour, Bi-sequentially Cohen-Macaulay bipartite graphs, to appear in J. Algebra Appl., (2023).
• J. Earl, K. N. Vander Meulen and A. Van Tuyl, Independence complexes of well-covered circulant Graphs, Exp. Math., 25(4) (2016), 441-451.
• D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
• 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.
• J. Herzog and T. Hibi, Componentwise linear ideals, Nagoya Math. J., 153 (1999), 141-153.
• J. Herzog and T. Hibi, Monomial Ideals, Graduate Texts in Mathematics, 260, Springer-Verlag London, Ltd., London, 2011.
• H. Higashidaira, On the sequentially Cohen-Macaulay properties of almost complete multipartite graphs, Comm. Algebra, 45(6) (2017), 2478-2493.
• M. Katzmann, Characteristic-independence of Betti numbers of graph ideals, J. Combin. Theory Ser. A, 113(3) (2006), 435-454.
• 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.
• M. Kummini, Regularity, depth and arithmetic rank of bipartite edge ideals, J. Algebraic Combin., 30(4) (2009), 429-445.
• 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.
• 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.
• R. P. Stanley, Combinatorics and Commutative Algebra, Second edition, Progress in Mathematics, 41. Birkhäuser Boston, Inc., Boston, MA, 1996.
• A. Van Tuyl, Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity, Arch. Math. (Basel) 93(5) (2009), 451-459.
• R. H. Villarreal, Cohen-Macaulay graphs, Manuscripta Math., 66(3) (1990), 277-293.
• R. Woodroofe, Vertex decomposable graphs and obstructions to shellability, Proc. Amer. Math. Soc., 137(10) (2009), 3235-3246.
• X. Zheng, Resolutions of facet ideals, Comm. Algebra, 32(6) (2004), 2301-2324.