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 \( \Phi(G) \) (\( \Phi^-(G) \)). The maximal pds-set with maximum cardinality is called a \( \Phi \)-set of \( G \). In this paper, we initiate a study of these parameters.