Disjoint homometric sets in graphs

Michael O. Albertson, Janos Pach, Michael E. Young


Two subsets of vertices in a graph are called homometric if the multisets of distances determined by them are the same. Let h(n) denote the largest number h such that any connected graph of n vertices contains two disjoint homometric subsets of size h. It is shown that (c log n)/(log log n) < h(n) < n/4, for n > 3.


Graph distances, homometric subsets, Golumb ruler

Full Text:


DOI: https://doi.org/10.26493/1855-3974.174.027

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications