Vertex decomposability and regularity of very well-covered graphs (Q635459)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Vertex decomposability and regularity of very well-covered graphs
scientific article

    Statements

    Vertex decomposability and regularity of very well-covered graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    19 August 2011
    0 references
    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.
    0 references
    unmixed graph
    0 references
    Cohen-Macaulay
    0 references
    vertex-decomposable
    0 references
    Castelnuovo-Mumford regularity
    0 references
    independence complex
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references