×

The ally-reconstruction number of a disconnected graph. (English) Zbl 0704.05036

The ally-reconstruction number of a graph G is the minimum number of vertex-deleted subgraphs required in order to identify G up to isomorphism. (This parameter was introduced by F. Harary and M. Plantholt [J. Graph Theory 9, No.4, 451-454 (1985; Zbl 0664.05043)] as the reconstruction number of a graph.) In the paper under review it is shown that a disconnected graph with at least two nonisomorphic components has ally-reconstruction number three. In addition, it is proved that the ally-reconstruction number of a disconnected graph with all components isomorphic is at most \(c+2\), where c is the order of a component.
Reviewer: T.Andreae

MSC:

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

Citations:

Zbl 0664.05043
PDFBibTeX XMLCite