2022/01/26 by Konstantinova, Elena
#Cayley graphs #Reconstruction problems #pancake problem #sorting by reversals #the signed permutation group #the symmetric group
paper · doi:10.4230/dagsemproc.06201.11
In this report paper we collect recent results on the vertex reconstruction in Cayley graphs Cay(G,S). The problem is stated as the problem of reconstructing a vertex from the minimum number of its r-neighbors that are vertices at distance at most r from the unknown vertex. The combinatorial properties of Cayley graphs on the symmetric group Sn and the signed permutation group Bn with respect to this problem are presented. The sets of generators of S are specified by applications in coding theory, computer science, molecular biology and physics.