Sparsity of graphs that allow two distinct eigenvalues

The parameter q(G) of a graph G is the minimum number of distinct eigenvalues over the family of symmetric matrices described by G. It is shown that the minimum number of edges necessary for a connected graph G to have q(G)=2 is 2n−4 if n is even, and 2n−3 if n is odd. In addition, a characterizatio...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2023-10, Vol.674, p.377-395
Main Authors: Barrett, Wayne, Fallat, Shaun, Furst, Veronika, Kenter, Franklin, Nasserasr, Shahla, Rooney, Brendan, Tait, Michael, van der Holst, Hein
Format: Article
Language:English
Subjects:
Inverse eigenvalue problem for graphs
Orthogonality
q-parameter
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The parameter q(G) of a graph G is the minimum number of distinct eigenvalues over the family of symmetric matrices described by G. It is shown that the minimum number of edges necessary for a connected graph G to have q(G)=2 is 2n−4 if n is even, and 2n−3 if n is odd. In addition, a characterization of graphs for which equality is achieved in either case is given.
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2023.06.004