Given a connected graph $G=(V,E)$ and a vertex set $S\subset V$, the { \em Steiner distance} $d(S)$ of $S$ is the size of a minimum spanning tree of $S$ in $G$. For a connected graph $G$ of order $n$ and an integer $k$ with $2\leq k \leq n$, the $k$-eccentricity of a vertex $v$ in $G$ is the maximum value of $d(S)$ over all $S\subset V$ with $|S|=k$ and $v\in S$. The minimum $k$-eccentricity, ${ srad}_k(G)$, is called the $k$-radius of $G$ while the maximum $k$-eccentricity, ${ sdiam}_k(G)$, is called the $k$-diameter of $G$. In 1990, Henning, Oellermann, and Swart [\textit{ Ars Combinatoria} \textbf{ 12} 13-19, (1990)] showed that there exists a graph $H_k$ such that ${ sdiam}_k(H_k) = \frac{ 2(k+1)}{ 2k-1}srad_k(H_k)$. The authors also conjectured that for any $k\geq 2$ and connected graph $G$ ${ sdiam}_k(G) \leq \frac{ 2(k+1)}{ 2k-1}srad_k(G)$. The authors provided proofs of the conjecture for $k=3$ and $4$. Their proof for $k=4$, however, was incomplete. In this note, we disprove the conjecture for $k\geq 5$ by proving that the bound ${ sdiam}_k(G)\leq \frac{ k+3}{ k+1}{ srad}_k(G)$ is tight for $k\geq 5$. We then provide a complete proof for $k=4$ and identify the error in the previous proof of this case.
Categories: math.CO