paper

The Steiner diameter of a graph

arXiv:1509.02801

Abstract

The Steiner distance of a graph, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph $G$ of order at least $2$ and $S \subseteq V (G)$ , the \emph{Steiner distance} $d (S)$ among the vertices of $S$ is the minimum size among all connected subgraphs whose vertex sets contain $S$ . Let $n, k$ be two integers with $2 \leq k \leq n$ . Then the \emph{Steiner $k$ -eccentricity $e_{k} (v)$ } of a vertex $v$ of $G$ is defined by $e_{k} (v) = max {d (S) ∣ S \subseteq V (G), ∣ S ∣ = k, an d v \in S}$ . Furthermore, the \emph{Steiner $k$ -diameter} of $G$ is $s d ia m_{k} (G) = max {e_{k} (v) ∣ v \in V (G)}$ . In 2011, Chartrand, Okamoto and Zhang showed that $k - 1 \leq s d ia m_{k} (G) \leq n - 1$ . In this paper, graphs with $s d ia m_{3} (G) = 2, 3, n - 1$ are characterized, respectively. We also consider the Nordhaus-Gaddum-type results for the parameter $s d ia m_{k} (G)$ . We determine sharp upper and lower bounds of $s d ia m_{k} (G) + s d ia m_{k} (G)$ and $s d ia m_{k} (G) \cdot s d ia m_{k} (G)$ for a graph $G$ of order $n$ . Some graph classes attaining these bounds are also given.

14 pages