Pairwise Distance Similar Sets in Graphs

Abstract

Let $G=(V,E)$ be a connected graph. Two vertices $u$ and $v$ are said to be distance similar if $d(u,x)=d(v,x)$ for all $x\in V–\{u,v\}$. A nonempty subset $S$ of $V$ is called a pairwise distance similar set (in short `pds-set’) if either $|S|=1$ or any two vertices in $S$ are distance similar. The maximum (minimum) cardinality of a maximal pairwise distance similar set in $G$ is called the pairwise distance similar number (lower pairwise distance similar number) of $G$ and is denoted by $\mathrm{\Phi }(G)$ (${\mathrm{\Phi }}^{-}(G)$). The maximal pds-set with maximum cardinality is called a $\mathrm{\Phi }$-set of $G$. In this paper, we initiate a study of these parameters.