Originator: Willem Haemers (presented by Sebastian Cioaba - REGS 2011)
Definitions: The adjacency matrix $A$ of a graph $G$ has rows and columns indexed by its vertices (in the same order), with $(u,v)$-entry $1$ when $u$ and $v$ are adjacent and $0$ otherwise. Since $A$ is real and symmetric, its eigenvalues $\lambda_1,\ldots,\lambda_n$ (indexed in nonincreasing order) are real; these are the eigenvalues of $G$, and the multiset of eigenvalues is the spectrum of $G$. Spectral graph theory studies the eigenvalues of graphs and their connections to combinatorial graph parameters. Nonisomorphic graphs with the same spectrum are cospectral, and they are called cospectral mates. A graph $G$ is determined by its spectrum or unispectral if it has no cospectral mates.
Background: In the 1970s, Schwenk proved that almost all trees are NOT unispectral. Recently, Haemers conjectured that almost all graphs are unispectral. In general, proving that a graph is unispectral is nontrivial. Van Dam and Haemers [DH1,DH2] have provided surveys of these topics.
Godsil and McKay [GM] introduced a method of constructing graphs with the same spectrum (called Godsil-McKay switching). Consider a graph $G$ whose vertices can be partitioned into subsets $D, C_1, \dots, C_k$ such that
Problem 1: Construct (perhaps using Godsil-McKay switching) two cospectral regular graphs $G$ and $G'$ such that $G$ has a perfect matching and $G'$ does not.
The non-regular graph $C_4+P_k$ is cospectral with the graph obtained from
the path $P_k$ by adding two pendant edges at each of its endpoints. When $k$
is even, this graph does not have a perfect matching, but $C_4+P_k$ does.
Aidan Roy used Godsil-McKay switching to construct an example of two connected cospectral graphs $G$ and $G'$ such that $G$ contains a perfect matching and $G'$ does not contain a perfect matching. Stephen Hartke checked by computer all $3$-regular cospectral graphs up to $20$ vertices; they all had the same matching number.
Problem 2: Construct (perhaps using Godsil-McKay switching) two regular cospectral graphs $G$ and $G'$ whose edge-chromatic numbers are different.
[DH1] E. van Dam and W.H. Haemers, Which graphs are determined by their spectrum? (Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002), Linear Algebra Appl. 373 (2003), 241-272.
[DH2] E. van Dam and W.H. Haemers, Developments on spectral characterizations of graphs, Discrete Math. 309 (2009), no. 3, 576-586.
[GM] C. Godsil and B. McKay, Constructing cospectral graphs, Aequationes Math. 25 (1982), no. 2-3, 257-268.