Vertex-switching reconstruction and folded cubes (Q1924133)

We use eigenvalues of folded cubes to simplify an analogue of Kelly's lemma for vertex-switching reconstruction due to Krasikov and Roditty. Our new version states that the number of subgraphs (or induced subgraphs) of an \(n\)-vertex graph \(G\) isomorphic to a given \(m\)-vertex graph can be found from the \(s\)-vertex-switching deck of \(G\) provided the Krawtchouk polynomial \(K^n_s (x)\) has no even roots in \([0,m]\). This generalizes a condition of Stanley for \(s\)-vertex-switching reconstructibility. We also comment on the role of cubes and folded cubes in the theory of vertex-switching reconstruction.