Helly Theorems for Dismantlable Graphs and Pseudo-Modular Graphs
H. -J. Bandelt, Henry Martyn Mulder · 1990
The geodesic convexity of a graph consists of all those subsets of the vertex-set which contain all geodesics (i.e., shortest paths) joining any two of its elements. The Helly number of this convexity is trivially bounded from below by the clique number (i.e., the size of a largest clique). We show that equality between the two numbers hold for graphs which are dismantlable (alias cop-win) or pseudo-modular. This generalizes previously known results for chordal graphs and distance-hereditary graphs, due to Čepoj, Duchet, Jamison and Nowakowski, respectively. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.