A REPRESENTATION DIAGRAM FOR MAXIMAL INDEPENDENT SETS OF A GRAPH

Let H = (V(H) E(H)) be a directed graph with distinguished vertices s and t. An st-path in H is a simple directed path starting from s and e nding at t. Let P(H) be defined as {S \ S is the set of vertices on an st-path in H (s and t are excluded)}. For an undirected graph G = (V( G),E(G)) with V(G) subset of or equal to V(H) - {s,t}, if the family o f maximal independent sets of G coincides with P(H), we call H an MIS- diagram for G. In this paper, we provide a necessary and sufficient co ndition for a directed graph to be an MIS-diagram for an undirected gr aph. We also show that an undirected graph G has an MIS-diagram iff G is a cocomparability graph. Based on the proof of the latter result, w e can construct an efficient algorithm for generating all maximal inde pendent sets of a cocomparability graph.