Recognizing 𝐖_2 Graphs
share
Let G be a graph. A set S ⊆ V(G) is independent if its elements are pairwise non-adjacent. A vertex v ∈ V(G) is shedding if for every independent set S ⊆ V(G) ∖ N[v] there exists u ∈ N(v) such that S ∪{u} is independent. An independent set S is maximal if it is not contained in another independent set. An independent set S is maximum if the size of every independent set of G is not bigger than |S|. The size of a maximum independent set of G is denoted α(G). A graph G is well-covered if all its maximal independent sets are maximum, i.e. the size of every maximal independent set is α(G). The graph G belongs to class 𝐖_2 if every two pairwise disjoint independent sets in G are included in two pairwise disjoint maximum independent sets. If a graph belongs to the class 𝐖_2 then it is well-covered. Finding a maximum independent set in an input graph is an NP-complete problem. Recognizing well-covered graphs is co-NP-complete. The complexity status of deciding whether an input graph belongs to the 𝐖_2 class is not known. Even when the input is restricted to well-covered graphs, the complexity status of recognizing graphs in 𝐖_2 is not known. In this article, we investigate the connection between shedding vertices and 𝐖_2 graphs. On the one hand, we prove that recognizing shedding vertices is co-NP-complete. On the other hand, we find polynomial solutions for restricted cases of the problem. We also supply polynomial characterizations of several families of 𝐖_2 graphs.
READ FULL TEXT