Homometric sets in trees

Abstract

Let $G=(V,E)$ denote a simple graph with the vertex set $V$ and the edge set $E$. The profile of a vertex set $V^{\prime }\subseteq V$ denotes the multiset of pairwise distances between the vertices of $V^{\prime }$. Two disjoint subsets of $V$ are \emph{homometric}, if their profiles are the same. If $G$ is a tree on $n$ vertices we prove that its vertex sets contains a pair of disjoint homometric subsets of size at least $\sqrt{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 case of haircomb trees, in which we are able to find a pair of disjoint homometric sets of size at least $c{n}^{2/3}$ for a constant $c>0$.

Cited by in corpus (1)

• Twins in graphs