{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T15:39:08Z","timestamp":1774625948068,"version":"3.50.1"},"reference-count":15,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5276,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1992,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A graph with <jats:italic>n<\/jats:italic> vertices is well covered if every maximal independent set is a maximum independent set and very well covered if every maximal independent set has size <jats:italic>n<\/jats:italic>\/2. In this work, we study these graphs from an algorithmic complexity point of view. We show that well\u2010covered graph recognition is co\u2010NP\u2010complete and that several other problems are NP\u2010complete for well\u2010covered graphs. A number of these problems remain NP\u2010complete on very well covered graphs, while some admit polynomial time solutions for the smaller class. For both families, the isomorphism problem is as hard as general graph isomorphism.<\/jats:p>","DOI":"10.1002\/net.3230220304","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T12:22:22Z","timestamp":1178972542000},"page":"247-262","source":"Crossref","is-referenced-by-count":69,"title":["Complexity results for well\u2010covered graphs"],"prefix":"10.1002","volume":"22","author":[{"given":"Ramesh S.","family":"Sankaranarayana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lorna K.","family":"Stewart","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"C.Berge Some common properties for regularizable graphs edge\u2010critical graphs and B\u2010graphs. Tohoku Univ. Tsuken Symp. on Graph Theory and Algorithms (October1980) 108\u2013123.","DOI":"10.1007\/3-540-10704-5_10"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"e_1_2_1_4_2","first-page":"215","article-title":"On well\u2010covered 3\u2010polytopes","volume":"25","author":"Campbell S. R.","year":"1988","journal-title":"Ars Combin."},{"key":"e_1_2_1_5_2","unstructured":"V.Chv\u00e1talandP. J.Slater A note on well\u2010covered graphs. Preprint."},{"key":"e_1_2_1_6_2","article-title":"Well covered graphs and extendability","author":"Dean N.","journal-title":"Discrete Math."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90215-1"},{"key":"e_1_2_1_8_2","first-page":"189","article-title":"A game related to covering by stars","volume":"16","author":"Finbow A.","year":"1983","journal-title":"Ars Combin."},{"key":"e_1_2_1_9_2","article-title":"A characterization of well covered graphs of girth 5 or greater","author":"Finbow A.","journal-title":"J. Combin. Theory B"},{"key":"e_1_2_1_10_2","unstructured":"A.Finbow B. L.Hartnell andR.Nowakowski A characterization of well covered graph which contain neither 4\u2010 nor 5\u2010cycles. Submitted."},{"key":"e_1_2_1_11_2","volume-title":"Computers and intractability\u2014A guide to the theory of NP\u2010completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_12_2","first-page":"239","volume-title":"Graph Theory and Combinatorics","author":"Lesk M.","year":"1984"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760842"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80011-4"},{"issue":"1","key":"e_1_2_1_15_2","first-page":"20","article-title":"Well covered graphs","volume":"2","author":"Ravindra G.","year":"1977","journal-title":"J. Combin. Info. Syst. Sci."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190030211"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230220304","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230220304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T08:49:57Z","timestamp":1698050997000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230220304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,5]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,5]]}},"alternative-id":["10.1002\/net.3230220304"],"URL":"https:\/\/doi.org\/10.1002\/net.3230220304","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,5]]}}}