Boolean graphs are Cohen–Macaulay

ABSTRACT

For each Boolean graph B_n, it is proved that both B_n and its complement $\overline{B_n}$ are vertex decomposable. It is also proved that B_n is an unmixed graph, thus it is also Cohen–Macaulay.

KEYWORDS:

• Boolean graphs
• Cohen–Macaulay graphs
• unmixed graphs
• vertex decomposable graphs

2010 AMS CLASSIFICATION:

• Primary: 13H10
• 05E45
• Secondary: 13F55
• 05E40

Acknowledgments

The authors express their sincere thanks to the reviewer for the helpful comments and suggestions on an earlier version of this paper.