Isometric subgraphs for Steiner distance

Let G be a connected graph and ℓ   : E ( G ) → R +a length‐function on the edges of G . The Steiner distance sd G ( A ) of A  ⊆  V ( G ) within G is the minimum length of a connected subgraph of G containing A , where the length of a subgraph is the sum of the lengths of its edges. It is clear that every subgraph H  ⊆  G , endowed with the induced length‐function ℓ ∣ E ( H ) , satisfies sd H ( A ) ≥ sd G ( A ) for every A  ⊆  V ( H ). Given an integer k  ≥ 2, we call H  ⊆  G k‐isometric in G if equality is attained for every A  ⊆  V ( H ) with ∣ A ∣ ≤  k . A subgraph is fully isometric if it is k ‐isometric for every k ∈ N . It is easy to construct examples of graphs H  ⊆  G such that H is k ‐isometric, but not ( k  + 1)‐isometric, so this defines a strict hierarchy of properties. We are interested in situations in which this hierarchy collapses in the sense that if H  ⊆  G is k ‐isometric, then H is already fully isometric in G . Our first result of this kind asserts that if T is a tree and T  ⊆  G is 2‐isometric with respect to some length‐function ℓ , then it is fully isometric. This fails for graphs containing a cycle. We then prove that if C is a cycle and C  ⊆  G is 6‐isometric, then C is fully isometric. We present an example showing that the number 6 is indeed optimal. We then develop a structural approach toward a more general theory and present several open questions concerning the big picture underlying this phenomenon.