Discrete Math Research Group at the University of Regina

For a graph $G$ on $n$ vertices, $S(G)$ denotes the set of all real $n \times n$ symmetric matrices with $A=[a_{ij}]$ such that $a_{ij}\neq 0$, for $i\neq j$ if and only if vertices $i$ and $j$ are connected by an edge. The minimum number of distinct eigenvalues of $A$ when minimum is taken over all matrices in $S(G)$ is denoted by $q(G)$. We have many questions about this parameter $q$. For example $q(G) =1$ if and only if $G$ is the empty graph. So for which graphs $G$ is $q(G) =2$? So far we have found far many more than we ever expected! On the other end of the scale, $q(G)$ is equal to the number of vertices in $G$ if and only if $G$ is a path. So for which graphs $G$ is $q(G)$ one less than the number of vertices?