On pseudosimilarity in trees (Q791542)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On pseudosimilarity in trees |
scientific article |
Statements
On pseudosimilarity in trees (English)
0 references
1983
0 references
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.)
0 references
pseudosimilarity
0 references
removal-similar vertices
0 references