Title | ||
---|---|---|
Vertex-decomposable Graphs, Codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford Regularity. |
Abstract | ||
---|---|---|
We call a vertex x of a graph G = (V, E) a codominated vertex if N-G[y] subset of N-G[x] for some vertex y is an element of 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 (C-4, C-5)-free vertex-decomposable graphs are codismantlable, and prove that if G is a (C-4, C-5, C-7)-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 (C-4, C-5)-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 H-n (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(H-n) = im(H-n) if n >= 6. This answers a recent question of Mahmoudi, et al [12]. |
Year | Venue | Keywords |
---|---|---|
2014 | ELECTRONIC JOURNAL OF COMBINATORICS | Cohen-Macaulay and sequentially Cohen-Macaulay graphs,vertex decomposable graphs,well-covered graphs,codismantlability,induced matching,co-chordal cover number,edge rings,Castelnuovo-Mumford regularity |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Indifference graph,Vertex (geometry),Interval graph,Vertex (graph theory),Chordal graph,Bipartite graph,Neighbourhood (graph theory),Pathwidth,Mathematics | Journal | 21.0 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 2 |
PageRank | References | Authors |
0.43 | 6 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Türker Bíyíkoglu | 1 | 88 | 7.40 |
Yusuf Civan | 2 | 7 | 2.73 |