On the displacement of eigenvalues when removing a twin vertex

DOI10.7151/DMGT.2274zbMATH Open1433.05187arXiv1904.05670OpenAlexW2940444477WikidataQ126533529 ScholiaQ126533529MaRDI QIDQ2295997FDOQ2295997

Authors: Johann A. Briffa, Irene Sciriha 

Publication date: 17 February 2020

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

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.

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

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

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)

Cites Work

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

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)