Distance queries to reconstruct an unknown graph

Question

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:

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

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

Q2. 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)?

Answer 1

This is an intriguing question. From one query, one can establish a lot of nonedges: if two vertices differ in distance from a third by two or more, these two vertices are not neighbors. So it would seem from taking queries from a few "remote" vertices, one could determine a lot of nonedges and come close to determining the graph. However, "triangulating" a graph (in the sense I am about to introduce), means one can't triangulate a graph with a few distance observations in the sense Joseph asks. In particular, one needs at least n/3 queries.

Here is my sense of triangulation, which should work for any base graph, but start with a path for example of m vertices. We will make a graph of n=3m vertices by adding triangles to the original graph: for each vertex v, add a vertex u and w, and the only new edges are the triangle connecting u,v, and w; u and w connect to nothing else in the construction.

For each pair of u and w, you have to query one of them to see if there is an edge between them. All other queries "have to go through v", and will not be able to determine if u and w have such an edge. Thus you need n/3 queries to cover the triangles. By combining this idea with the comment, you can (K_d)-gulate a graph to force a large fraction of vertices to be queried to determine the graph. Of course, you can make it even more interesting by removing an edge from each K_d pendant.

Gerhard "Graph Zoo Has New Member" Paseman, 2019.12.21.