EQUAL DISTANCES BETWEEN EQUAL SETS OF VERTICES IN GRAPHS

Author:

Art\={u}ras DUBICKAS

2010 Mathematics Subject Classification:

05C12.

Keywords:

diameter, distance in graphs, homometric sets.

Abstract:

Let n,r,\ell be three integers satisfying r,\ell \geq 2 and r \ell \leq n. We are interested if every simple connected graph G with n vertices contains r disjoint subsets U_1,\ldots,U_r with \ell vertices each such that the list of \frac{\ell(\ell-1)}{2} distances between \ell vertices of U_j in the graph G is the same for every j, 1\leq j \leq r. In particular, we prove that such disjoint subsets exist if r \ell \leq (1-\eps) \frac{\log n}{\log \log n} for \eps>0 and n \geq n(\eps).

Download paper:

Dubi-2013

Vol. 8 (16), 2013