The Steiner diameter of a graph

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 $Ssubseteq V(G)$‎, ‎the 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 $2leq kleq n$‎. ‎Then the Steiner‎ ‎$k$-eccentricity $e_k(v)$ of a vertex $v$ of $G$ is defined by‎ ‎$e_k(v)=max {d(S),|,Ssubseteq V(G)‎, |S|=k‎, and vin S‎‎}$‎. ‎Furthermore‎, ‎the Steiner $k$-diameter of $G$ is‎ ‎$sdiam_k(G)=max {e_k(v),| ‎vin V(G)}$‎. ‎In 2011‎, ‎Chartrand‎, ‎Okamoto and Zhang showed that $k-1leq sdiam_k(G)leq n-1$‎. ‎In this‎ ‎paper‎, ‎graphs with $sdiam_3(G)=2,3,n-1$ are characterized‎, ‎respectively‎. ‎We also consider the Nordhaus-Gaddum-type results for‎ ‎the parameter $sdiam_k(G)$‎. ‎We determine sharp upper and lower‎ ‎bounds of $sdiam_k(G)+sdiam_k(overline{G})$ and $sdiam_k(G)cdot‎ ‎sdiam_k(overline{G})$ for a graph $G$ of order $n$‎. ‎Some‎ ‎graph classes attaining these bounds are also given.