Steiner intervals, geodesic intervals, and betweenness

The concept of the k -Steiner interval is a natural generalization of the geodesic (binary) interval. It is defined as a mapping S : V × ⋯ × V ⟶ 2 V such that S ( u 1 , … , u k ) consists of all vertices in G that lie on some Steiner tree with respect to a multiset W = { u 1 , … , u k } of vertices from G . In this paper we obtain, for each k , a characterization of the class of graphs in which every k -Steiner interval S has the so-called union property, which says that S ( u 1 , … , u k ) coincides with the union of geodesic intervals I ( u i , u j ) between all pairs from W . It turns out that, as soon as k > 3 , this class coincides with the class of graphs in which the k -Steiner interval enjoys the monotone axiom (m), respectively (b2) axiom, the conditions from betweenness theory. Notably, S satisfies (m), if x 1 , … , x k ∈ S ( u 1 , … , u k ) implies S ( x 1 , … , x k ) ⊆ S ( u 1 , … , u k ) , and S satisfies (b2) if x ∈ S ( u 1 , u 2 , … , u k ) implies S ( x , u 2 , … , u k ) ⊆ S ( u 1 , … , u k ) . In the case k = 3 , these three classes are different, and we give structural characterizations of graphs for which their Steiner interval S satisfies the union property as well as the monotone axiom (m). We also prove several partial observations on the class of graphs in which the 3-Steiner interval satisfies (b2), which lead to the conjecture that these are precisely the graphs in which every block is a geodetic graph with diameter at most two.