On pseudosimilarity in trees (Q791542): Difference between revisions

Two vertices u and v in a graph G are removal-similar if \(G\backslash u\) and \(G\backslash v\) are isomorphic. They are similar if there is an automorphism of G mapping u onto v. Clearly similar vertices in a graph are necessarily removal-similar, but the converse need not hold. Removal- similar vertices which are not similar are known as pseudosimilar. This interesting paper offers a new characterization of removal-similar vertices, from which it follows that it is not possible to have three or more pair-wise pseudosimilar vertices in a tree. This characterization is extended to forests and block-graphs. Amongst other results, it is also proved that if u and v are removal-similar vertices in a tree T and \(T\backslash N(u)\) is isomorphic to \(T\backslash N(v)\) then u and v are similar. (Here N(x) denotes the subgraph of T induced by x, together with all vertices adjacent to it.)