Well-covered circulant graphs

作者：Brown Jason^*; Hoshino Richard

来源：Discrete Mathematics, 2011, 311(4): 244-251.

DOI：10.1016/j.disc.2010.11.007

• Circulant graph
• Well-covered graph
• Independence polynomial
• Powers of cycles
• Cubic graphs

A graph is well-covered if every independent set can be extended to a maximum independent set. We show that it is co-NP-complete to determine whether an arbitrary graph is well-covered, even when restricted to the family of circulant graphs. Despite the intractability of characterizing the complete set of well-covered circulant graphs, we apply the theory of independence polynomials to show that several families of circulants are indeed well-covered. Since the lexicographic product of two well-covered circulants is also a well-covered circulant, our partial characterization theorems enable us to generate infinitely many families of well-covered circulants previously unknown in the literature.

• 出版日期2011-2-28