Distance similar sets in graphs

Abstract

Let G = (V, E) be a connected graph. A proper subset S of V is called a distance similar set if |{dist(u,v) : v 6 S}| = 1 for all u ϵ V - S. A distance similar set S is called a maximal distance similar set if any set Si with S ⊂ S1 ⊂ 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(n4)-Time. We also investigate the relation between distance similar number and other parameters.