Steiner intervals, geodesic intervals, and betweenness

The concept of the kk-Steiner interval is a natural generalization of the geodesic (binary) interval. It is defined as a mapping S:V×⋯×V⟶2VS:V×⋯×V⟶2V such that S(u1,…,uk)S(u1,…,uk) consists of all vertices in GG that lie on some Steiner tree with respect to a multiset W={u1,…,uk}W={u1,…,uk} of vertices from GG. In this paper we obtain, for each kk, a characterization of the class of graphs in which every kk-Steiner interval SS has the so-called union property, which says that S(u1,…,uk)S(u1,…,uk) coincides with the union of geodesic intervals I(ui,uj)I(ui,uj) between all pairs from WW. It turns out that, as soon as k>3k>3, this class coincides with the class of graphs in which the kk-Steiner interval enjoys the monotone axiom (m), respectively (b2) axiom, the conditions from betweenness theory. Notably, SS satisfies (m), if x1,…,xk∈S(u1,…,uk)x1,…,xk∈S(u1,…,uk) implies S(x1,…,xk)⊆S(u1,…,uk)S(x1,…,xk)⊆S(u1,…,uk), and SS satisfies (b2) if x∈S(u1,u2,…,uk)x∈S(u1,u2,…,uk) implies S(x,u2,…,uk)⊆S(u1,…,uk)S(x,u2,…,uk)⊆S(u1,…,uk). In the case k=3k=3, these three classes are different, and we give structural characterizations of graphs for which their Steiner interval SS 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.