Shellability of Polyhedral Joins of Simplicial Complexes and Its Application to Graph Theory

Abstract

We investigate the shellability of the polyhedral join ${\mathcal{Z}}_M^{\ast }(K,L)$ of simplicial complexes $K,M$ and a subcomplex $L\subset K$. We give sufficient conditions and necessary conditions on $(K,L)$ for ${\mathcal{Z}}_M^{\ast }(K,L)$ being shellable. In particular, we show that for some pairs $(K,L)$, ${\mathcal{Z}}_M^{\ast }(K,L)$ becomes shellable regardless of whether $M$ is shellable or not. Polyhedral joins can be applied to graph theory as the independence complex of a certain generalized version of lexicographic products of graphs which we define in this paper. The graph obtained from two graphs $G,H$ by attaching one copy of $H$ to each vertex of $G$ is a special case of this generalized lexicographic product and we give a result on the shellability of the independence complex of this graph by applying the above results.

18 pages