Convexity and HHD-Free Graphs
Feodor F. Dragan, Falk Nicolai, Andreas Brandstädt · SIAM Journal on Discrete Mathematics · 1999
It is well known that chordal graphs can be characterized via m-convexity. In this paper we introduce the notion of m 3 -convexity (a relaxation of m-convexity) which is closely related to semisimplicial ordering of graphs. We present new characterizations of HHD-free graphs via m 3 -convexity and obtain some results known from [B. Jamison and S. Olariu, Adv. Appl. Math., 9 (1988), pp. 364--376] as corollaries. Moreover, we characterize weak bipolarizable graphs as the graphs for which the family of all m 3 -convex sets is a convex geometry. As an application of our results we present a simple efficient criterion for deciding whether a HHD-free graph contains a r-dominating clique with respect to a given vertex radius function r.