2017/03/29 by Weißauer, Daniel
#05C05 #05C12 #05C75 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1703.09969
Let G be a connected graph and ℓ : E(G) → ℝ+ a length-function on the edges of G. The Steiner distance sdG(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, with the induced length-function ℓ|E(H), satisfies sdH(A) ≥ sdG(A) for every A ⊆ V(H). We call H ⊆ G k-geodesic in G if equality is attained for every A ⊆ V(H) with |A| ≤ k. A subgraph is fully geodesic if it is k-geodesic for every k ∈ ℕ. It is easy to construct examples of graphs H ⊆ G such that H is k-geodesic, but not (k+1)-geodesic, 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-geodesic, then H is already fully geodesic in G. Our first result of this kind asserts that if T is a tree and T ⊆ G is 2-geodesic with respect to some length-function ℓ, then it is fully geodesic. This fails for graphs containing a cycle. We also prove that if C is a cycle and C ⊆ G is 6-geodesic, then C is fully geodesic. We present an example showing that the number six is indeed optimal. We then develop a structural approach towards a more general theory and present several open questions concerning the big picture underlying this phenomenon.