Shedding vertices of vertex decomposable well-covered graphs
| Autor: | Kevin N. Vander Meulen, Jonathan Baker, Adam Van Tuyl |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Conjecture Mathematics::Commutative Algebra 010102 general mathematics 0102 computer and information sciences 01 natural sciences Theoretical Computer Science Vertex (geometry) Combinatorics 010201 computation theory & mathematics Dominating set Discrete Mathematics and Combinatorics 0101 mathematics Minimal counterexample Mathematics |
| Zdroj: | Discrete Mathematics. 341:3355-3369 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2018.07.029 |
| Popis: | 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 Villarreal regarding Cohen–Macaulay graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect