A Note on Steiner-Distance-Hereditary Graphs

In a graph, the Steiner distance of a set of vertices \(U\) is the minimum number of edges in a connected subgraph containing \(U\). For \(k \geq 2\) and \(d \geq k-1\), let \(S(k,d)\) denote the property that for all sets \(S\) of \(k\) vertices with Steiner distance \(d\), the Steiner distance of \(S\) is preserved in any induced connected subgraph containing \(S\). A \(k\)-Steiner-distance-hereditary (\(k\)-SDH) graph is one with the property \(S(k, d)\) for all \(d\). We show that property \(S(k, k)\) is equivalent to being \(k\)-SDH, and that being \(k\)-SDH implies \((k + 1)\)-SDH. This establishes a conjecture of Day, Oellermann and Swart.