A Note on Steiner-Distance-Hereditary Graphs

Abstract

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\ge 2$ and $d\ge 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.