Minimum number of distinct eigenvalues of graphs

View/ Open
Date
2013-09Author
Ahmadi, Bahman
Alinaghipour, Fatemeh
Cavers, Michael
Fallat, Shaun
Meagher, Karen
Nasserasr, Shahla
Metadata
Show full item recordAbstract
The minimum number of distinct eigenvalues, taken over all real symmetric matrices
compatible with a given graph G, is denoted by q(G). Using other parameters related to G, bounds
for q(G) are proven and then applied to deduce further properties of q(G). It is shown that there
is a great number of graphs G for which q(G) = 2. For some families of graphs, such as the
join of a graph with itself, complete bipartite graphs, and cycles, this minimum value is obtained.
Moreover, examples of graphs G are provided to show that adding and deleting edges or vertices can
dramatically change the value of q(G). Finally, the set of graphs G with q(G) near the number of
vertices is shown to be a subset of known families of graphs with small maximum multiplicity.