A note on 3-Steiner intervals and betweenness

作者：Changat Manoj; Lakshmikuttyamma Anandavally K; Mathews Joseph; Peterin Iztok; Narasimha Shenoi Prasanth G; Tepeh Aleksandra^*

来源：Discrete Mathematics, 2011, 311(22): 2601-2609.

DOI：10.1016/j.disc.2011.08.009

• Steiner interval
• Betweenness
• Geodetic graph

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 k(k > 2) vertices, generalize geodesics. In Bresar et al. (2009) [1], the authors studied the k-Steiner intervals S(u(1), u(2), ... , u(k)) on connected graphs (k >= 3) as the k-ary generalization of the geodesic intervals. The analogous betweenness axiom (b2) and the monotone axiom (m) were generalized from binary to k-ary functions as follows. For any u(1), ... , u(k), x, x(1), ... , x(k) is an element of V (G) which are not necessarily distinct,
(b2) x is an element of S(u(1), u(2), ... , u(k)) double right arrow S(x, u2, ... , u(k)) subset of S(u(1), u(2), ... , u(k)), (m) x(1), ... , x(k) is an element of S (u(1) , ... , u(k)) double right arrow S(x(1), ... , u(k)) subset of S(u(1), ... , u(k)).
The authors conjectured in Bresar et al. (2009) [1] that the 3-Steiner interval on a connected graph G satisfies the betweenness axiom (b2) if and only if each block of G 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 + 1, k > 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.

• 出版日期2011-11-28