Shellability, vertex decomposability, and lexicographical products of graphs


  • Kevin N Vander Meulen Redeemer University College
  • Adam Van Tuyl McMaster University



independence complex, vertex decomposable, shellable, circulant graphs


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

Author Biography

Adam Van Tuyl, McMaster University

Department of Math & Stats

Associate Professor


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.