A reconstruction problem related to balance equations

DOI10.1016/S0012-365X(96)00312-3MaRDI QIDQ1377699zbMATH OpenOpenAlexFDO

Authors Bhalchandra D. Thatte

Publication date 29 June 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0608080

zbMATH Keywords

decksedge reconstructabilityeigenvaluesJohnson graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: 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 M"uller's result on the edge reconstructibility 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'asz's result, one describing the constructed graph explicitly, (thus answering a question of Bondy), and another based on the eigenvalues of Johnson graph.

Recommendations

• A reconstruction problem related to balance equations. II: The general case
• Reconstruction from the deck of k-vertex induced subgraphs
• Size reconstructibility of graphs
• Reconstructing graphs from a deck of all distinct cards

Cites work

• A note on the line reconstruction problem
• Balance equations for reconstruction problems
• Graph reconstruction—a survey
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• The edge reconstruction hypothesis is true for graphs with more than n _2\,n edges
• Vertex-switching reconstruction of subgraph numbers and triangle-free graphs

Cited in

(1)

• A reconstruction problem related to balance equations. II: The general case

This page was built for publication: A reconstruction problem related to balance equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377699)