Published in

International Linear Algebra Society, Electronic Journal of Linear Algebra, (30), 2015

DOI: 10.13001/1081-3810.2936

Links

Tools

Export citation

Search in Google Scholar

On the multiplicities of eigenvalues of graphs and their vertex deleted subgraphs: old and new results

This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown
Data provided by SHERPA/RoMEO

Abstract

Given a simple graph G, let A(G) be its adjacency matrix. A principal submatrix of A(G) of 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 A(G) 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 A(G)−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 generalizeour results to weighted graphs, or equivalently to symmetric matrices.