The graph reconstruction number. (English) Zbl 0664.05043

The reconstruction number of graph G is the minimum number of point- deleted subgraphs required in order to uniquely identify the original graph G. We list, based on computer calculations, the reconstruction number for all graphs with at most seven points. Some constructions and conjectures for graphs of higher order are given. The most striking statement is our concluding conjecture that almost all graphs have reconstruction number three.


05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: DOI


[1] On the reconstruction of a graph from a collection of subgraphs. Theory of Graphs and Its Applications. Academic, New York (1964), p. 47–52.
[2] McKay, J. Graph Theory 1 pp 281– (1977)
[3] A Collection of Mathematical Problems. Wiley, New York, (1960), p. 29. · Zbl 0086.24101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.