✦ LIBER ✦

Complexity results for well-covered graphs

✍ Scribed by Ramesh S. Sankaranarayana; Lorna K. Stewart

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 740 KB
Volume: 22
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230220304

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph with n 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 n/2. In this work, we study these graphs from an algorithmic complexity point of view. We show that well‐covered graph recognition is co‐NP‐complete and that several other problems are NP‐complete for well‐covered graphs. A number of these problems remain NP‐complete 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.

📜 SIMILAR VOLUMES

Very well covered graphs

✍ O. Favaron 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 481 KB

A gra~h is wen-covered if it has no isolated vertices and all the maximal stable (iadependent) sets have the same cardinality. If fm'thermore this cardinality is equal to ½n, where n is the order of, he graph, the graph is called 'veE¢ well covered'. The class of very well-covered graphs contains in

Well-Covered Claw-Free Graphs

✍ David Tankus; Michael Tarsi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 336 KB

Well-covered graphs and extendability

✍ Nathaniel Dean; Jennifer Zito 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 928 KB

The Structure of Well-Covered Graphs and

The Structure of Well-Covered Graphs and the Complexity of Their Recognition Problems

✍ David Tankus; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 449 KB

A graph is well-covered if all its maximal independent sets are of the same cardinality. Deciding whether a given graph is well-covered is known to be NP-hard in general, and solvable in polynomial time, if the input is restricted to certain families of graphs. We present here a simple structural ch

Subdivisions, parity and well-covered gr

Subdivisions, parity and well-covered graphs

✍ Caro, Yair 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 2 views

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm

ModelingK-coteries by well-covered graph

ModelingK-coteries by well-covered graphs

✍ Yamashita, Masafumi; Kameda, Tsunehiko (Tiko) 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 3 views

The concept of k-coterie is useful for achieving k-mutual exclusion in distributed systems. A graph is said to be well covered if any of its maximal independent sets is also maximum. We first show that a graph G is well covered with independence number k if and only if G represents the incidence rel