On pseudosimilarity in trees
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.)
- Some remarks on pseudotrees
- Similarity reconstruction of trees
- A characterization of dissimilarity families of trees
- Similarity and asymmetrization of trees
- scientific article; zbMATH DE number 4132180
- Tree approximation in quasi-trees
- Topologies on pseudo-trees and applications
- Finding similar consensus between trees: An algorithm and a distance hierarchy
- On dissimilarity vectors of general weighted trees
- scientific article; zbMATH DE number 1409202
- A Characterization of Block-Graphs
- Constructing graphs with pairs of pseudo-similar vertices
- Cospectral graphs and digraphs with given automorphism group
- scientific article; zbMATH DE number 3720954 (Why is no real title available?)
- scientific article; zbMATH DE number 3227794 (Why is no real title available?)
- scientific article; zbMATH DE number 3227795 (Why is no real title available?)
- scientific article; zbMATH DE number 3270498 (Why is no real title available?)
- Pseudosimilar vertices in a graph
- Similarity reconstruction of trees
- Interchanging branches and similarity in a tree
- Constructing graphs with several pseudosimilar vertices or edges
- Large sets of pseudosimilar vertices
- Retractions to Pseudoforests
- scientific article; zbMATH DE number 3933105 (Why is no real title available?)
- scientific article; zbMATH DE number 4097434 (Why is no real title available?)
- scientific article; zbMATH DE number 4128829 (Why is no real title available?)
- scientific article; zbMATH DE number 2095749 (Why is no real title available?)
- scientific article; zbMATH DE number 857660 (Why is no real title available?)
- Indistinguishable trees and graphs
- Reconstructing trees from two cards
- Vertex-removal, vertex-addition and different notions of similarity for vertices of a graph
- The degree-associated reconstruction number of an unicentroidal tree
- Regular Cayley maps for finite abelian groups
This page was built for publication: On pseudosimilarity in trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q791542)
