Homometric sets in trees

Let G = (V, E) denote a simple graph with vertex set V and edge set E. The profile of a vertex set V' subset of V denotes the multiset of pairwise distances between the vertices of V'. Two disjoint subsets of V are homometric if their profiles are the same. If G is a tree on n vertices, we prove that its vertex set contains a pair of disjoint homometric subsets of size at least root n/2 - 1. Previously it was known that such a pair of size at least roughly n(1/3) exists. We get a better result in the case of haircomb trees, in which we are able to find a pair of disjoint homometric sets of size at least cn(2/3) for a constant c > 0. (C) 2013 Elsevier Ltd. All rights reserved.