Vertex decomposability and regularity of very well-covered graphs (Q635459): Difference between revisions

In the present article, a subclass of unmixed graphs, so-called very well-covered graphs, are studied. If a graph \(G\) is unmixed without isolated vertices, then the cardinality of a minimal vertex cover is at least half the number of vertices of \(G\). Motivated by this relation, a graph is called very well-covered if these two quantities are equal, which is the case e.g., for unmixed bipartite graphs without isolated vertices. Though, in general, for an unmixed graph vertex decomposability is stronger than shellability, which is stronger than Cohen-Macaulayness, the authors prove that for very well-covered graphs those properties are equivalent. The proof of this result uses a characterization of very well-covered Cohen-Macaulay graphs from [\textit{M. Crupi, G. Rinaldo} and \textit{N. Terai}, Nagoya Math. J. 201, 117--131 (2011; Zbl 1227.05218)]. In addition to the Cohen-Macaulay property, the authors investigate the Castelnuovo-Mumford regularity of the edge ideal of a very well-covered graph. It is known that for an arbitrary graph \(G\), this regularity is bounded below by the maximum cardinality of all pairwise 3-disjoint sets of edges in \(G\). In this article it is shown that for very well-covered graphs, these two numbers coincide. First, this is verified for Cohen-Macaulay graphs. For the general case, using a similar idea as \textit{M. Kummini} [J. Algebr. Comb. 30, No. 4, 429--445 (2009; Zbl 1203.13018)], a certain semi-directed graph is associated to a very well-covered graph which allows for the reduction to the Cohen-Macaulay case.