Abstract
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 dkT(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.
Original language | English |
---|---|
Pages (from-to) | 13-26 |
Number of pages | 14 |
Journal | Discrete Applied Mathematics |
Volume | 365 |
DOIs | |
State | Published - Apr 15 2025 |
Scopus Subject Areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics
Keywords
- Centroid
- Extremal ratios
- Median
- Steiner distance