## DIMACS TR: 2001-06

## Weighted well-covered graphs and complexity questions

### Authors: I. E. Zverovich

**
ABSTRACT
**

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