Generating subgraphs in chordal graphs
share
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 B_X and B_Y. Then B is generating if there exists an independent set S such that S ∪ B_X and S ∪ B_Y are both maximal independent sets of G. In the restricted case that a generating subgraph B is isomorphic to K_1,1, the unique edge in B is called a relating edge. Generating subgraphs play an important role in finding WCW(G). Deciding whether an input graph G is well-covered is co-NP-complete. Hence, finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is NP-complete. Therefore, deciding whether a subgraph is generating is NP-complete as well. A graph is chordal if every induced cycle is a triangle. It is known that finding WCW(G) can be done polynomially in the restricted case that G is chordal. Thus recognizing well-covered chordal graphs is a polynomial problem. We present a polynomial algorithm for recognizing relating edges and generating subgraphs in chordal graphs.
READ FULL TEXT