Vertex-removal, vertex-addition and different notions of similarity for vertices of a graph. Issue 20 (19th December 2022) - Seeger, Alberto; Sossa, David
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.