Template:Short description Template:Graph connectivity sidebar Template:Confused
In graph theory, a vertex subset Template:Tmath is a vertex separator (or vertex cut, separating set) for nonadjacent vertices Template:Mvar and Template:Mvar if the removal of Template:Mvar from the graph separates Template:Mvar and Template:Mvar into distinct connected components.
ExamplesEdit
Consider a grid graph with Template:Mvar rows and Template:Mvar columns; the total number Template:Mvar of vertices is Template:Math. For instance, in the illustration, Template:Math, Template:Math, and Template:Math. If Template:Mvar is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if Template:Mvar is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing Template:Mvar to be any of these central rows or columns, and removing Template:Mvar from the graph, partitions the graph into two smaller connected subgraphs Template:Mvar and Template:Mvar, each of which has at most Template:Math vertices. If Template:Math (as in the illustration), then choosing a central column will give a separator Template:Mvar with <math>r \leq \sqrt{n}</math> vertices, and similarly if Template:Math then choosing a central row will give a separator with at most <math>\sqrt{n}</math> vertices. Thus, every grid graph has a separator Template:Mvar of size at most <math>\sqrt{n},</math> the removal of which partitions it into two connected components, each of size at most Template:Math.<ref name="g73">Template:Harvtxt. Instead of using a row or column of a grid graph, George partitions the graph into four pieces by using the union of a row and a column as a separator.</ref>
To give another class of examples, every free tree Template:Mvar has a separator Template:Mvar consisting of a single vertex, the removal of which partitions Template:Mvar into two or more connected components, each of size at most Template:Math. 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.<ref name="Jordan">Template:Harvtxt</ref>
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 separatorsEdit
Let Template:Mvar be an Template:Math-separator, that is, a vertex subset that separates two nonadjacent vertices Template:Mvar and Template:Mvar. Then Template:Mvar is a minimal Template:Math-separator if no proper subset of Template:Mvar separates Template:Mvar and Template:Mvar. More generally, Template:Mvar is called a minimal separator if it is a minimal separator for some pair Template:Math of nonadjacent vertices. Notice that this is different from minimal separating set which says that no proper subset of Template:Mvar is a minimal Template:Math-separator for any pair of vertices Template:Math. The following is a well-known result characterizing the minimal separators:<ref>Template:Harvtxt.</ref>
Lemma. A vertex separator Template:Mvar in Template:Mvar is minimal if and only if the graph Template:Math, obtained by removing Template:Mvar from Template:Mvar, has two connected components Template:Math and Template:Math such that each vertex in Template:Mvar is both adjacent to some vertex in Template:Math and to some vertex in Template:Math.
The minimal Template:Math-separators also form an algebraic structure: For two fixed vertices Template:Mvar and Template:Mvar of a given graph Template:Mvar, an Template:Math-separator Template:Mvar can be regarded as a predecessor of another Template:Math-separator Template:Mvar, if every path from Template:Mvar to Template:Mvar meets Template:Mvar before it meets Template:Mvar. More rigorously, the predecessor relation is defined as follows: Let Template:Mvar and Template:Mvar be two Template:Math-separators in Template:Math. Then Template:Mvar is a predecessor of Template:Mvar, in symbols <math>S \sqsubseteq_{a,b}^G T</math>, if for each Template:Math, every path connecting Template:Mvar to Template:Mvar meets Template:Mvar. It follows from the definition that the predecessor relation yields a preorder on the set of all Template:Math-separators. Furthermore, Template:Harvtxt proved that the predecessor relation gives rise to a complete lattice when restricted to the set of minimal Template:Math-separators in Template:Mvar.
See alsoEdit
- Chordal graph, a graph in which every minimal separator is a clique.
- k-vertex-connected graph
NotesEdit
<references />