𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A reconstruction problem related to balance equations

✍ Scribed by Bhalchandra D. Thatte

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
273 KB
Volume
176
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A modified k-deck of a graph is obtained by removing k edges in all possible ways and adding k (not necessarily new) edges in all possible ways. Krasikov and Roditty used these decks to give an independent proof of Miiller's result on the edge reconstructability of graphs. They asked if a k-edge deck could be constructed from its modified k-deck. In this paper, we solve the problem when k -1. We also offer new proofs of Lov~sz's result, one describing the constructed graph explicitly (thus answering a question of Bondy), and another based on the eigenvalues of Johnson graph.

πŸ“œ 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