Pseudo-similarity in graphs
Speaker:
Antoine Poirier, University of Ottawa
Date and Time:
Friday, May 27, 2016 - 3:30pm to 3:50pm
Abstract:
If there exists an automorphism mapping a vertex u to a vertex v in a graph G, then u and v are said to be similar. If G−u is isomorphic to G−v, then u and v are said to be pseudo-similar. Analogous definitions can be made for edge deletion and edge contraction. Clearly, similarity implies pseudo-similarity. In this talk, we investigate why the converse implication is false. In 1982, Godsil and Kocay characterized pseudo-similar vertices and pseudo-similar edges for edge deletion, and we recently established a characterization in the context of edge contraction.