Convexity and HHD-free graphs

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 orderings 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 bipo larizable 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-dom inating clique with respect to a given vertex radius function r.