Please use this identifier to cite or link to this item:
Title: Vertex-decomposable graphs, codismantlability, cohen-macaulayness, and castelnuovo-mumford regularity
Authors: Bıyıkoğlu, Türker
Civan, Yusuf
Keywords: Edge rings
Vertex decomposable graphs
Induced matching
Cochordal cover number
Publisher: Electronic Journal of Combinatorics
Source: Bıyıkoğlu, T., and Civan, Y. (2014). Vertex-decomposable graphs, codismantlability, cohen-macaulayness, and castelnuovo-mumford regularity. Electronic Journal of Combinatorics, 21(1).
Abstract: We call a vertex x of a graph G = (V, E) a codominated vertex if NG[y] ⊆ NG[x] for some vertex y ∈ V \{x}, and a graph G is called codismantlable if either it is an edgeless graph or it contains a codominated vertex x such that G - x is codismantlable. We show that (C4, C5)-free vertex-decomposable graphs are codismantlable, and prove that if G is a (C4, C5, C7)-free well-covered graph, then vertex-decomposability, codismantlability and Cohen-Macaulayness for G are all equivalent. These results complement and unify many of the earlier results on bipartite, chordal and very well-covered graphs. We also study the Castelnuovo-Mumford regularity reg(G) of such graphs, and show that reg(G) = im(G) whenever G is a (C4, C5)-free vertex-decomposable graph, where im(G) is the induced matching number of G. Furthermore, we prove that H must be a codismantlable graph if im(H) = reg(H) = m(H), where m(H) is the matching number of H. We further describe an operation on digraphs that creates a vertex-decomposable and codismantlable graph from any acyclic digraph. By way of application, we provide an infinite family Hn (n ≥ 4) of sequentially Cohen-Macaulay graphs whose vertex cover numbers are half of their orders, while containing no vertex of degree-one such that they are vertex-decomposable, and reg(Hn) = im(Hn) if n ≥ 6. This answers a recent question of Mahmoudi, et al [12].
ISSN: 1077-8926
Appears in Collections:Mathematics / Matematik
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection

Files in This Item:
File Description SizeFormat 
5597.pdfMakale238.8 kBAdobe PDFThumbnail
Show full item record

CORE Recommender


checked on Mar 29, 2024

Page view(s)

checked on Apr 15, 2024


checked on Apr 15, 2024

Google ScholarTM


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.