Helly theorems for 3-Steiner and 3-monophonic convexity in graphs

AbstractA family C of sets has the Helly property if any subfamily C′ whose elements are pairwise intersecting has non-empty intersection. Suppose that C is a non-empty family of subsets of a finite set V: the Helly number h(C) of C is the least positive integer n such that every n-wise intersecting subfamily of C has non-empty intersection.In this paper the Helly property of families of convex sets relative to two new graph convexities are studied. Let G be a (finite) connected graph and U a set of vertices of G. A connected subgraph with the fewest edges containing U is called a Steiner tree for U, and the collection of all vertices of G that belong to some Steiner tree for U is called the Steiner interval for U. A set S of vertices of G is g3-convex if it contains the Steiner interval for every 3-subset U of S. A subtree T of G that contains U is a minimal U-tree if every vertex of T that is not in U is a cut-vertex of the subgraph induced by V(T). The set of all vertices that belong to some minimal U-tree is called the monophonic interval for U and a set S of vertices is m3-convex if it contains the monophonic interval of every 3-subset U of S. Those graphs are characterized for which the families of g3-convex (m3-convex) sets of size at least 3 have the Helly property. A graph obtained from a complete graph by deleting a matching is called a near-clique. The maximum order of a near-clique in a graph G is called the near-clique number of G. The near-clique number of a graph is a lower bound on the Helly number for both g3-convex families and m3-convex families. For m3-convex families equality holds. For g3-convex families equality holds for chordal graphs and for distance-hereditary graphs, but the bound can be arbitrarily bad in general, even when the near-clique number is 3