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.


Published in:
European Journal Of Combinatorics, 35, 256-263
Presented at:
6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb)', u'6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb)
Year:
2014
Publisher:
London, Academic Press Ltd- Elsevier Science Ltd
ISSN:
0195-6698
Laboratories:




 Record created 2014-01-09, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)