Cohen–Macaulay Circulant Graphs

Abstract

Let G be the circulant graph C _n (S) with , and let I(G) denote the edge ideal in the ring R = k[x ₁,…, x _n ]. We consider the problem of determining when G is Cohen–Macaulay, i.e, R/I(G) is a Cohen–Macaulay ring. Because a Cohen–Macaulay graph G must be well-covered, we focus on known families of well-covered circulant graphs of the form C _n (1, 2,…, d). We also characterize which cubic circulant graphs are Cohen–Macaulay. We end with the observation that even though the well-covered property is preserved under lexicographical products of graphs, this is not true of the Cohen–Macaulay property.

Key Words:

• Circulant graph
• Cohen–Macaulay
• Shellable
• Vertex decomposable
• Well-covered graph

2010 Mathematics Subject Classification:

• 13F55
• 13H10
• 05C75
• 05E45

ACKNOWLEDGMENTS

We thank Brydon Eastman for writing the \LaTeX code to produce circulant graphs. We also thank Jennifer Biermann, Alexander Engström, Russ Woodroofe, and the referee for their suggestions and comments. Research of the first two authors supported in part by NSERC Discovery Grants. Research of the third author supported by an NSERC USRA.

Notes

Communicated by I. Swanson.