Let $G$ be a finite, simple, connected, undirected graph on $n$ vertices. Suppose your goal is to determine $G$ uniquely via queries. Each query choses a $v_i$, and returns the shortest distances (number of edges) from $v_i$ to each other $v_j$, $j \neq i$. So, for a $4$-vertex graph, a $v_1$ query might return this (indices on 1st row, distances on 2nd row): $$ \left[ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 0 & 1 & 1 & 2 \\ \end{array} \right] $$

This data is compatible with graphs (a), (b), (c), (d) above, but not (e), because the distance from $v_1$ to $v_4$ should be $2$, not $1$. If now we query distances from $v_2$, and receive this information, $$ \left[ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 1 & 0 & 2 & 1 \\ \end{array} \right] $$ then only (a) and (c) are compatible. One more query seems necessary to pin down which.

Under the scenario where the user chooses each query after reviewing the results of the previous queries:

. Are there classes of graphs on $n$ vertices that require $n$ queries to pin down their structure?Q1

I believe if one knows the complete distance matrix, then the adjacency matrix is determined, and so $G$ is determined.

. Can sub-linear queries suffice for (a) some natural class of graphs (e.g, trees?), or (b) for some model of random graphs (e.g., Erdős-Rényi)?Q2

2more comments