Vertex separator

File:Grid separator.svg

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 $r\; \backslash leq\; \backslash sqrt\{n\}$ vertices, and similarly if {{math|c ≤ r}} then choosing a central row will give a separator with at most $\backslash sqrt\{n\}$ vertices. Thus, every grid graph has a separator {{mvar|S}} of size at most $\backslash 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 ]]

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.{{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.

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: 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\; \backslash 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 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}}.

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

• {{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