Vertex separator

Consider a grid graph with rows and columns; the total number of vertices is . For instance, in the illustration, , , and . If is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing to be any of these central rows or columns, and removing from the graph, partitions the graph into two smaller connected subgraphs and , each of which has at most vertices. If (as in the illustration), then choosing a central column will give a separator with r \leq \sqrt{n} vertices, and similarly if then choosing a central row will give a separator with at most \sqrt{n} vertices. Thus, every grid graph has a separator of size at most \sqrt{n}, the removal of which partitions it into two connected components, each of size at most . To give another class of examples, every free tree has a separator consisting of a single vertex, the removal of which partitions into two or more connected components, each of size at most . More precisely, there is always exactly one or exactly two vertices, which amount to such a separator, depending on whether the tree is centered or bicentered. As opposed to these examples, not all vertex separators are balanced, but that property is most useful for applications in computer science, such as the planar separator theorem. ==Minimal separators==

Let be an -separator, that is, a vertex subset that separates two nonadjacent vertices and . Then is a minimal -separator if no proper subset of separates and . More generally, is called a minimal separator if it is a minimal separator for some pair of nonadjacent vertices. Notice that this is different from minimal separating set which says that no proper subset of is a minimal -separator for any pair of vertices . The following is a well-known result characterizing the minimal separators: Lemma. A vertex separator in is minimal if and only if the graph , obtained by removing from , has two connected components and such that each vertex in is both adjacent to some vertex in and to some vertex in . The minimal -separators also form an algebraic structure: For two fixed vertices and of a given graph , an -separator can be regarded as a predecessor of another -separator , if every path from to meets before it meets . More rigorously, the predecessor relation is defined as follows: Let and be two -separators in . Then is a predecessor of , in symbols S \sqsubseteq_{a,b}^G T, if for each , every path connecting to meets . It follows from the definition that the predecessor relation yields a preorder on the set of all -separators. Furthermore, proved that the predecessor relation gives rise to a complete lattice when restricted to the set of minimal -separators in . ==See also==