Vertex decomposability and regularity of very well-covered graphs

2010/06/06 by Mahmoudi, Mohammad, Mousivand, Amir, Crupi, Marilena +3 · 3 citations
#05C75 #13H10 #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics

paper · doi:10.48550/arxiv.1006.1087

Abstract

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 \citeCRT 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.

Cited by

• Cohen-Macauleyness of the Zero-Divisor Graph of a Boolean Poset
• Castelnuovo-Mumford Regularity and Combinatorial Invariants of Trees
• The Serre depth of Stanley-Reisner rings and the depth of their symbolic powers

Related

• On well-covered, vertex decomposable and Cohen-Macaulay graphs
• Shedding vertices of vertex decomposable graphs
• Well-covered and uniformly well-covered graphs
• Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity
• Very well-covered graphs by Betti splittings