In this note we use eigenvalues of folded cubes to simplify all 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. (C) 1996 Academic Press, Inc. [References: 10]
展开▼
