Similarity reconstruction of trees (Q1062078)

Call the set of vertices which are similar to a given vertex the similarity class of that vertex. We shall consider a reconstruction type problem on the similarity classes of vertices in a graph. A conjecture on the similarity classes of a graph is presented and shown to be implied by the reconstruction conjecture. Finally the similarity class of vertex a in a tree T on n vertices is shown to be determined by the collection of subgraphs of T on at most \((n+1)/2\) vertices in which v is included and specified. Examples are given which show this result is best possible.