2014/01/01 by Levit, Vadim E., Tankus, David
#05C69 (Primary) 05C85 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.1401.0294
A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space, denoted WCW(G). Let B be a complete bipartite induced subgraph of G on vertex sets of bipartition BX and BY. Then B is generating if there exists an independent set S such that S ∪ BX and S ∪ BY are both maximal independent sets of G. A relating edge is a generating subgraph in the restricted case that B = K1,1. Deciding whether an input graph G is well-covered is co-NP-complete. Therefore finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is co-NP-complete. Therefore, deciding whether a subgraph is generating is co-NP-complete as well. In this article we discuss the connections among these problems, provide proofs for NP-completeness for several restricted cases, and present polynomial characterizations for some other cases.