Minimum Number of Distinct Eigenvalues of Graphs

Authors

Bahman Ahmadi, University of Regina
Fatehmeh Alinaghipour, University of Regina
Michael S. Cavers, University of Calgary
Shaun Fallat, University of Regina
Karen Meagher, University of Regina
Shahla Nasserasr, Nova Southeastern UniversityFollow

Document Type

Article

Publication Date

9-1-2013

Publication Title

Electronic Journal of Linear Algebra

Keywords

Symmetric matrix, Eigenvalue, Join of graphs, Diameter, Trees, Bipartite graph, Maximum multiplicity

ISSN

1081-3810

Volume

26

First Page

673

Last Page

691

Abstract

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 Gare provided to show that adding and deleting edges or vertices can dramatically change the value ofq(G). Finally, the set of graphs Gwith q(G) near the number of vertices is shown to be a subset of known families of graphs with small maximum multiplicity

Comments

AMS subject classifications. 05C50, 15A18

NSUWorks Citation

Ahmadi, Bahman; Alinaghipour, Fatehmeh; Cavers, Michael S.; Fallat, Shaun; Meagher, Karen; and Nasserasr, Shahla, "Minimum Number of Distinct Eigenvalues of Graphs" (2013). Mathematics Faculty Articles. 75.
https://nsuworks.nova.edu/math_facarticles/75

DOI

10.13001/1081-3810.1679