×
Baker, Jonathan; Vander Meulen, Kevin N.; Van Tuyl, Adam

Shedding vertices of vertex decomposable well-covered graphs. (English) Zbl 1397.05138

Discrete Math. 341, No. 12, 3355-3369 (2018).
Summary: We focus our attention on well-covered graphs that are vertex decomposable. We show that for many known families of these vertex decomposable graphs, the set of shedding vertices forms a dominating set. We then construct three new infinite families of well-covered graphs, none of which have this property. We use these results to provide a minimal counterexample to a conjecture of R. H. Villarreal [Manuscr. Math. 66, No. 3, 277–293 (1990; Zbl 0737.13003)] regarding Cohen-Macaulay graphs.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
13C14 Cohen-Macaulay modules

Keywords:

well-covered graph; vertex decomposable graph; dominating set; shedding vertices; Cohen-Macaulay graph

Citations:

Zbl 0737.13003

Software:

Nauty; SimplicialComplexes; SimplicialDecomposability; nauty; EdgeIdeals; OEIS; Macaulay2
Cite Review PDF
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Number of connected graphs with n nodes.

References:

[1] Biermann, J.; Francisco, C.; Hà, T.; Van Tuyl, A., Colorings of simplicial complexes and vertex decomposability, J. Commut. Algebra, 7, 337-352, (2015) · Zbl 1328.05207
[2] Bıyıkoğlu, T.; Civan, Y., Vertex-decomposable graphs, codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford regularity, Electron. J. Combin., 21, (2014), paper 1.1 (17 pages) · Zbl 1305.13007
[3] Björner, A.; Wachs, M., Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc., 349, 3945-3975, (1997) · Zbl 0886.05126
[4] Cook II, D., Simplicial decomposability, J. Softw. Algebra Geom., 2, 20-23, (2010) · Zbl 1311.05002
[5] Cook II, D., Nauty in macaulay2, J. Softw. Algebra Geom., 3, 1-4, (2011) · Zbl 1311.05080
[6] Cook II, D.; Nagel, U., Cohen-Macaulay graphs and face vectors of flag complexes, SIAM J. Discrete Math., 26, 89-101, (2012) · Zbl 1245.05138
[7] Crupi, M.; Rinaldo, G.; Terai, N., Cohen-Macaulay edge ideal whose height is half the number of vertices, Nagoya Math. J., 201, 117-131, (2011) · Zbl 1227.05218
[8] Dochtermann, A.; Engström, A., Algebraic properties of edge ideals via combinatorial topology, Electron. J. Combin., 16, (2009), Research Paper 2 · Zbl 1161.13013
[9] Earl, J.; Vander Meulen, K. N.; Van Tuyl, A., Independence complexes of well-covered circulant graphs, Exp. Math., 25, 441-451, (2016) · Zbl 1339.05333
[10] Favaron, O., Very well covered graphs, Discrete Math., 42, 177-187, (1982) · Zbl 0507.05053
[11] Finbow, A.; Hartnell, B.; Nowakowski, R. J., A characterization of well covered graphs of girth \(5\) or greater, J. Combin. Theory Ser. B, 57, 44-68, (1993) · Zbl 0777.05088
[12] Francisco, C.; Hoefel, A.; Van Tuyl, A., Edgeideals: a package for (hyper)graphs, J. Softw. Algebra Geom., 1, 1-4, (2009) · Zbl 1311.13030
[13] D.R. Grayson, M.E. Stillman, Macaulay2, a software system for research in algebraic geometry. http://www.math.uiuc.edu/Macaulay2/; D.R. Grayson, M.E. Stillman, Macaulay2, a software system for research in algebraic geometry. http://www.math.uiuc.edu/Macaulay2/
[14] Herzog, J.; Hibi, T., (Monomial Ideals, GTM, vol. 260, (2011), Springer) · Zbl 1206.13001
[15] Hibi, T.; Higashitani, A.; Kimura, K.; O’Keefe, A. B., Algebraic study on cameron-Walker graphs, J. Algebra, 422, 257-269, (2015) · Zbl 1303.05218
[16] Hoang, D. T.; Minh, N. C.; Trung, T. N., Cohen-Macaulay graphs with large girth, J. Algebra Appl., 14, (2015), 16 pages · Zbl 1326.13010
[17] Jonsson, J., (Simplicial Complexes of Graphs, LNM, vol. 1928, (2008), Springer) · Zbl 1152.05001
[18] Mahmoudi, M.; Mousivand, A.; Crupi, M.; Rinaldo, G.; Terai, N.; Yassemi, S., Vertex decomposability and regularity of very well-covered graphs, J. Pure Appl. Algebra, 215, 2473-2480, (2011) · Zbl 1227.13017
[19] Moradi, S.; Khosh-Ahang, F., Expansion of a simplicial complex, J. Algebra Appl., 15, (2016), (15 pages) · Zbl 1338.13041
[20] Prisner, E.; Topp, J.; P. D., Vestergaard, well-covered simplicial, chordal and circular arc graphs, J. Graph Theory, 21, 113-119, (1996) · Zbl 0847.05062
[21] Provan, J. S.; Billera, L. J., Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res., 5, 576-594, (1980) · Zbl 0457.52005
[22] N.J.A. Sloane, (Ed.), The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org; N.J.A. Sloane, (Ed.), The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org · Zbl 1044.11108
[23] Van Tuyl, A., Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity, Arch. Math. (Basel), 93, 451-459, (2009) · Zbl 1184.13062
[24] Villarreal, R. H., Cohen-Macaulay graphs, Manuscripta Math., 66, 277-293, (1990) · Zbl 0737.13003
[25] Villarreal, R. H., Monomial algebras, (2001), Marcel Dekker · Zbl 1002.13010
[26] Woodroofe, R., Vertex decomposable graphs and obstructions to shellability, Proc. Amer. Math. Soc., 137, 3235-3246, (2009) · Zbl 1180.13031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.