{{Short description|Set of graph nodes which separate a given pair of nodes if removed}} {{Graph connectivity sidebar}} {{confused|cut vertex}}

In graph theory, a vertex subset {{tmath|S \subset V}} is a '''vertex separator''' (or '''vertex cut''', '''separating set''') for nonadjacent vertices {{mvar|a}} and {{mvar|b}} if the removal of {{mvar|S}} from the graph separates {{mvar|a}} and {{mvar|b}} into distinct connected components.

==Examples== thumb|240px|A separator for a grid graph. Consider a grid graph with {{mvar|r}} rows and {{mvar|c}} columns; the total number {{mvar|n}} of vertices is {{math|''r'' × ''c''}}. For instance, in the illustration, {{math|1=''r'' = 5}}, {{math|1=''c'' = 8}}, and {{math|1=''n'' = 40}}. If {{mvar|r}} is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if {{mvar|c}} is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing {{mvar|S}} to be any of these central rows or columns, and removing {{mvar|S}} from the graph, partitions the graph into two smaller connected subgraphs {{mvar|A}} and {{mvar|B}}, each of which has at most {{math|{{frac|''n''|2}}}} vertices. If {{math|''r'' ≤ ''c''}} (as in the illustration), then choosing a central column will give a separator {{mvar|S}} with <math>r \leq \sqrt{n}</math> vertices, and similarly if {{math|''c'' ≤ ''r''}} then choosing a central row will give a separator with at most <math>\sqrt{n}</math> vertices. Thus, every grid graph has a separator {{mvar|S}} of size at most <math>\sqrt{n},</math> the removal of which partitions it into two connected components, each of size at most {{math|{{frac|''n''|2}}}}.<ref name="g73">{{harvtxt|George|1973}}. 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>

[[Image:Centered tree.gif|right|frame|On the left a centered tree, on the right a bicentered one. The numbers show each node's eccentricity. ]]

To give another class of examples, every free tree {{mvar|T}} has a separator {{mvar|S}} consisting of a single vertex, the removal of which partitions {{mvar|T}} into two or more connected components, each of size at most {{math|{{frac|''n''|2}}}}. 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">{{harvtxt|Jordan|1869}}</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 separators== Let {{mvar|S}} be an {{math|(''a'',''b'')}}-separator, that is, a vertex subset that separates two nonadjacent vertices {{mvar|a}} and {{mvar|b}}. Then {{mvar|S}} is a ''minimal'' {{math|(''a'',''b'')}}-''separator'' if no proper subset of {{mvar|S}} separates {{mvar|a}} and {{mvar|b}}. More generally, {{mvar|S}} is called a ''minimal separator'' if it is a minimal separator for some pair {{math|(''a'',''b'')}} of nonadjacent vertices. Notice that this is different from ''minimal separating set'' which says that no proper subset of {{mvar|S}} is a minimal {{math|(''u'',''v'')}}-separator for any pair of vertices {{math|(''u'',''v'')}}. The following is a well-known result characterizing the minimal separators:<ref>{{harvtxt|Golumbic|1980}}.</ref>

'''Lemma.''' A vertex separator {{mvar|S}} in {{mvar|G}} is minimal if and only if the graph {{math|''G'' – ''S''}}, obtained by removing {{mvar|S}} from {{mvar|G}}, has two connected components {{math|''C''{{sub|1}}}} and {{math|''C''{{sub|2}}}} such that each vertex in {{mvar|S}} is both adjacent to some vertex in {{math|''C''{{sub|1}}}} and to some vertex in {{math|''C''{{sub|2}}}}.

The minimal {{math|(''a'',''b'')}}-separators also form an algebraic structure: For two fixed vertices {{mvar|a}} and {{mvar|b}} of a given graph {{mvar|G}}, an {{math|(''a'',''b'')}}-separator {{mvar|S}} can be regarded as a ''predecessor'' of another {{math|(''a'',''b'')}}-separator {{mvar|T}}, if every path from {{mvar|a}} to {{mvar|b}} meets {{mvar|S}} before it meets {{mvar|T}}. More rigorously, the predecessor relation is defined as follows: Let {{mvar|S}} and {{mvar|T}} be two {{math|(''a'',''b'')}}-separators in {{math|G}}. Then {{mvar|S}} is a predecessor of {{mvar|T}}, in symbols <math>S \sqsubseteq_{a,b}^G T</math>, if for each {{math|''x'' ∈ ''S'' \ ''T''}}, every path connecting {{mvar|x}} to {{mvar|b}} meets {{mvar|T}}. It follows from the definition that the predecessor relation yields a preorder on the set of all {{math|(''a'',''b'')}}-separators. Furthermore, {{harvtxt|Escalante|1972}} proved that the predecessor relation gives rise to a complete lattice when restricted to the set of ''minimal'' {{math|(''a'',''b'')}}-separators in {{mvar|G}}.

==See also==

* Chordal graph, a graph in which every minimal separator is a clique. * k-vertex-connected graph

==Notes== <references />

==References== *{{Cite journal | last1 = Escalante | first1 = F. | doi = 10.1007/BF02996932 | title = Schnittverbände in Graphen | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg | volume = 38 | pages = 199–220 | year = 1972 }} *{{citation | last = George | first = J. Alan | author-link = J. Alan George | doi = 10.1137/0710032 | issue = 2 | journal = SIAM Journal on Numerical Analysis | pages = 345–363 | title = Nested dissection of a regular finite element mesh | jstor = 2156361 | volume = 10 | year = 1973| bibcode = 1973SJNA...10..345G }}. *{{citation | last = Golumbic | first = Martin Charles | author-link = Martin Charles Golumbic | title = Algorithmic Graph Theory and Perfect Graphs | publisher = Academic Press | year = 1980 | isbn = 0-12-289260-7}}. *{{cite journal | last = Jordan | first = Camille | author-link = Camille Jordan | year = 1869 | title = Sur les assemblages de lignes | journal = Journal für die reine und angewandte Mathematik | volume = 70 | issue = 2 | pages = 185–190 | url = http://resolver.sub.uni-goettingen.de/purl?GDZPPN002153998 | language = fr }} *{{Cite book | title = Graph Separators, with Applications| first1=Arnold | last1=Rosenberg | author1-link = Arnold L. Rosenberg| first2=Lenwood | last2=Heath| series=Frontiers of Computer Science | year = 2002 | publisher = Springer| doi = 10.1007/b115747| isbn=0-306-46464-0 }}

{{DEFAULTSORT:Vertex Separator}} Category:Graph connectivity