Vertex-removal, vertex-addition and different notions of similarity for vertices of a graph

Abstract

This work examines different notions of similarity for a pair u, v of vertices of a graph G. The considered similarity notions are either of removal type or attachment type. In the removal case, checking similarity between u and v is a matter of comparing the vertex-deleted subgraphs G-u and G-v according to a certain criterion (isomorphism, degree sequence, index, characteristic polynomial, complementarity spectrum, etc.). In the attachment case, we compare the expanded graphs G(u)1 and G(v)1 obtained by attaching a pendant vertex to u and v, respectively. The duality between vertex-removal and vertex-attachment serves as central axis for the exposition.