Authors: Simić, Slobodan 
Anđelić, Milica
Da Fonseca, Carlos
Živković, Dejan
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: On the multiplicities of eigenvalues of graphs and their vertex deleted subgraphs: Old and new results
Journal: Electronic Journal of Linear Algebra
Volume: 30
First page: 85
Last page: 105
Issue Date: 1-Jan-2015
Rank: M23
ISSN: 1537-9582
DOI: 10.13001/1081-3810.2936
Given a simple graph G, let AG be its adjacency matrix. A principal submatrix of AGof order one less than the order of G is the adjacency matrix of its vertex deleted subgraph. It is well-known that the multiplicity of any eigenvalue of AG and such a principal submatrix can differ by at most one. Therefore, a vertex v of G is a downer vertex (neutral vertex, or Parter vertex) with respect to a fixed eigenvalue μ if the multiplicity of μ in AG−v goes down by one (resp., remains the same, or goes up by one). In this paper, we consider the problems of characterizing these three types of vertices under various constraints imposed on graphs being considered, on vertices being chosen and on eigenvalues being observed. By assigning weights to edges of graphs, we generalize our results to weighted graphs, or equivalently to symmetric matrices.
Keywords: Adjacency matrix | Cut vertex | Downer vertex | Graph | Kronecker product | Multiplicity | Neutral vertex | Parter vertex
Publisher: International Linear Algebra Society
Project: Graph theory and mathematical programming with applications in chemistry and computer science 
Development of new information and communication technologies, based on advanced mathematical methods, with applications in medicine, telecommunications, power systems, protection of national heritage and education 
QREN, Grant Cloud Thinking CENTRO-07-ST24-FEDER-002031
FCT - Fundação para a Ciênciae a Tecnologia, Project PEst-OE/MA/UI4106/2014 .
“Applications of Graph Spectra in Computer Science”, bilateral project supported by the governments of Serbia and Portugal

Show full item record


checked on Jul 15, 2024

Page view(s)

checked on May 10, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.