Graphs with Complete Minimal \(k\)-Vertex Separators

Abstract

Dirac characterized chordal graphs by every minimal \((2\)-)vertex separator inducing a complete subgraph. This generalizes to \(k\)-vertex separators and to a characterization of the class of \(\{P_5, 2P_3\}\)-free chordal graphs. The correspondence between minimal \(2\)-vertex separators of chordal graphs and the edges of their clique trees parallels a correspondence between minimal \(k\)-vertex separators of \(\{P_5, 2P_3\}\)-free chordal graphs and certain \((k-1)\)-edge substars of their clique trees.