The Steiner $k$-radius and Steiner $k$-diameter of connected graphs for $k\ge 4$

Abstract

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\le k\le 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}sra{d}_k(H_k)$. The authors also conjectured that for any $k\ge 2$ and connected graph $G$ ${sdiam}_k(G)\le \frac{2(k+1)}{2k-1}sra{d}_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\ge 5$ by proving that the bound ${sdiam}_k(G)\le \frac{k+3}{k+1}{srad}_k(G)$ is tight for $k\ge 5$. We then provide a complete proof for $k=4$ and identify the error in the previous proof of this case.