On homometric sets in graphs

Maria Axenovich, Lale Özkahya

Published 2012-03-06Version 1

For a vertex set $S\subseteq V(G)$ in a graph $G$, the {\em distance multiset}, $D(S)$, is the multiset of pairwise distances between vertices of $S$ in $G$. Two vertex sets are called {\em homometric} if their distance multisets are identical. For a graph $G$, the largest integer $h$, such that there are two disjoint homometric sets of order $h$ in $G$, is denoted by $h(G)$. We slightly improve the general bound on this parameter introduced by Albertson, Pach and Young (2010) and investigate it in more detail for trees and graphs of bounded diameter. In particular, we show that for any tree $T$ on $n$ vertices $h(T) \geq \sqrt[3]{n}$ and for any graph $G$ of fixed diameter $d$, $h(G) \geq cn^{1/ (2d-2)}$.