A note on 3-Steiner intervals and betweenness

The geodesic and geodesic interval, namely the set of all vertices lying on geodesics between a pair of vertices in a connected graph, is a part of folklore in metric graph theory. It is also known that Steiner trees of a (multi) set with kk (k>2k>2) vertices, generalize geodesics. In Brešar et al. (2009) [1], the authors studied the kk-Steiner intervals S(u1,u2,…,uk)S(u1,u2,…,uk) on connected graphs (k≥3k≥3) as the kk-ary generalization of the geodesic intervals. The analogous betweenness axiom (b2) and the monotone axiom (m) were generalized from binary to kk-ary functions as follows. For any u1,…,uk,x,x1,…,xk∈V(G)u1,…,uk,x,x1,…,xk∈V(G) which are not necessarily distinct, (b2)x∈S(u1,u2,…,uk)⇒S(x,u2,…,uk)⊆S(u1,u2,…,uk),(m)x1,…,xk∈S(u1,…,uk)⇒S(x1,…,xk)⊆S(u1,…,uk).The authors conjectured in Brešar et al. (2009) [1] that the 3-Steiner interval on a connected graph GG satisfies the betweenness axiom (b2)(b2) if and only if each block of GG is geodetic of diameter at most 2. In this paper we settle this conjecture. For this we show that there exists an isometric cycle of length 2k+12k+1, k>2k>2, in every geodetic block of diameter at least 3. We also introduce another axiom (b2(2)), which is meaningful only to 3-Steiner intervals and show that this axiom is equivalent to the monotone axiom.