Minimum number of distinct eigenvalues of graphs
| Autor: | Ahmadi, Bahman, Alinaghipour, Fatemeh, Cavers, Michael S., Fallat, Shaun, Meagher, Karen, Nasserasr, Shahla |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 19 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|