Timeline for Distance queries to reconstruct an unknown graph
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 23, 2019 at 2:26 | comment | added | Gerhard Paseman | If you don't care which of u and w is adjacent to t, then it might help. However, -gulation seems powerful enough to tackle isomorphism also: we know t is distance two from v, but we don't know without querying u or w if a path from v to t goes through one of those. Gerhard "May Still Need Maps App" Paseman, 2019.12.22. | |
| Dec 23, 2019 at 1:03 | comment | added | Joseph O'Rourke | @GerhardPaseman: "to find its orientation": Perhaps there are two versions of what constitutes "determining the graph." One up to isomorphism; another requiring exact labeling. | |
| Dec 22, 2019 at 16:16 | comment | added | Gerhard Paseman | 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. | |
| Dec 22, 2019 at 13:52 | comment | added | Joseph O'Rourke | I added "connected." And added trees as a possible interesting class, because the distance matrix of a tree has special properties. | |
| Dec 22, 2019 at 13:49 | history | edited | Joseph O'Rourke | CC BY-SA 4.0 |
added 10 characters in body
|
| Dec 22, 2019 at 4:28 | comment | added | LeechLattice | 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$. | |
| Dec 22, 2019 at 4:24 | answer | added | Gerhard Paseman | timeline score: 1 | |
| Dec 22, 2019 at 4:12 | comment | added | LeechLattice | $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. | |
| Dec 22, 2019 at 2:05 | comment | added | Gerhard Paseman | 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. | |
| Dec 22, 2019 at 1:54 | history | asked | Joseph O'Rourke | CC BY-SA 4.0 |