Extremal problems on Steiner k-distances

The Steiner distance of a set of k vertices is a natural generalization of the regular distance between two vertices in a graph. We extend several theorems on the middle parts and extremal values of trees from their regular distance variants to their Steiner distance variants. More specifically, we show that for a tree T, the Steiner k-distance, Steiner k-leaf-distance, and Steiner k-internal-distance are all concave along a path. We also study distances between the Steiner k-median, Steiner k-internal-median, and Steiner k-leaf-median. Letting the Steiner k-distance of a vertex v∈V(T) be d_k^T(v), we find bounds based on the order of T for the ratios [Formula presented], [Formula presented], and [Formula presented] where u and v are leaves, w and z are internal vertices, and y is in the Steiner k-median. The extremal graphs that produce these bounds are also presented.