✦ LIBER ✦

Vertex-Switching Reconstruction and Folded Cubes

✍ Scribed by M.N. Ellingham

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 216 KB
Volume: 66
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0027

No coin nor oath required. For personal study only.

✦ Synopsis

In this note 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-vertexswitching 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.

📜 SIMILAR VOLUMES

Applications of balance equations to ver

Applications of balance equations to vertex switching reconstruction

✍ I. Krasikov 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 404 KB 👁 1 views

## Abstract A graph is called __s‐vertex switching reconstructible__ (__s__‐VSR) if it is uniquely defined, up to isomorphism, by the multiset of unlabeled graphs obtained by switching of all its __s__‐vertex subsets. We show that a graph with __n__ vertices is __n__/2‐VSR if __n__ = 0(mod 4), (__n

Complete binary trees in folded and enha

Complete binary trees in folded and enhanced cubes

✍ S.A. Choudum; R. Usha Nandini 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

Vertex-switching, isomorphism, and pseud

Vertex-switching, isomorphism, and pseudosimilarity

✍ M. N. Ellingham 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 442 KB

## Abstract A __vertex__‐__switching G__~__s__~ of a graph __G__ is obtained by deleting from __G__ all edges of __G__ with exactly one end in the set of vertices __S__, and then adding to __G__ all edges of the complement of __G__ with exactly one end in __S__. We characterize the situations in wh

Switching reconstruction of digraphs

✍ J. A. Bondy; F. Mercier 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB

On the Characterization of the Folded Jo

On the Characterization of the Folded Johnson Graphs and the Folded Halved Cubes by their Intersection Arrays

✍ Klaus Metsch 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 285 KB

Note on the reconstruction of vertex col

Note on the reconstruction of vertex colored graphs

✍ R. Taylor 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB 👁 2 views