Technical Reports

The ICICS/CS Reading Room

UBC CS TR-81-03 Summary

On Pseudo-Similar Vertices in Trees, April 1981 David G. Kirkpatrick, Maria M. Klawe and D. G. Corneil

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

If you have any questions or comments regarding this page please send mail to