On distinct distance sets in a graph (Q1377770): Difference between revisions

A set \(S\) of vertices in a graph \(G\) with \(|S|=s\) is a distinct distance set (DDset) if it has the property that every two distinct pairs of vertices of \(S\) are distinct distances apart. The maximum size of a DDset in a graph \(G\) is denoted by \(\text{DD} (G)\). Let \(\text{LB} (k)\) be the smallest value \(L\) for which there exist positive integers \(A\) and \(B\) with \(A+B=k\), \((A(A-1)+ B(B-1))/2 \leq\lfloor L/2 \rfloor\), and \(AB\leq \lceil L/2 \rceil\). Let \(B_1(K_k)\) denote the size of the Colomb ruler corresponding to \(k\). The authors provide a table of values for a Colomb ruler for various values of \(k\) as well as for the values of \(\text{LB} (k)\). Let \(d_m(G)\) be the diameter of \(G\). It is shown that if \(k\) is an integer, \(6\leq k\leq 18\), then there exists a tree \(T\) with \(\text{DD} (T)=k\) and \(d_m(T)= \text{LB} (k)<B_1 (K_k)\). It is shown that for \(k\leq 10\), the minimum order of a tree \(T\) with \(\text{DD} (T)=k\) is \(B_1(K_k)\).