|
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.
Received: April 22, 2004
Citation:
I. É. Zverovich, “Weighted well-covered graphs and complexity questions”, Mosc. Math. J., 4:2 (2004), 523–528
Linking options:
https://www.mathnet.ru/eng/mmj159 https://www.mathnet.ru/eng/mmj/v4/i2/p523
|
|