Shellability, vertex decomposability, and lexicographical products of graphs

Kevin N Vander Meulen, Adam Van Tuyl

Abstract


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
decomposable.

Keywords


independence complex, vertex decomposable, shellable, circulant graphs

Full Text:

PDF

References


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, http://www.math.uiuc.edu/Macaulay2/.

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