19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Steiner intervals, geodesic intervals and betweenness

Presented by Aleksandra TEPEH
Type: Oral presentation
Track: Metric Graph Theory


The concept of the $k$-Steiner interval is a natural generalization of the geodesic (binary) interval. It is defined as a mapping $S: V\times V\cdots V \rightarrow 2^{V}$ such that $S(u_1,\ldots, u_k)$ consists of all vertices in $G$ that lie on some Steiner tree with respect to a multiset $W=(u_1\ldots,u_k)$ of vertices from $G$. We will focus on the the following three axioms for the k-Steiner interval: (i) a graph has the {\em k-union property} if every k-multiset $W$ satisfies $S(W)=\cup _{u,v\in W}I(u,v)$, (ii) a graph satisfies the {\em betweenness axiom} (b2) if $x\in S(u_1,u_2,\ldots u_k)$ implies $S(x,u_2,\ldots,u_k)\subseteq (u_1,u_2,\ldots,u_k)$, (iii) a graph satisfies the {\em monotone axiom} (m) if $x_1,x_2,\ldots,x_k\in S(u_1,u_2,\ldots,u_k)$ implies $S(x_1,x_2,\ldots,x_k)\subseteq S(u_1,u_2,\ldots,u_k)$. Structural characterizations of graphs that satisfy the above axioms will be presented.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors