×

New problems of graph reconstruction. (English) Zbl 1105.05051

For a graph \(G\) and a vertex \(v\) in \(G\) let \(B_r(v,G)\) be the set of vertices at a distance at most \(r\) from \(v\). Can \(G\) be uniquely determined if we are only given the sets \(B_r(v,G)\) for all vertices \(v\) in \(G\)? And how large must a subset of \(B_r(v,G)\) be to enable us to identify the vertex \(v\)? This paper surveys known results connected with these and related reconstruction questions. This survey paper should be extremely useful for anyone interested in these questions or their applications to information transmission, computational chemistry or computational biology.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
92B05 General biology and biomathematics
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
94B25 Combinatorial codes
PDFBibTeX XMLCite