paper

The Steiner (n-3)-diameter of a graph

arXiv:1703.03984

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$ and $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 Steiner \emph{ $k$ -diameter} of $G$ is $s d ia m_{k} (G) = max {e_{k} (v) ∣ v \in V (G)}$ . In 2011, Chartrand, Okamoto, Zhang showed that $k - 1 \leq s d ia m_{k} (G) \leq n - 1$ . In this paper, graphs with $s d ia m_{k} (G) = ℓ$ for $k = n, n - 1, n - 2, n - 3$ and $k - 1 \leq ℓ \leq n - 1$ are characterized, respectively.

19 pages. arXiv admin note: text overlap with arXiv:1703.01410