On the displacement of eigenvalues when removing a twin vertex

DOI10.7151/DMGT.2274MaRDI QIDQ2295997zbMATH OpenOpenAlexWikidataFDO

Authors Johann A. Briffa, Irene Sciriha

Publication date 17 February 2020

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1904.05670

zbMATH Keywords

eigenvaluesperturbationsthreshold graphnested split graphduplicate and co-duplicate vertices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: Twin vertices of a graph have the same open neighbourhood. If they are not adjacent, then they are called duplicates and contribute the eigenvalue zero to the adjacency matrix. Otherwise they are termed co-duplicates, when they contribute $-1$ as an eigenvalue of the adjacency matrix. On removing a twin vertex from a graph, the spectrum of the adjacency matrix does not only lose the eigenvalue $0$ or $-1$. The perturbation sends a rippling effect to the spectrum. The simple eigenvalues are displaced. We obtain a closed formula for the characteristic polynomial of a graph with twin vertices in terms of two polynomials associated with the perturbed graph. These are used to obtain estimates of the displacements in the spectrum caused by the perturbation.

Recommendations

• Deleting vertices and interlacing Laplacian eigenvalues
• The effect of removing a 2-downer edge or a cut 2-downer edge triangle for an eigenvalue
• Deleting vertices and interlacing of \(A_\alpha\) eigenvalues of a graph
• The change in multiplicity of an eigenvalue of a Hermitian matrix associated with the removal of an edge from its graph
• Eigenvalues and separation in graphs
• Eigenvalues of the derangement graph
• The change in multiplicity of an eigenvalue due to adding or removing edges
• Eigenvalue comparison theorems of the discrete Laplacians for a graph
• Eigenvalue multiplicity in triangle-free graphs
• Eigenvalues of the matching derangement graph

Cites work

• scientific article; zbMATH DE number 3659637 (Why is no real title available?)
• scientific article; zbMATH DE number 3668627 (Why is no real title available?)
• scientific article; zbMATH DE number 3482387 (Why is no real title available?)
• scientific article; zbMATH DE number 3216614 (Why is no real title available?)
• An introduction to the theory of graph spectra
• Another form of the transmission function
• Co-cliques and star complements in extremal strongly regular graphs
• Fast algorithms for indices of nested split graphs approximating real complex networks
• Interlacing eigenvalues and graphs
• Interlacing-extremal graphs
• More about singular line graphs of trees
• On the spectrum of threshold graphs
• Rank one perturbation and its application to the laplacian spectrum of a graph^∗
• Some spectral properties of cographs
• The main eigenvalues of a graph: a survey
• The spectral approach to determining the number of walks in a graph

Cited in

(4)

• Nullspace vertex partition in graphs
• Covering automorphisms and some eigenvalues of a graph
• Strong Cospectrality and Twin Vertices in Weighted Graphs
• Reconstruction from one labelled card and more

This page was built for publication: On the displacement of eigenvalues when removing a twin vertex

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2295997)