Distance Similar Sets in Graphs

Let G = (V, E) be a connected graph. A proper subset S of V is called a distance similar set if vertical bar{dist(u,v) : v is an element of S}vertical bar = 1 for all u E V S. A distance similar set S is called a maximal distance similar set if any set S-1 with S subset of S-l subset of V, is not a distance similar set of G. The maximum cardinality of a maximal distance similar set is called the distance similar number of G and is denoted by ds(G). The minimum cardinality of a maximal distance similar set in G is called the lower distance similar number of G and is denoted by ds (G). We present several fundamental results on these concepts and also an algorithm which computes ds(G) in O(n(4))-time. We also investigate the relation between distance similar number and other parameters.