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.