2
$\begingroup$

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] $$


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

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 22 '19 at 2:05
  • $\begingroup$ $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. $\endgroup$ Dec 22 '19 at 4:12
  • 1
    $\begingroup$ 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$. $\endgroup$ Dec 22 '19 at 4:28
  • $\begingroup$ I added "connected." And added trees as a possible interesting class, because the distance matrix of a tree has special properties. $\endgroup$ Dec 22 '19 at 13:52
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 22 '19 at 16:16
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I'll leave the formal details to others. However, the "-gulation" construction seems to allow modifications to cover both parts of Joseph's Q2, and that graphs which are triangulable in Joseph's sense may be only those which have few cycles, and those cycles being large. Gerhard "Has Been Around The Block" Paseman, 2019.12.21. $\endgroup$ Dec 22 '19 at 4:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.