Moscow Mathematical Journal
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mosc. Math. J.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Moscow Mathematical Journal, 2004, Volume 4, Number 2, Pages 523–528
DOI: https://doi.org/10.17323/1609-4514-2004-4-2-523-528
(Mi mmj159)
 

Weighted well-covered graphs and complexity questions

I. É. Zverovich

Rutgers, The State University of New Jersey
References:
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
Bibliographic databases:
MSC: 05C85
Language: English
Citation: I. É. Zverovich, “Weighted well-covered graphs and complexity questions”, Mosc. Math. J., 4:2 (2004), 523–528
Citation in format AMSBIB
\Bibitem{Zve04}
\by I.~\'E.~Zverovich
\paper Weighted well-covered graphs and complexity questions
\jour Mosc. Math.~J.
\yr 2004
\vol 4
\issue 2
\pages 523--528
\mathnet{http://mi.mathnet.ru/mmj159}
\crossref{https://doi.org/10.17323/1609-4514-2004-4-2-523-528}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2108448}
\zmath{https://zbmath.org/?q=an:1059.05101}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000208594700009}
Linking options:
  • https://www.mathnet.ru/eng/mmj159
  • https://www.mathnet.ru/eng/mmj/v4/i2/p523
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Moscow Mathematical Journal
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024