2011/03/15 by Kumar, Mrinal, Maheswari, Gaurav, Sadagopan, N.
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1103.2913
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.