On Pseudo-Similar Vertices in Trees

ID
TR-81-03
Authors
David G. Kirkpatrick, Maria M. Klawe and D. G. Corneil
Publishing date
April 1981
Abstract

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.