Well-covered circulant graphs |
| |
Authors: | Jason Brown Richard Hoshino |
| |
Institution: | aDepartment of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia, Canada B3H 3J5 |
| |
Abstract: | 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. |
| |
Keywords: | Circulant graph Well-covered graph Independence polynomial Powers of cycles Cubic graphs |
本文献已被 ScienceDirect 等数据库收录! |