| Relevant topics on |
| Graph connectivity |
|---|
Ingraph theory, a vertexsubset is avertex separator (orvertex cut,separating set) for nonadjacentverticesa andb if theremoval ofS from thegraph separatesa andb into distinctconnected components.
Consider agrid graph withr rows andc columns; the total numbern of vertices isr ×c. For instance, in the illustration,r = 5,c = 8, andn = 40. Ifr is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, ifc is odd, there is a single central column, and otherwise there are two columns equally close to the center. ChoosingS to be any of these central rows or columns, and removingS from the graph, partitions the graph into two smaller connected subgraphsA andB, each of which has at mostn⁄2 vertices. Ifr ≤c (as in the illustration), then choosing a central column will give a separatorS with vertices, and similarly ifc ≤r then choosing a central row will give a separator with at most vertices. Thus, every grid graph has a separatorS of size at most the removal of which partitions it into two connected components, each of size at mostn⁄2.[1]
To give another class of examples, everyfree treeT has a separatorS consisting of a single vertex, the removal of which partitionsT into two or more connected components, each of size at mostn⁄2. More precisely, there is always exactly one or exactly two vertices, which amount to such a separator, depending on whether the tree iscentered orbicentered.[2]
As opposed to these examples, not all vertex separators arebalanced, but that property is most useful for applications in computer science, such as theplanar separator theorem.
LetS be an(a,b)-separator, that is, a vertex subset that separates two nonadjacent verticesa andb. ThenS is aminimal(a,b)-separator if no proper subset ofS separatesa andb. More generally,S is called aminimal separator if it is a minimal separator for some pair(a,b) of nonadjacent vertices. Notice that this is different fromminimal separating set which says that no proper subset ofS is a minimal(u,v)-separator for any pair of vertices(u,v). The following is a well-known result characterizing the minimal separators:[3]
Lemma. A vertex separatorS inG is minimal if and only if the graphG –S, obtained by removingS fromG, has two connected componentsC1 andC2 such that each vertex inS is both adjacent to some vertex inC1 and to some vertex inC2.
The minimal(a,b)-separators also form analgebraic structure: For two fixed verticesa andb of a given graphG, an(a,b)-separatorS can be regarded as apredecessor of another(a,b)-separatorT, if every path froma tob meetsS before it meetsT. More rigorously, the predecessor relation is defined as follows: LetS andT be two(a,b)-separators inG. ThenS is a predecessor ofT, in symbols, if for eachx ∈S \T, every path connectingx tob meetsT. It follows from the definition that the predecessor relation yields apreorder on the set of all(a,b)-separators. Furthermore,Escalante (1972) proved that the predecessor relation gives rise to acomplete lattice when restricted to the set ofminimal(a,b)-separators inG.