Loading...
Please wait, while we are loading the content...
Similar Documents
The $k$-Steiner radius and $k$-Steiner diameter of connected graphs for $k\geq 4$
| Content Provider | Semantic Scholar |
|---|---|
| Author | Reiswig, Josiah |
| Copyright Year | 2019 |
| Abstract | Given a connected graph $G=(V,E)$ and a vertex set $S\subset V$, the \textit{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 $v$ 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, $\operatorname{srad}_k(G)$, is called the $k$-radius of $G$ while the maximum $k$-eccentricity, $\operatorname{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 $G_k$ such that $\operatorname{sdiam}_k(G_k) = \frac{2(k+1)}{2k-1}\operatorname{srad}_k(G_k)$ and conjectured that for $k\geq 2$ $\operatorname{sdiam}_k(G) \leq \frac{2(k+1)}{2k-1}\operatorname{srad}_k(G)$ for any connected graphs $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 $\operatorname{sdiam}_k(G)\leq \frac{k+3}{k+1}\operatorname{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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://arxiv.org/pdf/1907.07658v2.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
