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^{'} s u b s e t e q V

denotes the multiset of pairwise distances between the vertices of

V^{'}

. 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

s q r t 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

.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Homometric sets in trees