A weighted graph G is called well-covered if all its maximal stable sets have the same weight. This common weight is the value of G. Let S be a stable set of G (possibly, $S = \emptyset$). The subgraph $G - N[S]$ is called a co-stable subgraph of G. We denote by Sub(G) the set of all co-stable subgraphs of G (considered up to isomorphism). A class of weighted graphs P is called co-hereditary if it is closed under taking co-stable subgraphs, i.e., $G \in \mathcal{P}$ implies ${\rm CSub}(G) \subseteq \mathcal{P}$.
We note that the class $\mathcal{WW}$ of all weighted well-covered graphs is co-hereditary and characterize $\mathcal{WW}$ in terms of forbidden co-stable subgraphs.
Then we use a reduction from Satisfiability to show that the following decision problems are NP-complete.
Decision Problem 1 (Co-Stable Subgraph).
Instance: A graph $G$ and a set $U \subseteq V(G)$ that induces
a subgraph $H$.
Question: Is $H$ a co-stable subgraph of $G$?
Decision Problem 2 (Co-Stable Subgraph $H$).
Instance: A graph $G$.
Question: Is $H$ a co-stable subgraph of $G$?
Let $\Delta(G)$ be the maximum vertex degree of a graph $G$.
We show that recognizing weighted well-covered graphs with bounded
$\Delta(G)$ can be done in polynomial time.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-06.ps.gz
DIMACS Home Page