# Distance queries to reconstruct an unknown graph

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

• You need n-1 queries (or some not so unlucky guessing) to distinguish between the complete graph and the complete graph minus an edge. I think n guesses would yield redundant information. Gerhard "There's An App For That" Paseman, 2019.12.21. Commented Dec 22, 2019 at 2:05
• $n-1$ queries are enough: After querying the first $n-1$ vertices, we know which vertices among the first $n-1$ vertices are adjacent to the $n$th vertex, so the graph is complete determined. Commented Dec 22, 2019 at 4:12
• Let $G$ be a graph where $x$ and $y$ have the same set of neighbours. Let $H_x$ and $H_y$ be new graphs: $V(H_x)=V(G) \cup a$, and $E(H_x)=E(G) \cup (x,a)$, similarly for $V(H_y)$. Then one cannot tell $H_x$ from $H_y$ before querying $x$, $y$ or $a$. Commented Dec 22, 2019 at 4:28
• I added "connected." And added trees as a possible interesting class, because the distance matrix of a tree has special properties. Commented Dec 22, 2019 at 13:52
• For trees, note the "claw"-gulation: for each v, add u and w connected to v and add t connected to one of u or w. You need to query each claw (one of t,u, or w) to find its orientation, so n/4 queries minimum for the clawgulation of a tree. Gerhard "Has Found Favorite Mathematical Terminology" Paseman, 2019.12.22. Commented Dec 22, 2019 at 16:16