Shellability, vertex decomposability, and lexicographical products of graphs

Kevin N Vander Meulen, Adam Van Tuyl


In this note we describe 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 show that there exists an infinite family of
graphs whose independence complexes are shellable but not vertex


independence complex, vertex decomposable, shellable, circulant graphs

Full Text:



A. Bjorner, M.L. Wachs, and V. Welker, Poset ber theorems, Trans. Amer. Math. Soc. 357 (2005), 1877-1899.

E. Boros, V. Gurvich, and M. Milanic, On CIS circulants, Discrete Math. 318 (2014), 78-95.

J. Brown and R. Hoshino, Well-covered circulant graphs, Discrete Math. 311 (2011), 244-251.

J. Earl, K.N. Vander Meulen, and A. Van Tuyl, Independence complexes of well-covered circulant graphs, Experimental Math. 25 (2016), no. 4, 441-451.

D.R. Grayson and M.E. Stillman, Macaulay 2, a software system for research in algebraic geometry,

R. Hoshino, Independence polynomials of circulant graphs, Ph.D. thesis, Dalhousie University, 2007.

S. Moradi and F. Khosh-Ahang, Expansion of a simplicial complex, J. Algebra Appl. 15 (2016), 165004 (15 pages).

J. Provan and L. Biller, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5 (1980), 576-594.

J. Topp and L. Volkmann, On the well-coveredness of products of graphs, Ars Combin. 33 (1992), 199-215.

K.N. Vander Meulen, A. Van Tuyl, and C. Watt, Cohen{Macaulay circulant graphs, Comm. Algebra 42 (2014), 1896-1910.

R. Woodroofe, Vertex decomposable graphs and obstructions to shellability, Proc. Amer. Math. Soc. 137 (2009), 3235-3246.


Contributions to Discrete Mathematics. ISSN: 1715-0868