On pseudosimilarity in trees

Abstract

Two vertices u and v in a graph G are said to be removal-similar if G\u ≅ G\v. Vertices which are removal-similar but not similar are said to be pseudosimilar. A characterization theorem is presented for trees (later extended to forests and block graphs) with pseudosimilar vertices. It follows from this characterization that it is not possible to have three or more mutually pseudosimilar vertices in trees. Furthermore, removal-similarity combined with an extension of removal-similarity to include the removal of first neighbourhoods of vertices is sufficient to imply similarity in trees. Neither of these results holds, in general, if we replace trees by arbitrary graphs. © 1983.