Minimal Weak Separators of Chordal Graphs

Abstract

A minimal separator of a graph is an inclusion-minimal set of vertices whose removal disconnects some pair of vertices. We introduce a new notion of minimal weak separator of a graph, whose removal merely increases the distance between some pair of vertices.

The minimal separators of a chordal graph \(G\) have been identified with the edges of the clique graph of \(G\) that are in some clique tree, while we show that the minimal weak separators can be identified with the edges that are in no clique tree. We also show that the minimal weak separators of a chordal graph \(G\) can be identified with pairs of minimal separators that have nonempty intersection without either containing the other—in other words, the minimal weak separators can be identified with the edges of the overlap graph of the minimal separators of \(G\).