IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

On the $k$-Steiner radius and $k$-Steiner Diameter of a graph with $k\geq 5$

  • March 22, 2019
  • 2:30 p.m.
  • LeConte 312

Abstract

Given a connected graph $G = (V, E)$ and a vertex set $S \subset V$ , the 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 V$ is the maximum value of $d(S)$ over all $S \subset V$ with $|S| = k$ and $v \in S$. The minimum $k$-eccentricity over $V$, $srad _ k(G)$, is called the Steiner $k$-radius of $G$ while the maximum $k$-eccentricity over $V$, $sdiam _ k(G)$ is called the Steiner $k$-diameter of G. In their 1990 paper ``On the Steiner Radius and Steiner Diameter of a Graph,'' Henning, Oellermann, and Swart conjectured that $sdiam _ k(G) \leq \frac{2(k+1)}{2k-1} srad _ k(G)$ for all $k\geq 3$. In this talk, we will show that for all $k\geq 5$ and connected graphs $G$, $sdiam _ k(G) \leq \frac{k+3}{k+1}srad _ k(G)$ and that this bound is tight.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC