Independence Complexes of Well-Covered Circulant Graphs

ABSTRACT

We study the independence complexes of families of well-covered circulant graphs discovered by Boros–Gurvich–Milanič, Brown–Hoshino, and Moussi. Because these graphs are well-covered, their independence complexes are pure simplicial complexes. We determine when these pure complexes have extra combinatorial (e.g., vertex decomposable, shellable) or topological (e.g., Cohen–Macaulay, Buchsbaum) properties. We also provide a table of all well-covered circulant graphs on 16 or less vertices, and for each such graph, determine if it is vertex decomposable, shellable, Cohen–Macaulay, and/or Buchsbaum. A highlight of this search is an example of a graph whose independence complex is shellable but not vertex decomposable.

KEYWORDS:

• circulant graph
• well-covered graph
• independence complex
• vertex decomposable
• shellable
• Cohen–Macaulay
• Buchsbaum

2000 AMS Subject Classification:

• 05C75
• 05E45
• 13F55

Acknowledgments

We used the LaTeX code of [Eastman 14] to draw circulant graphs. We would like to thank Russ Woodroofe for answering some of our questions. We also thank the referee for useful suggestions and comments.

Funding

Research of the last two authors was supported in part by NSERC Discovery Grants 203336 and 2014-03898, respectively. Research of the first author was supported by NSERC USRA 344018.