𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vertex-switching, isomorphism, and pseudosimilarity

✍ Scribed by M. N. Ellingham

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
442 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 which G~s~ is isomorphic to G, a result with application to the vertex‐switching reconstruction problem. We use these results to construct pairs of vertex‐switching pseudosimilar vertices, nonsimilar vertices u and v in a graph G with G~{u}~ isomorphic to G~{v}~. We show that every such pair can be constructed by our methods.

📜 SIMILAR VOLUMES

Vertex-Switching Reconstruction and Fold
Vertex-Switching Reconstruction and Folded Cubes
✍ M.N. Ellingham 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 216 KB

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 foun

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