On a reconstruction problem of Harary and Manvel
type: Item
instance of: scholarly article
title: On a reconstruction problem of Harary and Manvel
zbMATH Open document ID: 1024.05063
author: Dieter Rautenbach
published in: Journal of Combinatorial Theory. Series A
publication date: 2003-03-26T00:00:00Z
review text: This paper is on the reconstruction of finite sets of points in the plane \(\mathbb{R}^2\). Two sets of points in the plane are considered isomorphic if one can be transformed into the other by a suitable translation and/or a rotation by a multiple of \(90^\circ\). The main result of this paper can be stated as follows. Let \(A,B\subseteq\mathbb{R}^2\) be two non-isomorphic finite sets and let \(\{a_1,\dots, a_n\}\subseteq A\) and \(\{b_1,\dots,b_n\}\subseteq B\) be such that \(A-\{a_i\}\approx B-\{b_i\}\) for \(1\leq i\leq n\). Then \(n\leq 4\). The author provides an example to show that this result is best possible. This result settles a combinatorial reconstruction problem posed by \textit{F. Harary} and \textit{B. Manvel} [Bull. Soc. Math. Belg. 24, 375-379 (1972; Zbl 0279.05128)]. The problem was to determine the reconstruction number for square-celled animals. A square-celled animal is a finite set of rookwise-connected squares in the plane that form a simply connected region, and a subanimal arises from an animal by deleting one square. Animals are considered isomorphic if one can be transformed into the other by translation and/or rotation. The reconstruction number of square-celled animals is the minimum number of subanimals (given up to isomorphism) that uniquely determine any square-celled animal up to isomorphism. Since there is a natural correspondence between square-celled animals and certain sets of points in the plane, the result proved in this paper implies that the reconstruction number for square-celled animals is 5.
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 1888398
zbMATH Keywords: reconstruction number
zbMATH Keywords: square-celled animal
reviewed by: Robert R. Molina
MaRDI profile type: Publication
OpenAlex ID: W1987248984
cites work: Q3975132
cites work: Q5544087
cites work: Q4404937
cites work: Q5682013
cites work: The graph reconstruction number
cites work: A congruence theorem for trees
cites work: Cell Growth Problems
cites work: Q4552214
cites work: Q5466062
cites work: Contributions to the Cell Growth Problem
cites work: Q3259049
DOI: 10.1006/JCTA.2002.3253
description: scientific article; zbMATH DE number 1888398