Vertex reconstruction in Cayley graphs

In this survey paper we review recent results on the vertex reconstruction problem (which is not related to Ulam’s problem) in Cayley graphs. The problem of reconstructing an arbitrary vertex xx from its rr-neighbors, that are, vertices at distance at most rr from xx, consists of finding the minimum restrictions on the number of rr-neighbors when such a reconstruction is possible. We discuss general results for simple, regular and Cayley graphs. To solve this problem for given Cayley graphs, it is essential to investigate their structural and combinatorial properties. We present such properties for Cayley graphs on the symmetric group Symn and the hyperoctahedral group Bn (the group of signed permutations) and overview the main results for them. The choice of generating sets for these graphs is motivated by applications in coding theory, computer science, molecular biology and physics.