\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Needs:
Set Differences
Chordal Graphs
Needed by:
Chordal Graphs and Vertex Separators
Links:
Sheet PDF
Graph PDF

Vertex Separators

Why

We characterize chordal graphs.1

Definition

Let $(V, E)$ be an undirected graph. A set $S \subset V$ is a vertex separator for two vertices $v, w$ (or a $vw$-separator) if $v$ and $w$ are disconnected in the subgraph induced by $V \setminus S$. There always exists a vertex separator for two nonadjacent vertices.

A vertex separator is a minimal vertex separator for two vertices if no proper subset of it is a vertex separator for those vertices. Another term for vertex separator is cutset. Similarly, one for minimal vertex separator is relatively minimal cutset.

Example

For example, for the graph in Figure below , $\set{c,e}$ is a minimal $ag$-separator and $\set{b,c,e}$ is a minimal $ad$-separator. A minimal vertex separator may contain another minimal vertex separator if they are minimal for different pairs of vertices.


  1. Future editions will expand. ↩︎
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view