RUS  ENG
Full version
JOURNALS // Moscow Mathematical Journal // Archive

Mosc. Math. J., 2004 Volume 4, Number 2, Pages 523–528 (Mi mmj159)

Weighted well-covered graphs and complexity questions

I. É. Zverovich

Rutgers, The State University of New Jersey

Abstract: A weighted graph $G$ is called well-covered if all its maximal independent sets have the same weight. Let $S$ be an independent set of $G$ (possibly, $S=\varnothing$). The subgraph $G-N[S]$ is called a co-stable subgraph of $G$. We denote by ${\rm CSub}(G)$ the set of all co-stable subgraphs of $G$ considered up to isomorphism. A class of weighted graphs $\mathscr P$ is called co-hereditary if it is closed under taking co-stable subgraphs, i.e., $G\in\mathscr P$ implies ${\rm CSub}(G)\subseteq\mathscr P$.
Note that the class $\mathscr{WWELL}$ of all weighted well-covered graphs is co-hereditary. We characterize $\mathscr{WWELL}$ 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.

Key words and phrases: Weighted well-covered graph, co-stable subgraph.

MSC: 05C85

Received: April 22, 2004

Language: English

DOI: 10.17323/1609-4514-2004-4-2-523-528



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025