A Representation Diagram for Maximal Independent Sets of a Graph

Masakuni TAKI, Sumio MASUDA, Toshinobu KASHIWABARA

Summary :

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 ending at t. Let (H) be defined as { SS 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) V(H)- { s,t }, if the family of maximal independent sets of G coincides with (H), we call H an MIS-diagram for G. In this paper, we provide a necessary and sufficient condition for a directed graph to be an MIS-diagram for an undirected graph. 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, we can construct an efficient algorithm for generating all maximal independent sets of a cocomparability graph.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.5 pp.784-788
• Publication Date: 1998/05/25
• Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Authors

Masakuni TAKI
Sumio MASUDA
Toshinobu KASHIWABARA

Keyword

maximal independent set,  interval graph,  cocomparability graph,  generation problem