A Representation Diagram for Maximal Independent Sets of a Graph

Masakuni TAKI; Sumio MASUDA; Toshinobu KASHIWABARA

A Representation Diagram for Maximal Independent Sets of a Graph

Masakuni TAKI, Sumio MASUDA, Toshinobu KASHIWABARA

Full Text Views

0

Share
Cite this

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

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Masakuni TAKI, Sumio MASUDA, Toshinobu KASHIWABARA, "A Representation Diagram for Maximal Independent Sets of a Graph" in IEICE TRANSACTIONS on Fundamentals, vol. E81-A, no. 5, pp. 784-788, May 1998, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e81-a_5_784/_p

Copy

@ARTICLE{e81-a_5_784,
author={Masakuni TAKI, Sumio MASUDA, Toshinobu KASHIWABARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Representation Diagram for Maximal Independent Sets of a Graph},
year={1998},
volume={E81-A},
number={5},
pages={784-788},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - A Representation Diagram for Maximal Independent Sets of a Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 784
EP - 788
AU - Masakuni TAKI
AU - Sumio MASUDA
AU - Toshinobu KASHIWABARA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1998
AB - 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.
ER -