Pure simplicial complexes and well-covered graphs

DOI10.1216/RMJ-2015-45-2-695zbMATH Open1327.05150arXiv1104.4556OpenAlexW2962678536MaRDI QIDQ491349FDOQ491349

Authors: Rashid Zaare-Nahandi 

Publication date: 25 August 2015

Published in: Rocky Mountain Journal of Mathematics (Search for Journal in Brave)

Abstract: A graph $G$ is called well-covered if all maximal independent sets of vertices have the same cardinality. A simplicial complex $Delta$ is called pure if all of its facets have the same cardinality. Let $mathcalG$ be the class of graphs with some disjoint maximal cliques covering all vertices. In this paper, we prove that for any simplicial complex or any graph, there is a corresponding graph in class $mathcalG$ with the same well-coveredness property. Then some necessary and sufficient conditions are presented to recognize fast when a graph in the class $calG$ is well-covered or not. To do this characterization, we use an algebraic interpretation according to zero-divisor elements of the edge rings of graphs.

Full work available at URL: https://arxiv.org/abs/1104.4556

Recommendations

• Well covered simplicial, chordal, and circular arc graphs
• The structure of well-covered graphs and the complexity of their recognition problems
• WELL-COVERED GRAPHS: A SURVEY
• Complexity results for well‐covered graphs
• Characterization of \(Z_m\)-well-covered graphs for some classes of graphs

zbMATH Keywords

perfect graphwell-covered graphclique coverpure simplicial complex

Mathematics Subject Classification ID

Combinatorial aspects of commutative algebra (05E40) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Combinatorial aspects of simplicial complexes (05E45) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55)

Cited In (5)

• Perfect matching of 3-uniform hypergraphs
• Impure Simplicial Complexes: Complete Axiomatization
• Graphs vertex-partitionable into strong cliques
• Covers of simplicial complexes and applications to geometry
• Sortable simplicial complexes and \(t\)-independence ideals of proper interval graphs

This page was built for publication: Pure simplicial complexes and well-covered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491349)