Vertex-removal, vertex-addition and different notions of similarity for vertices of a graph. Issue 20 (19th December 2022)

• Record Type: Journal Article
• Authors: Seeger, Alberto; Sossa, David
• Is Part Of: Linear & multilinear algebra. Volume 70:Issue 20(2022)
• Page Start: 5173
• Page End: 5192
• Publication Date: 2022-12-19
• Subjects: Similarity between vertices -- vertex-deleted subgraph -- vertex-addition -- spectral radius -- cospectral graphs -- degree sequence -- complementarity eigenvalue; 05C50 -- 15A42; Algebras, Linear -- Periodicals; Multilinear algebra -- Periodicals; 512.505
• DOI: 10.1080/03081087.2021.1908943
• Languages: English
• ISSNs: 0308-1087

Abstract

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.