Shellability, vertex decomposability, and lexicographical products of graphs

zbMATH Open1376.05171arXiv1505.02838MaRDI QIDQ4598367FDOQ4598367

Adam Van Tuyl, Kevin N. Vander Meulen

Publication date: 20 December 2017

Abstract: We investigate when the independence complex of $G[H]$, the lexicographical product of two graphs $G$ and $H$, is either vertex decomposable or shellable. As an application, we construct an infinite family of graphs with the property that every graph in this family has the property that the independence complex of each graph is shellable, but not vertex decomposable.

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

zbMATH Keywords

vertex decomposablecirculant graphsshellableindependence complex

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Combinatorial aspects of simplicial complexes (05E45) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55)

Cited In (6)

• Vertex decomposability, shellability and Cohen-Macaulayness of graphs upon graph operations
• Cohen-Macaulayness of two classes of circulant graphs
• Chordal graphs, higher independence and vertex decomposable complexes
• Shellability of polyhedral joins of simplicial complexes and its application to graph theory
• Betti numbers of some circulant graphs
• Vertex decomposable graphs and obstructions to shellability

This page was built for publication: Shellability, vertex decomposability, and lexicographical products of graphs

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