Vertex decomposability and regularity of very well-covered graphs

Original · EN

A graph G is well-covered if it has no isolated vertices and all the maximal independent sets have the same cardinality. If furthermore two times this cardinality is equal to |V(G)|, the graph G is called very well-covered. The class of very well-covered graphs contains bipartite well-covered graphs. Recently in CRT it is shown that a very well-covered graph G is Cohen-Macaulay if and only if it is pure shellable. In this article we improve this result by showing that G is Cohen-Macaulay if and only if it is pure vertex decomposable. In addition, if I(G) denotes the edge ideal of G, we show that the Castelnuovo-Mumford regularity of R/I(G) is equal to the maximum number of pairwise 3-disjoint edges of G. This improves Kummini's result on unmixed bipartite graphs.