# Vertex separator > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Vertex_separator > Markdown URL: https://mediated.wiki/source/Vertex_separator.md > Source: https://en.wikipedia.org/wiki/Vertex_separator > Source revision: 1232758235 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Set of graph nodes which separate a given pair of nodes if removed}} {{Graph connectivity sidebar}} {{confused|cut vertex}} In [graph theory](/source/graph_theory), a vertex [subset](/source/subset) {{tmath|S \subset V}} is a '''vertex separator''' (or '''vertex cut''', '''separating set''') for nonadjacent [vertices](/source/Vertex_(graph_theory)) {{mvar|a}} and {{mvar|b}} if the [removal](/source/Graph_partition) of {{mvar|S}} from the [graph](/source/Graph_(discrete_mathematics)) separates {{mvar|a}} and {{mvar|b}} into distinct [connected component](/source/connected_component_(graph_theory))s. ==Examples== thumb|240px|A separator for a grid graph. Consider a [grid graph](/source/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 r \leq \sqrt{n} vertices, and similarly if {{math|''c'' ≤ ''r''}} then choosing a central row will give a separator with at most \sqrt{n} vertices. Thus, every grid graph has a separator {{mvar|S}} of size at most \sqrt{n}, the removal of which partitions it into two connected components, each of size at most {{math|{{frac|''n''|2}}}}.{{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. [[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.](/source/Eccentricity_(graph_theory)) ]] To give another class of examples, every [free tree](/source/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](/source/centered_tree) or [bicentered](/source/centered_tree).{{harvtxt|Jordan|1869}} 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](/source/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:{{harvtxt|Golumbic|1980}}. '''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](/source/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 S \sqsubseteq_{a,b}^G T, 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](/source/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](/source/complete_lattice) when restricted to the set of ''minimal'' {{math|(''a'',''b'')}}-separators in {{mvar|G}}. ==See also== * [Chordal graph](/source/Chordal_graph), a graph in which every minimal separator is a [clique](/source/Clique_(graph_theory)). * [k-vertex-connected graph](/source/k-vertex-connected_graph) ==Notes== ==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](/source/Journal_f%C3%BCr_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 --- Adapted from the Wikipedia article [Vertex separator](https://en.wikipedia.org/wiki/Vertex_separator) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Vertex_separator?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.