Minimal Separators
Let S be an (a,b)-separator, that is, a vertex subset that separates two nonadjacent vertices a and b. Then S is a minimal (a,b)-separator if no proper subset of S separates a and b. More generally, S is called a minimal separator if it is a minimal separator for some pair (a,b) of nonadjacent vertices. The following is a well-known result characterizing the minimal separators:
Lemma. A vertex separator S in G is minimal if and only if the graph, obtained by removing S from G, has two connected components and such that each vertex in S is both adjacent to some vertex in and to some vertex in .
The minimal separators also form an algebraic structure: For two fixed vertices a and b of a given graph G, an (a,b)-separator S can be regarded as a predecessor of another (a,b)-separator T, if every path from a to b meets S before it meets T. More rigorously, the predecessor relation is defined as follows: Let S and T be two (a,b)-separators in 'G'. Then S is a predecessor of T, in symbols, if for each, every path connecting x to b meets T. It follows from the definition that the predecessor relation yields a preorder on the set of all (a,b)-separators. Furthermore, Escalante (1972) proved that the predecessor relation gives rise to a complete lattice when restricted to the set of minimal (a,b)-separators in G.
Read more about this topic: Vertex Separator
Famous quotes containing the word minimal:
“For those parents from lower-class and minority communities ... [who] have had minimal experience in negotiating dominant, external institutions or have had negative and hostile contact with social service agencies, their initial approaches to the school are often overwhelming and difficult. Not only does the school feel like an alien environment with incomprehensible norms and structures, but the families often do not feel entitled to make demands or force disagreements.”
—Sara Lawrence Lightfoot (20th century)