Extremal problems on Steiner k-distances

Hua Wang, Andrew Zhang

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)13-26
Number of pages14
JournalDiscrete Applied Mathematics
Volume365
DOIs
StatePublished - Apr 15 2025

Scopus Subject Areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Centroid
  • Extremal ratios
  • Median
  • Steiner distance

Fingerprint

Dive into the research topics of 'Extremal problems on Steiner k-distances'. Together they form a unique fingerprint.

Cite this