paper

Steiner Distance in Product Networks

arXiv:1703.01410 · doi:10.23638/DMTCS-20-2-8

Abstract

For a connected graph $G$ of order at least $2$ and $S \subseteq V (G)$ , the \emph{Steiner distance} $d_{G} (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_{G} (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 this paper, we investigate the Steiner distance and Steiner $k$ -diameter of Cartesian and lexicographical product graphs. Also, we study the Steiner $k$ -diameter of some networks.

29 pages, 4 figures