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.