A Generalized Steiner Distance for Graphs

Abstract

For a nonempty subset $S$ of vertices of a $k$-connected graph $G$ and for $1\le i\le k$, the Steiner $i$-distance $d_i(S)$ of $S$ is the minimum size among all $i$-connected subgraphs containing $S$. Relationships between Steiner $i$-distance and the connectivity and hamiltonian properties of a graph are discussed. For a $k$-connected graph $G$ of order $p$ and integers $i$ and $n$ with $1\le i\le k$ and $1\le n\le p$, the $(i,n)$-eccentricity of a vertex $v$ of $G$ is the maximum Steiner $i$-distance $d_i(S)$ of a set $S$ containing $v$ with $|S|=n$. The $(i,n)$-center $C_{i,n}(G)$ of $G$ is the subgraph induced by those vertices with minimum $(i,n)$-eccentricity. It is proved that for every graph $H$ and integers $i,n\ge 2$, there exists an $i$-connected graph $G$ such that $C_{i,n}(G)\cong H$.