A Characterization of all Stable Minimal Separator Graphs

Details A Characterization of all Stable Minimal Separator Graphs A Characterization of all Stable Minimal Separator Graphs

2011-03-15

arxiv.org/abs/1103.2913v1

Computer Science

Discrete Mathematics

Scientific paper

In this paper, our goal is to characterize two graph classes based on the properties of minimal vertex (edge) separators. We first present a structural characterization of graphs in which every minimal vertex separator is a stable set. We show that such graphs are precisely those in which the induced subgraph, namely, a cycle with exactly one chord is forbidden. We also show that deciding maximum such forbidden subgraph is NP-complete by establishing a polynomial time reduction from maximum induced cycle problem [1]. This result is of independent interest and can be used in other combinatorial problems. Secondly, we prove that a graph has the following property: every minimal edge separator induces a matching (that is no two edges share a vertex in common) if and only if it is a tree.

Affiliated with

Also associated with

No associations

Rating

A Characterization of all Stable Minimal Separator Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Characterization of all Stable Minimal Separator Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Characterization of all Stable Minimal Separator Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-139005